EFFICIENCY question: need help from the C geniuses

[mark]

Hello-

i am trying to make the function addbitwise more efficient. the code
below takes an array of binary numbers (of size 5) and performs
bitwise addition. it looks ugly and it is not elegant but it appears
to work. using time, i measured it takes .041s to execute, which i
admit isnt much. but, the problem is that this procedure will be
called many, many times in my project (probably at least a few
thousand times, if not more) so thus, efficiency very is important.
any suggestions (and explanations)? thanks...!

mark.

int main()
{
int arr1[5];
int arr2[5];

arr1[0] = 0;
arr1[1] = 1;
arr1[2] = 0;
arr1[3] = 0;
arr1[4] = 0;

arr2[0] = 1;
arr2[1] = 0;
arr2[2] = 1;
arr2[3] = 1;
arr2[4] = 0;

addbitwise(arr1 , arr2);

exit(1);
}

int addbitwise(int x[], int y[])
{
int result[5];
int i, carry = 0;

for (i=4; i>=0; i--)
{
result[i] = x[i] ^ y[i]; /* result of the bitwise
add */

if (x[i] & y[i]) /* a carry has occured */
{
carry = 1;

if (i != 0) /* prevents final iteration */
{ /* from peeking out of bounds */
if (x[i-1] == 0)
{
x[i-1] = 1; /* replace the next 0 bit with the carry'd 1 */
carry = 0;
}

else if (y[i-1] == 0) /* peek at the next array bit */
{
y[i-1] = 1;
carry = 0;
}
}
}
}

return(carry);
}

_______________ ______
Mark Fonnemann
Boston College
B.A., Computer Science 2000
M.A., Mathematics 2002
_______________ ______

[Arthur J. O'Dwyer]

On Mon, 30 Nov 2003, mark wrote:

i am trying to make the function addbitwise more efficient.
Oh dear, here we go again... :) You see, Mark, this newsgroup
gets a lot of people asking "how can I make this code faster, or
smaller, or more cache-utilizing, or whatever?" Usually on problems
that are trivial, or homework, or both. [Kind of like yours seems
to be.] And the simple answer to the efficiency question is:
It depends.
The complex answer is also: It depends. It depends on your
system, on your compiler optimization level, on lots of things
that are not even remotely on-topic here.
But we can help, a little bit, by stating the obvious things that
you may have been overlooking. Such as, "Why on earth are you
trying to store integers in arrays anyway?" Or "How on earth did
this monstrosity end up not only existing, but in the middle of
a loop?"
the code
below takes an array of binary numbers (of size 5) and performs
bitwise addition. it looks ugly and it is not elegant but it appears
to work. using time, i measured it takes .041s to execute, which i
admit isnt much.
It depends. On how fast your machine is, and how fast other
things need to execute. Among other considerations.
but, the problem is that this procedure will be
called many, many times in my project (probably at least a few
thousand times, if not more) so thus, efficiency very is important.
any suggestions (and explanations)? thanks...!

mark.
int main()
int main(void) is preferred by many here, myself included.
{
int arr1[5];
int arr2[5];

arr1[0] = 0;
arr1[1] = 1;
arr1[2] = 0;
arr1[3] = 0;
arr1[4] = 0;

arr2[0] = 1;
arr2[1] = 0;
arr2[2] = 1;
arr2[3] = 1;
arr2[4] = 0;

addbitwise(arr1 , arr2);
Okay, first optimization:

int i1 = 8;
int i2 = 22;
(i1+i2 > 31); /* duplicate effects of 'addbitwise' */

I bet that runs a *lot* faster, even considering that "it depends."
You want real solutions, you'd better write down the real problem.
What is forcing you to use these ugly "bit arrays" in the first
place? Can you use a better data structure?
exit(1);
Non-portable return code. exit(EXIT_SUCCE SS); or exit(EXIT_FAILU RE);
are portable, as is the simple and traditional return 0; .
}

int addbitwise(int x[], int y[])
{
int result[5];
int i, carry = 0;

for (i=4; i>=0; i--)
{
result[i] = x[i] ^ y[i]; /* result of the bitwise
add */

if (x[i] & y[i]) /* a carry has occured */
{
carry = 1;

if (i != 0) /* prevents final iteration */
{ /* from peeking out of bounds */
if (x[i-1] == 0)
{
x[i-1] = 1; /* replace the next 0 bit with the carry'd 1 */
carry = 0;
}

else if (y[i-1] == 0) /* peek at the next array bit */
{
y[i-1] = 1;
carry = 0;
}
}
}
}

return(carry);
}

