Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   Finding sum of absolute differences of memory blocks (http://www.velocityreviews.com/forums/t442590-finding-sum-of-absolute-differences-of-memory-blocks.html)

 equinox1248 05-03-2006 02:45 AM

Finding sum of absolute differences of memory blocks

Hi,

I thought this would be answered several time in this group, but I
couldn't find anything relevant.

What would be the most efficient way of calculating sum of absolute
values of two memory blocks?

Consider A and B size of N:

int temp=0;
for (n=N;n>-1;n--)
temp+= abs(A[n]-B[n]);

How can one optimize this piece of code and make it run faster? Any
tricks are appreciated. FYI, the memory blocks carry integer values.

Thanks!

 Jack Klein 05-03-2006 06:06 AM

Re: Finding sum of absolute differences of memory blocks

On 2 May 2006 19:45:26 -0700, "equinox1248" <equinox1248@yahoo.com>
wrote in comp.lang.c:

> Hi,
>
> I thought this would be answered several time in this group, but I
> couldn't find anything relevant.
>
> What would be the most efficient way of calculating sum of absolute
> values of two memory blocks?

What do you mean by "memory blocks"? Do you mean what the C language
laughingly calls "arrays"?

> Consider A and B size of N:

Now you have a terminology problem. What exactly are 'A' and 'B'? If
you actually have "memory blocks", that is raw memory, the size of the
number of bytes (char sized objects) it contains. On the other hand,
if you have an array of some type, say int or double, it generally has
two different sizes. The result of the sizeof operator on an array
will yield the number of bytes it contains. But generally more useful
is the number of elements it contains, which is the number of bytes in
the array divided by the number of bytes in each element, that is
sizeof array/sizeof (type of array).

> int temp=0;
> for (n=N;n>-1;n--)
> temp+= abs(A[n]-B[n]);
>
> How can one optimize this piece of code and make it run faster? Any
> tricks are appreciated. FYI, the memory blocks carry integer values.
>
> Thanks!

How exactly do you expect to be able to compute a sum of values that
you do not have in any way other than computing each value and adding
it to a sum?

By the way, if you are actually talking about arrays, defined like
this:

#define N some_number

int A[N];
int B[N];

....then your code snippet above has a serious mistake.

Such arrays have N elements numbered 0 through N-1. Your loop is
starting at element N, which is beyond the end of an N element array
in C.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://c-faq.com/
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html

 Walter Roberson 05-03-2006 07:11 AM

Re: Finding sum of absolute differences of memory blocks

equinox1248 <equinox1248@yahoo.com> wrote:
>What would be the most efficient way of calculating sum of absolute
>values of two memory blocks?

>Consider A and B size of N:

>int temp=0;
>for (n=N;n>-1;n--)
> temp+= abs(A[n]-B[n]);

>How can one optimize this piece of code and make it run faster?

Leave the optimization to the compiler. Chances are that it can
do as well as you can for any one architecture -- and the
next compiler over on the next architecture is probably going
to know how to optimize for -that-, whereas any tricks you
might not work on the next platform.

There is something that should be fairly portable:

#define ABSDIFF(i,j) ((i)<(j)?(j)-(i):(i)-(j))

This has problems with side effects, but it saves on the
function call. On the other hand, the abs function call might
be coded as a single inline hardware instruction...

On some highly pipelined implementations, the macro I show
above can be fairly efficient, because the CPU can
"speculate" about the result of the comparison,
calculating both possible results and then "move conditional"
the proper value in -- all without taking any branchs. But that
doesnm't work for all CPU tpes`
--
There are some ideas so wrong that only a very intelligent person
could believe in them. -- George Orwell

 All times are GMT. The time now is 02:28 PM.