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_SUCCESS); or exit(EXIT_FAILURE);
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_SUCCESS);
}

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(unsigned 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(unsigned 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.andrew.cmu.edu> wrote in message news:<Pi**********************************@unix42. 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_SUCCESS); or exit(EXIT_FAILURE);
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(unsigned 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,pb,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*******************@newssvr25.news.prodigy .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.

[Christian Bau]

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

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.

With your program, the time between start and stop is almost exactly
zero. 0.041 seconds is about the time a cheap, modern PC takes to
execute lets say 40 to 100 million instructions. How many instructions
do you think your code needed?

To get a result that is anywhere near reasonable you could do something
like this:

static void test_function (void) {
/* Here goes the code you want to test */
}

int main (void) {
#define ITERATIONS 1
unsigned long i;
for (i = 0; i < ITERATIONS; ++i)
test_function ();
return 0;
}

Measure the time. Then double ITERATIONS, check how long it takes now.
Repeat until you can see that doubling ITERATIONS doubles the execution
time.

[Christian Bau]

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

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.

I will in the future carefully check any CV to see whether it mentions
Boston College :-(

[CBFalconer]

mark wrote:

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.

Please do not toppost, and please do snip non-germane quotations.
Topposting is not condoned in this newsgroup.

IIRC your original (now lost due to topposting) appeared to be
simulating a serial full adder. I think I spotted some logical
errors, but we'll never know now.

If you don't explain why you want to do such things, many people
will suggest much more efficient methods, such as dealing with a
byte/short/int/long worth of bits at a time.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

[mark]

my views and actions don't reflect the views of my university. so,
please do not let this affect your judgment of the school. as for my
coding, i never had to resort to cheating while at the university. if
the problem was difficult, then i would merely end up with bloated
code. perhaps, there was cheating by other students in the program but
no more so than another university.

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

I will in the future carefully check any CV to see whether it mentions
Boston College :-(

mark wrote:

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.

[Paul Hsieh]

no************@yahoo.com (mark) wrote:

I am trying to make the function addbitwise more efficient.

Under the assumption that x[] and y[] hold only the values 0 and 1
(which I gather from the algorithm and what you tried to say) try the
following:

int addbitwise(int x[], int y[]) {
int xx = x[4]+((x[3]+((x[2]+((x[1]+(x[0]<<1))<<1))<<1))<<1);
int yy = y[4]+((y[3]+((y[2]+((y[1]+(y[0]<<1))<<1))<<1))<<1);
return xx+yy >= 32;
}

BTW, this is not such a great newsgroup for seeking advice on code
optimization. The people who post here are C language lawyers. Even
the C geniuses here aren't going to give very insightful answers.
OTOH, I don't really know if there is a good code optimization
newsgroup anywhere.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[Thomas Matthews]

Paul Hsieh wrote:

no************@yahoo.com (mark) wrote:

I am trying to make the function addbitwise more efficient.

Under the assumption that x[] and y[] hold only the values 0 and 1
(which I gather from the algorithm and what you tried to say) try the
following:

int addbitwise(int x[], int y[]) {
int xx = x[4]+((x[3]+((x[2]+((x[1]+(x[0]<<1))<<1))<<1))<<1);
int yy = y[4]+((y[3]+((y[2]+((y[1]+(y[0]<<1))<<1))<<1))<<1);
return xx+yy >= 32;
}

BTW, this is not such a great newsgroup for seeking advice on code
optimization. The people who post here are C language lawyers. Even
the C geniuses here aren't going to give very insightful answers.
OTOH, I don't really know if there is a good code optimization
newsgroup anywhere.

--
Paul Hsieh

But what are you optimizing for: Speed, Code Size, Readability,
Portability?

As many people here have stated, profile before optimizing. Much
time is spent in small areas of code. More often than not, the
critical factor is quality first, then the others.

At my work, we only optimize if we need space (to add more code)
or the execution takes too long. In many real-time embedded
systems, there is a fixed amount of time between critical events.
If the code execeeds its time window, then the event is missed
or a nice backlog develops.

Personally, if the OP's function needed full optimization, I
would write it in assembly language. I've found bit manipulation
easier in assembly language than C or other high level languages.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

[Dan Pop]

In <79**************************@posting.google.com > qe*@pobox.com (Paul Hsieh) writes:

BTW, this is not such a great newsgroup for seeking advice on code
optimization. The people who post here are C language lawyers. Even
the C geniuses here aren't going to give very insightful answers.

Some of them are also experienced C programmers, willing to discuss
the optimisation vs portability trade-offs, when such discussions make
sense.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Paul Hsieh]

Try this:

int addbitwise (int x[], int y[]) {
int xx, yy

xx = x[4] + ((x[3] + ((x[2] + ((x[1] + (x[0] << 1)) << 1)) << 1)) << 1);
yy = y[4] + ((y[3] + ((y[2] + ((y[1] + (y[0] << 1)) << 1)) << 1)) << 1);
return xx + yy >= 32;
}

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[Paul Hsieh]

Th****************************@sbcglobal.net says...

Paul Hsieh wrote:

no************@yahoo.com (mark) wrote:

I am trying to make the function addbitwise more efficient.
Under the assumption that x[] and y[] hold only the values 0 and 1
(which I gather from the algorithm and what you tried to say) try the
following:

int addbitwise(int x[], int y[]) {
int xx = x[4]+((x[3]+((x[2]+((x[1]+(x[0]<<1))<<1))<<1))<<1);
int yy = y[4]+((y[3]+((y[2]+((y[1]+(y[0]<<1))<<1))<<1))<<1);
return xx+yy >= 32;
}

BTW, this is not such a great newsgroup for seeking advice on code
optimization. The people who post here are C language lawyers. Even
the C geniuses here aren't going to give very insightful answers.
OTOH, I don't really know if there is a good code optimization
newsgroup anywhere.

--
Paul Hsieh

But what are you optimizing for: Speed, Code Size, Readability,
Portability?

In this case, I think I've won on all those except possibly portability to
systems for which integers are less than 6 bits.

Speed: If this routine doesn't waste the original or anyone else's post by at
least a factor of 2 I would be very very surprised.

Code Size: Its 3 lines. Even the object code is likely to be competitive if
not smaller -- a for loop for just 5 iterations?

Readability: The code obviously coallesces the 5 bits of each into a packed 2s
complement integer (horner's rule) then checks if the resulting add >= 32
(carries over to the 5th bit.) It actually takes some analysis to know for
sure that the other submissions actually does this.
As many people here have stated, profile before optimizing.
And how do you know the OP didn't do this?
[...] Personally, if the OP's function needed full optimization, I
would write it in assembly language. I've found bit manipulation
easier in assembly language than C or other high level languages.

That rule of thumb seems too rough. You use assembly language when your
compiler produced inadequate code and you can incurr the maintenance and non-
portability penalty of using assembly language.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[Christian Bau]

In article <MP************************@news.sf.sbcglobal.net> ,
qe*@pobox.com (Paul Hsieh) wrote:

Th****************************@sbcglobal.net says...

As many people here have stated, profile before optimizing.

And how do you know the OP didn't do this?

He used a unix tool to measure the total execution time of the program,
which was 0.041 seconds. The function in question was called once. I
would guess that the execution time of that function is less than a
microsecond, so the ratio overhead / execution time is about 41,000 to
1. If he replaced his function with yours which as a rough guess would
be ten times faster, then his measurement will still be 0.041 seconds.

[mark]

qe*@pobox.com (Paul Hsieh) wrote in message news:<79*************************@posting.google.c om>...

Try this:

int addbitwise (int x[], int y[]) {
int xx, yy

xx = x[4] + ((x[3] + ((x[2] + ((x[1] + (x[0] << 1)) << 1)) << 1)) << 1);
yy = y[4] + ((y[3] + ((y[2] + ((y[1] + (y[0] << 1)) << 1)) << 1)) << 1);
return xx + yy >= 32;
}

i will... btw, i guess i wasn't so clear before but i am optimizing
for speed and all other factors (code size, portability, etc.) in this
case are not a concern. thanks...

mark.

[Paul Hsieh]

Christian Bau <ch***********@cbau.freeserve.co.uk> wrote:

qe*@pobox.com (Paul Hsieh) wrote:

Th****************************@sbcglobal.net says...

As many people here have stated, profile before optimizing.

And how do you know the OP didn't do this?

He used a unix tool to measure the total execution time of the program,
which was 0.041 seconds. The function in question was called once. I
would guess that the execution time of that function is less than a
microsecond, so the ratio overhead / execution time is about 41,000 to
1. If he replaced his function with yours which as a rough guess would
be ten times faster, then his measurement will still be 0.041 seconds.

Yes, I noticed that part of the thread. However, the fact that he
made an error if understanding order of magnitude of various things
going on in program execution, it doesn't preclude the possibility
that he correctly profiled at the beginning, but just followed it up
by doing a detailed analysis of a small section of code but measured
it wrong.

But this is comp.lang.c, not comp.programming.realworld so discussions
of what really matters to programmers is probably OT around here.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[Richard Heathfield]

Paul Hsieh wrote:

But this is comp.lang.c, not comp.programming.realworld so discussions
of what really matters to programmers is probably OT around here.

Speak for yourself. Portable C programming is topical here, and portable C
programming matters for those who use this newsgroup regularly. If it
didn't, they wouldn't use it, would they?

Yes, there are things that matter to me other than portable C programming,
but there are *other newsgroups* for discussing such things.

--
Richard Heathfield : bi****@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

[Grumble]

Paul Hsieh wrote:

In this case, I think I've won on all those except possibly
portability to systems for which integers are less than 6 bits.

But I thought:

(CHAR_BITS >= 8) && (sizeof int >= sizeof char)

Am I mistaken?

[CBFalconer]

Grumble wrote:

Paul Hsieh wrote:

In this case, I think I've won on all those except possibly
portability to systems for which integers are less than 6 bits.

But I thought:

(CHAR_BITS >= 8) && (sizeof int >= sizeof char)

Am I mistaken?

Please show me how you code integers, which must range from -32767
through 32767, in those 6 bits. These are min/max values allowed
for INT_MIN and INT_MAX.

When you show me, I believe I can immediately create something
that compresses all zip, bzip2, gzip, etc. files by a further
factor of better than two.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

[Grumble]

CBFalconer wrote:

Grumble wrote:

Paul Hsieh wrote:

In this case, I think I've won on all those except possibly
portability to systems for which integers are less than 6 bits.

But I thought:

(CHAR_BITS >= 8) && (sizeof int >= sizeof char)

Am I mistaken?

Please show me how you code integers, which must range from -32767
through 32767, in those 6 bits. These are min/max values allowed
for INT_MIN and INT_MAX.

When you show me, I believe I can immediately create something
that compresses all zip, bzip2, gzip, etc. files by a further
factor of better than two.

Chuck,

Are you responding to me?

In any case, are you saying that an int must be at least 16 bits wide?

[Arthur J. O'Dwyer]

On Fri, 5 Dec 2003, Grumble wrote:

CBFalconer wrote:

Grumble wrote:

Paul Hsieh wrote:

In this case, I think I've won on all those except possibly
portability to systems for which integers are less than 6 bits.

But I thought:
(CHAR_BITS >= 8) && (sizeof int >= sizeof char)
Am I mistaken?

Please show me how you code integers, which must range from -32767
through 32767, in those 6 bits. These are min/max values allowed
for INT_MIN and INT_MAX.

When you show me, I believe I can immediately create something
that compresses all zip, bzip2, gzip, etc. files by a further
factor of better than two.

Chuck,

Are you responding to me?

In any case, are you saying that an int must be at least 16 bits wide?

I don't know to whom he's responding, but that is correct -- ints
must be at least 16 bits wide in order to be able to represent values
from INT_MIN to INT_MAX. And wider if INT_MIN or INT_MAX have larger
absolute values.

-Arthur

[CBFalconer]

Grumble wrote:

CBFalconer wrote:

Grumble wrote:

Paul Hsieh wrote:

In this case, I think I've won on all those except possibly
portability to systems for which integers are less than 6 bits.

But I thought:

(CHAR_BITS >= 8) && (sizeof int >= sizeof char)

Am I mistaken?

Please show me how you code integers, which must range from -32767
through 32767, in those 6 bits. These are min/max values allowed
for INT_MIN and INT_MAX.

When you show me, I believe I can immediately create something
that compresses all zip, bzip2, gzip, etc. files by a further
factor of better than two.

Are you responding to me?

In any case, are you saying that an int must be at least 16 bits wide?

I am saying that they have to represent that range of values.
They must also be constructed out of binary weighted bits. So, if
you can show me how to meet standards with a six bit integer, I
can do other miraculous things :-)

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

[Paul Hsieh]

Grumble <in*****@kma.eu.org> wrote:

Paul Hsieh wrote:

In this case, I think I've won on all those except possibly
portability to systems for which integers are less than 6 bits.

But I thought:

(CHAR_BITS >= 8) && (sizeof int >= sizeof char)

Am I mistaken?

Ok, then maybe it is portable. What do I look like? A language lawyer?

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[Ben Pfaff]

Grumble <in*****@kma.eu.org> writes:

Paul Hsieh wrote:

In this case, I think I've won on all those except possibly
portability to systems for which integers are less than 6 bits.

But I thought:

(CHAR_BITS >= 8) && (sizeof int >= sizeof char)

Am I mistaken?

No, although there is no S in CHAR_BIT and you forgot the
mandatory parentheses in this usage of the sizeof operator. A
byte in C is at least 8 bits, and every object is at least one
byte in size.
--
A competent C programmer knows how to write C programs correctly,
a C expert knows enough to argue with Dan Pop, and a C expert
expert knows not to bother.

[Grumble]

Ben Pfaff wrote:

Grumble <in*****@kma.eu.org> writes:

But I thought:

(CHAR_BITS >= 8) && (sizeof int >= sizeof char)

Am I mistaken?

No, although there is no S in CHAR_BIT and you forgot the
mandatory parentheses in this usage of the sizeof operator. A
byte in C is at least 8 bits, and every object is at least one
byte in size.

CHAR_BIT. No 'S'. Got that.

Are parentheses mandatory when sizeof is used to evaluate a type
instead of an object?

[Irrwahn Grausewitz]

Grumble <in*****@kma.eu.org> wrote:
<snip>

Are parentheses mandatory when sizeof is used to evaluate a type
instead of an object?

Yes.

Regards
--
Irrwahn Grausewitz (ir*******@freenet.de)
welcome to clc : http://www.angelfire.com/ms3/bchambl...me_to_clc.html
clc faq-list : http://www.eskimo.com/~scs/C-faq/top.html
acllc-c++ faq : http://www.contrib.andrew.cmu.edu/~a...acllc-c++.html