This is disgusting. Since you're using integers anyway, how's
about giving this a try:

int addbitwise(int x[5], int y[5])
{
int t = 0;
int i;
for (i=0; i < 5; ++i)
t += (x[i]+y[i]) << (4-i);
return (t > 31);
}

[NB: the explicit use of '5' in the array bounds -- help your
maintenance programmers, please!]

There are certainly better ways to do it, but until you explain
*why* you need this particular homework problem solved, I don't
feel much like giving any better answers.

Still HTH,
-Arthur

[Morris Dovey]

mark wrote:

Hello-

i am trying to make the function addbitwise more efficient. the code
below takes an array of binary numbers (of size 5) and performs
bitwise addition. it looks ugly and it is not elegant but it appears
to work. using time, i measured it takes .041s to execute, which i
admit isnt much. but, the problem is that this procedure will be
called many, many times in my project (probably at least a few
thousand times, if not more) so thus, efficiency very is important.
any suggestions (and explanations)? thanks...!

mark.

int main(void)
{ int arr1[5];
int arr2[5];

arr1[0] = 0;
arr1[1] = 1;
arr1[2] = 0;
arr1[3] = 0;
arr1[4] = 0;

arr2[0] = 1;
arr2[1] = 0;
arr2[2] = 1;
arr2[3] = 1;
arr2[4] = 0;

addbitwise(arr1 , arr2);
exit(EXIT_SUCCE SS);
}

int addbitwise(int x[], int y[])
{ int result[5];
int i, carry = 0;

for (i=4; i>=0; i--)
{ result[i] = x[i] ^ y[i]; /* result of the bitwise add */
if (x[i] & y[i]) /* a carry has occured */
{ carry = 1;
if (i != 0) /* prevents final iteration */
{ if (x[i-1] == 0)
{ x[i-1] = 1; /* replace the next 0 bit with the carry'd 1 */
carry = 0;
}
else if (y[i-1] == 0) /* peek at the next array bit */
{ y[i-1] = 1;
carry = 0;
}
}
}
}

return(carry);
}

Mark...

I'm assuming you want to perform unsigned two's complement
addition. Why not put all the bits into an unsigned arithmetic
type? If there are only five bits, then put all five bits into an
unsigned char. You already know that the sum of two five bit
entities can't be more than six bits (note that this will return
as soon as all carries have been propagated):

unsigned char addbitwise(unsi gned char *a,unsigned char *b)
{ unsigned char t;
while (*b)
{ t = *a ^ *b; /* half-adder result */
*b = (*a & *b) << 1; /* propagate any carries */
*a = t; /* prepare to add carries */
};
return *b >> 5;
}

If it were my project I'd just pass in a and b and return the sum:

unsigned char addbitwise(unsi gned char a,unsigned char b)
{ unsigned char t;
while (b)
{ t = a ^ b; /* half-adder result */
b = (a & b) << 1; /* propagate any carries */
a = t; /* prepare to add carries */
};
return a; /* return sum */
}

--
Morris Dovey
West Des Moines, Iowa USA
C links at http://www.iedu.com/c
Read my lips: The apple doesn't fall far from the tree.

[Christian Bau]

In article <f6************ **************@ posting.google. com>,
no************@ yahoo.com (mark) wrote:

Hello-

i am trying to make the function addbitwise more efficient. the code
below takes an array of binary numbers (of size 5) and performs
bitwise addition. it looks ugly and it is not elegant but it appears
to work. using time, i measured it takes .041s to execute, which i
admit isnt much. but, the problem is that this procedure will be
called many, many times in my project (probably at least a few
thousand times, if not more) so thus, efficiency very is important.
any suggestions (and explanations)? thanks...!

You measured the time to start and stop the program, nothing else.

[NFish]

mark wrote:

Hello-

i am trying to make the function addbitwise more efficient. the code
below takes an array of binary numbers (of size 5) and performs
bitwise addition. it looks ugly and it is not elegant but it appears
to work. using time, i measured it takes .041s to execute, which i
admit isnt much.
It's a huge amount, and it's probably wildly inaccurate.
but, the problem is that this procedure will be
called many, many times in my project (probably at least a few
thousand times, if not more) so thus, efficiency very is important.
any suggestions (and explanations)? thanks...!
Is there some aversion you have to using the addition operator? Here's
a simpler version I whipped up:

int add(const int* x, const int* y) {
int i, carry=0;
int result[5];
for (i=4; i >= 0; i--) {
int sum = carry + x[i] + y[i];
carry = sum >> 1;
result[i] = sum & 1;
}
return carry;
}

On my machine, it took about 8 seconds to do one hundred million calls
to your function, including the overhead of memcpying the arrays each
time (because your function is destructive wrt the parameters).

It took 4 seconds for my version with an equivalent memcpy, and 3
seconds without.

mark.

int main()
{
int arr1[5];
int arr2[5];

arr1[0] = 0;
arr1[1] = 1;
arr1[2] = 0;
arr1[3] = 0;
arr1[4] = 0;

arr2[0] = 1;
arr2[1] = 0;
arr2[2] = 1;
arr2[3] = 1;
arr2[4] = 0;
int arr1[5] = {0,1,0,0,0};
int arr2[5] = {1,0,1,1,0};

addbitwise(arr1 , arr2);

exit(1);
exit(0) or return 0.
}

int addbitwise(int x[], int y[])
{
int result[5];
int i, carry = 0;

for (i=4; i>=0; i--)
{
result[i] = x[i] ^ y[i]; /* result of the bitwise
add */

You can calculate both the carry and the sum with the + operator.
if (x[i] & y[i]) /* a carry has occured */
Branching is typically slow. You might find it faster to replace the
next zero bit with the carry, whether the carry is a 0 or a 1. That is,
write

carry = x[i] & y[i];

and skip the if altogether.
{
carry = 1;

if (i != 0) /* prevents final iteration */
{ /* from peeking out of bounds */
if (x[i-1] == 0)
{
x[i-1] = 1; /* replace the next 0 bit with the carry'd 1 */
carry = 0;
}

else if (y[i-1] == 0) /* peek at the next array bit */
{
y[i-1] = 1;
carry = 0;
}
}
}
}

return(carry);
}

Hope this has been useful.

[mark]

Christian Bau <ch***********@ cbau.freeserve. co.uk> wrote in message news:<ch******* *************** ***********@slb-newsm1.svr.pol. co.uk>...

In article <f6************ **************@ posting.google. com>,
no************@ yahoo.com (mark) wrote:

Hello-

i am trying to make the function addbitwise more efficient. the code
below takes an array of binary numbers (of size 5) and performs
bitwise addition. it looks ugly and it is not elegant but it appears
to work. using time, i measured it takes .041s to execute, which i
admit isnt much. but, the problem is that this procedure will be
called many, many times in my project (probably at least a few
thousand times, if not more) so thus, efficiency very is important.
any suggestions (and explanations)? thanks...!

You measured the time to start and stop the program, nothing else.

then how would i measure the entire execution of the program...? i
used time ./a where a was the name of the executable.

thanks...
mark.

[mark]

Arthur-

it may be trivial to you, but despite programming in C for several
years (pascal before that, atari basic before that) bitwise operators
always give me a problem. clearly, i could have defined it as two
integers and used the binary additive operator denoted '+' if that was
what i was trying to accomplish. however, my project works entirely
with bits, and as we all know, the byte is the smallest indivisble
unit defined in C.

that said, i'm kinda offended about the HW problem issue. i know that
many people probably use this group for answers. however, that is not
my case. i graduated from Boston College in 2000 with a degree in
computer science as denoted in my sig file. perhaps, this was
overlooked. as for the other "cheaters", well rather than criticize
just be assured that you can only fool people for so long about how
well/not well you can code. those people will get what they deserve
eventually. i see too few people here willing to let fate take its
part and i wonder if its insecurity.

regardless, i understand your intentions, no hard feelings. thanks...

mark.

"Arthur J. O'Dwyer" <aj*@nospam.and rew.cmu.edu> wrote in message news:<Pi******* *************** ************@un ix42.andrew.cmu .edu>...

On Mon, 30 Nov 2003, mark wrote:

i am trying to make the function addbitwise more efficient.

Oh dear, here we go again... :) You see, Mark, this newsgroup
gets a lot of people asking "how can I make this code faster, or
smaller, or more cache-utilizing, or whatever?" Usually on problems
that are trivial, or homework, or both. [Kind of like yours seems
to be.] And the simple answer to the efficiency question is:
It depends.
The complex answer is also: It depends. It depends on your
system, on your compiler optimization level, on lots of things
that are not even remotely on-topic here.
But we can help, a little bit, by stating the obvious things that
you may have been overlooking. Such as, "Why on earth are you
trying to store integers in arrays anyway?" Or "How on earth did
this monstrosity end up not only existing, but in the middle of
a loop?"

the code
below takes an array of binary numbers (of size 5) and performs
bitwise addition. it looks ugly and it is not elegant but it appears
to work. using time, i measured it takes .041s to execute, which i
admit isnt much.

It depends. On how fast your machine is, and how fast other
things need to execute. Among other considerations.

but, the problem is that this procedure will be
called many, many times in my project (probably at least a few
thousand times, if not more) so thus, efficiency very is important.
any suggestions (and explanations)? thanks...!

mark.

int main()

int main(void) is preferred by many here, myself included.

{
int arr1[5];
int arr2[5];

arr1[0] = 0;
arr1[1] = 1;
arr1[2] = 0;
arr1[3] = 0;
arr1[4] = 0;

arr2[0] = 1;
arr2[1] = 0;
arr2[2] = 1;
arr2[3] = 1;
arr2[4] = 0;

addbitwise(arr1 , arr2);

Okay, first optimization:

int i1 = 8;
int i2 = 22;
(i1+i2 > 31); /* duplicate effects of 'addbitwise' */

I bet that runs a *lot* faster, even considering that "it depends."
You want real solutions, you'd better write down the real problem.
What is forcing you to use these ugly "bit arrays" in the first
place? Can you use a better data structure?

exit(1);

Non-portable return code. exit(EXIT_SUCCE SS); or exit(EXIT_FAILU RE);
are portable, as is the simple and traditional return 0; .

}

int addbitwise(int x[], int y[])
{
int result[5];
int i, carry = 0;

for (i=4; i>=0; i--)
{
result[i] = x[i] ^ y[i]; /* result of the bitwise
add */

if (x[i] & y[i]) /* a carry has occured */
{
carry = 1;

if (i != 0) /* prevents final iteration */
{ /* from peeking out of bounds */
if (x[i-1] == 0)
{
x[i-1] = 1; /* replace the next 0 bit with the carry'd 1 */
carry = 0;
}

else if (y[i-1] == 0) /* peek at the next array bit */
{
y[i-1] = 1;
carry = 0;
}

}

}
}

return(carry);
}

This is disgusting. Since you're using integers anyway, how's
about giving this a try:

int addbitwise(int x[5], int y[5])
{
int t = 0;
int i;
for (i=0; i < 5; ++i)
t += (x[i]+y[i]) << (4-i);
return (t > 31);
}

[NB: the explicit use of '5' in the array bounds -- help your
maintenance programmers, please!]

There are certainly better ways to do it, but until you explain
*why* you need this particular homework problem solved, I don't
feel much like giving any better answers.

Still HTH,
-Arthur

[Ed Morton]

mark wrote:

Hello-

i am trying to make the function addbitwise more efficient. the code
below takes an array of binary numbers (of size 5) and performs
bitwise addition. it looks ugly and it is not elegant but it appears
to work. using time, i measured it takes .041s to execute, which i
admit isnt much. but, the problem is that this procedure will be
called many, many times in my project (probably at least a few
thousand times, if not more)

You might want to make it a macro instead of a function then, or an
inline function if you're using C99. As a macro, you'd have to be
careful to avoid evaluating the arguments multiple times. Here's one way
based on Morris's first proposed solution:

Instead of this:

unsigned char addbitwise(unsi gned char *a,unsigned char *b)
{ unsigned char t;
while (*b)
{ t = *a ^ *b; /* half-adder result */
*b = (*a & *b) << 1; /* propagate any carries */
*a = t; /* prepare to add carries */
}
return *b >> 5;
}

use this:

#define addbitwise(pa,p b,t) \
do { \
unsigned char _a = *(pa), _b = *(pb); \
while (_b) \
{ (t) = _a ^ _b; /* half-adder result */ \
_b = (_a & _b) << 1; /* propagate any carries */ \
_a = (t); /* prepare to add carries */ \
} \
(t) = _b >> 5; \
} while (0)

Note that this requires what was previously the function return code to
become an extra parameter instead which obviously affects the callers
code, so it may not be practical if this is existing code.

Ed.

[Randy Howard]

In article <f6************ **************@ posting.google. com>,
no************@ yahoo.com says...

Christian Bau <ch***********@ cbau.freeserve. co.uk> wrote in message news:<ch******* *************** ***********@slb-newsm1.svr.pol. co.uk>...

In article <f6************ **************@ posting.google. com>,
no************@ yahoo.com (mark) wrote:

Hello-

i am trying to make the function addbitwise more efficient. the code
below takes an array of binary numbers (of size 5) and performs
bitwise addition. it looks ugly and it is not elegant but it appears
to work. using time, i measured it takes .041s to execute, which i
admit isnt much. but, the problem is that this procedure will be
called many, many times in my project (probably at least a few
thousand times, if not more) so thus, efficiency very is important.
any suggestions (and explanations)? thanks...!

You measured the time to start and stop the program, nothing else.

then how would i measure the entire execution of the program...? i
used time ./a where a was the name of the executable.

thanks...
mark.

If you want a better approximation of the run time of a particular
function, you might consider doing the same thing as you describe
above, but modify your main() such that you call the function(s)
you wish to measure repeatedly in a loop and then divide the time
by the repeat count.

Depending on how long they take to execute, a few hundred or thousand
times. You still need to keep in mind that it's a very rough
approximation and may result in cache artificially changing your results,
particularly if the code path is small.

Even so, you will get a more reasonable value than just calling it
once, in which case the C runtime startup code and linking of any
required shared libraries, etc. will balloon the execution time.

--
Randy Howard _o
2reply remove FOOBAR \<,
_______________ _______()/ ()_____________ _______________ _______________ ___
SCO Spam-magnet: po********@sco. com

[mark]

NFish-

thanks for the very helpful and useful answer... i had written code
myself similar to that and i couldnt figure out why it didn't work.
so, then i assumed that my logic was wrong, the problem i was having
was going to be much tougher, and that a solution involving all these
if-then statements was needed for special cases. well, it turns out it
wasnt the code, it was me. i wasnt adding properly in binary in
certain cases (maybe i should have paid better attention in assembly
language class after all). :-) thanks for your help though, it
reinforced the ideas definitely. thanks again...

mark.

p.s. did you use a unix timing program to measure the 100 million
calls or simply a stopwatch? j/c.

NFish <no****@nowhere .net> wrote in message news:<Kt******* ************@ne wssvr25.news.pr odigy.com>...

mark wrote:

Hello-

i am trying to make the function addbitwise more efficient. the code
below takes an array of binary numbers (of size 5) and performs
bitwise addition. it looks ugly and it is not elegant but it appears
to work. using time, i measured it takes .041s to execute, which i
admit isnt much.

It's a huge amount, and it's probably wildly inaccurate.

but, the problem is that this procedure will be
called many, many times in my project (probably at least a few
thousand times, if not more) so thus, efficiency very is important.
any suggestions (and explanations)? thanks...!

Is there some aversion you have to using the addition operator? Here's
a simpler version I whipped up:

int add(const int* x, const int* y) {
int i, carry=0;
int result[5];
for (i=4; i >= 0; i--) {
int sum = carry + x[i] + y[i];
carry = sum >> 1;
result[i] = sum & 1;
}
return carry;
}

On my machine, it took about 8 seconds to do one hundred million calls
to your function, including the overhead of memcpying the arrays each
time (because your function is destructive wrt the parameters).

It took 4 seconds for my version with an equivalent memcpy, and 3
seconds without.

mark.

int main()
{
int arr1[5];
int arr2[5];

arr1[0] = 0;
arr1[1] = 1;
arr1[2] = 0;
arr1[3] = 0;
arr1[4] = 0;

arr2[0] = 1;
arr2[1] = 0;
arr2[2] = 1;
arr2[3] = 1;
arr2[4] = 0;

int arr1[5] = {0,1,0,0,0};
int arr2[5] = {1,0,1,1,0};

addbitwise(arr1 , arr2);

exit(1);

exit(0) or return 0.

}

int addbitwise(int x[], int y[])
{
int result[5];
int i, carry = 0;

for (i=4; i>=0; i--)
{
result[i] = x[i] ^ y[i]; /* result of the bitwise
add */

You can calculate both the carry and the sum with the + operator.

if (x[i] & y[i]) /* a carry has occured */

Branching is typically slow. You might find it faster to replace the
next zero bit with the carry, whether the carry is a 0 or a 1. That is,
write

carry = x[i] & y[i];

and skip the if altogether.

{
carry = 1;

if (i != 0) /* prevents final iteration */
{ /* from peeking out of bounds */
if (x[i-1] == 0)
{
x[i-1] = 1; /* replace the next 0 bit with the carry'd 1 */
carry = 0;
}

else if (y[i-1] == 0) /* peek at the next array bit */
{
y[i-1] = 1;
carry = 0;
}

}

}
}

return(carry);
}

Hope this has been useful.