Determine which sum is larger

[Peter Ammon]

Howdy,

I have four unsigned long longs a, b, c, d. I want to determine whether
a+b or c+d is larger, as if there were no overflow. That is, ULLONG_MAX
+ 5 should be considered larger than 10 + 20.

The best approach I have thought of so far is to check for overflow in
both sums; if exactly one overflows, that one is larger. Otherwise,
compare the sums normally. Is there a better way?

Thanks for any ideas!
-Peter

 

[Richard Heathfield]

Peter Ammon said:

Howdy,

Hi Peter, ltns.

I have four unsigned long longs a, b, c, d. I want to determine whether
a+b or c+d is larger, as if there were no overflow.

There isn't any overflow, of course, because unsigned types can't overflow.

Your question involves unsigned long long ints, but in fact we can ignore
that, and focus on the fact that they are unsigned types than which we
cannot guarantee having a wider type available.

That is, ULLONG_MAX
+ 5 should be considered larger than 10 + 20.

The best approach I have thought of so far is to check for overflow in
both sums; if exactly one overflows, that one is larger. Otherwise,
compare the sums normally. Is there a better way?

Apart from the nitpick about the word "overflow", I can see no problem with
your existing solution. Any other way is likely to be more complicated.

I did play around with reducing the values a bit - for example, if(a > c) {
a -= c; c = 0; } else { c -= a; a = 0; } and the same for b, d - but I
couldn't see it leading anywhere useful. If a and c were known to share a
high value bit (that is, both were at least half the maximum possible
value for the type), and b and d likewise, it could conceivably have been
useful if you really needed to avoid value wrapping for some reason.

 

[Catsby]

Howdy,

I have four unsigned long longs a, b, c, d. I want to determine whether
a+b or c+d is larger, as if there were no overflow. That is, ULLONG_MAX
+ 5 should be considered larger than 10 + 20.

The best approach I have thought of so far is to check for overflow in
both sums; if exactly one overflows, that one is larger. Otherwise,
compare the sums normally. Is there a better way?

Thanks for any ideas!
-Peter

Hi Peter!

We won't overflow if we check half the sum. Since we lose data, we
clarify unclear results by checking the remainders we snipped out.

int compareULLSums( unsigned long long a, unsigned long long b,
unsigned long long c, unsigned long long d )
{
unsigned long long s1 = (a/2+b/2), s2 = (c/2+d/2);
if( s1 > s2 || ( s1 == s2 && ( (a%2+b%2) > (c%2+d%2) ) ) )
return 1;
return 0;
}

Hope this helps!
- Sam

 

[Philip Potter]

Peter Ammon said:

Your question involves unsigned long long ints, but in fact we can ignore
that, and focus on the fact that they are unsigned types than which we
cannot guarantee having a wider type available.


Apart from the nitpick about the word "overflow", I can see no problem with
your existing solution. Any other way is likely to be more complicated.

I did play around with reducing the values a bit - for example, if(a > c) {
a -= c; c = 0; } else { c -= a; a = 0; } and the same for b, d - but I
couldn't see it leading anywhere useful.

After that process, you have four possibilities:
a == b == 0, a == d == 0, c == b == 0, and c == d == 0.

If a == b == 0, then finding the smaller sum is trivial.
Otherwise if a == d == 0, then b > c gives the comparison you want.
Other cases are handled similarly.

I agree that this is probably more complicated than the OP's original
idea though.

 

[Richard Heathfield]

Philip Potter said:

Richard Heathfield wrote:


After that process, you have four possibilities:
a == b == 0, a == d == 0, c == b == 0, and c == d == 0.

If a == b == 0, then finding the smaller sum is trivial.
Otherwise if a == d == 0, then b > c gives the comparison you want.
Other cases are handled similarly.

See, that's why we have Usenet - so one person can kickstart an idea, and
someone else can carry it on...

I agree that this is probably more complicated than the OP's original
idea though.

....and then consign it to the dustbin of history.

 

[Thad Smith]

We won't overflow if we check half the sum. Since we lose data, we
clarify unclear results by checking the remainders we snipped out.

int compareULLSums( unsigned long long a, unsigned long long b,
unsigned long long c, unsigned long long d )
{
unsigned long long s1 = (a/2+b/2), s2 = (c/2+d/2);
if( s1 > s2 || ( s1 == s2 && ( (a%2+b%2) > (c%2+d%2) ) ) )
return 1;
return 0;
}

What does this say about 5+3 compared with 4+4?

Shouldn't the result of a comparison have three states?

 

[Eric Sosman]

Howdy,

I have four unsigned long longs a, b, c, d. I want to determine whether
a+b or c+d is larger, as if there were no overflow. That is, ULLONG_MAX
+ 5 should be considered larger than 10 + 20.

The best approach I have thought of so far is to check for overflow in
both sums; if exactly one overflows, that one is larger. Otherwise,
compare the sums normally. Is there a better way?

In essence, you're using "it overflowed" to detect whether
the non-stored super-high-order bit is a 1 or a 0. Another way
would be to scale down and handle the low-order bits separately:

const char *answer;
unsigned long long abhi, cdhi;
abhi = (a >> 1) + (b >> 1);
cdhi = (c >> 1) + (c >> 1);
if (abhi > cdhi)
answer = "a+b";
else if (abhi < cdhi)
answer = "c+d";
else {
unsigned int ablo, cdlo;
/* Casts could be omitted, but may help speed: */
ablo = ((unsigned int)a & 1) + ((unsigned int)b & 1);
cdlo = ((unsigned int)c & 1) + ((unsigned int)d & 1);
if (ablo > cdlo)
answer = "a+b";
else if (ablo < cdlo)
answer = "c+d";
else
answer = "neither";
}
printf ("%s is larger\n", answer);

Whether this is better depends on your definition of "better."
It has the possible advantage that the low-order pieces usually
don't need to be examined, but even that advantage depends on the
distribution of input data and may be too small to worry about.

 

[Philip Potter]

What does this say about 5+3 compared with 4+4?

Exactly the same as for 4+4 compared with 4+4.

Shouldn't the result of a comparison have three states?

It depends. This function seems to emulate greater-than, rather than a
three-state strcmp()-style return value. This may be the correct thing,
though it's poorly named if so.

 

[Chris Torek]

In essence, you're using "it overflowed" to detect whether
the non-stored super-high-order bit is a 1 or a 0.
Indeed.

Another way would be to scale down and handle the low-order bits separately:

const char *answer;
unsigned long long abhi, cdhi;
abhi = (a >> 1) + (b >> 1);
cdhi = (c >> 1) + (c >> 1);
if (abhi > cdhi)
answer = "a+b";
else if (abhi < cdhi)
answer = "c+d";
else {
unsigned int ablo, cdlo;
/* Casts could be omitted, but may help speed: */
ablo = ((unsigned int)a & 1) + ((unsigned int)b & 1);
cdlo = ((unsigned int)c & 1) + ((unsigned int)d & 1);
if (ablo > cdlo)
answer = "a+b";
else if (ablo < cdlo)
answer = "c+d";
else
answer = "neither";
}
printf ("%s is larger\n", answer);

Whether this is better depends on your definition of "better."
It has the possible advantage that the low-order pieces usually
don't need to be examined, but even that advantage depends on the
distribution of input data and may be too small to worry about.

For the sake of comparison, here is a stab (untested) at the version
that calculates the extra bit:

unsigned long long ab_sum = a + b;
int ab_extra = ab_sum < a; /* "extra" (top) bit at high end of sum */
unsigned long long cd_sum = c + d;
int cd_extra = cd_sum < c;

const char *answer;

/*
* If the "extra" bits differ, they determine the result.
* Otherwise, the result depends on the straightforward
* comparison of the reduced (mod ULLONG_MAX+1) sums.
*/
if (ab_extra != cd_extra)
answer = ab_extra ? "a+b" : "c+d";
else if (ab_sum != cd_sum)
answer = ab_sum > cd_sum ? "a+b" : "c+d";
else
answer = "neither";

(Eric's version can be shortened by using ?: expressions, so the
length of the source code is not that significant.)

 

[Eric Sosman]

In essence, you're using "it overflowed" to detect whether
the non-stored super-high-order bit is a 1 or a 0.
Indeed.

Another way would be to scale down and handle the low-order bits separately:

const char *answer;
unsigned long long abhi, cdhi;
abhi = (a >> 1) + (b >> 1);
cdhi = (c >> 1) + (c >> 1);
[...]

> [...]
(Eric's version can be shortened by using ?: expressions, so the
length of the source code is not that significant.)

My version could also be improved (although not shortened)
by corretcing the typo ...

 

[Ralf Damaschke]

Exactly the same as for 4+4 compared with 4+4.

OK, right so far (assuming the first expression corresponds
to the first function argument).

It depends. This function seems to emulate greater-than,
rather than a three-state strcmp()-style return value. This
may be the correct thing, though it's poorly named if so.

So you would accept the function's claim "4+4 > 5+3"?

-- Ralf

 

[Philip Potter]

So you would accept the function's claim "4+4 > 5+3"?

Er... no! Good catch.

 

[Tor Rustad]

Howdy,

I have four unsigned long longs a, b, c, d. I want to determine whether
a+b or c+d is larger, as if there were no overflow. That is, ULLONG_MAX
+ 5 should be considered larger than 10 + 20.

The best approach I have thought of so far is to check for overflow in
both sums; if exactly one overflows, that one is larger. Otherwise,
compare the sums normally. Is there a better way?

Not only will your approach work, but it looks simple and require little
overhead too, so I can't really come up with something "better"...

However, let say you find the two smallest numbers of the set {a,b,c,d},
if it's {a,b} or {c,d} you have the answer. If not, those two numbers
can be subtracted from the LHS and RHS, the biggest sum is then given by
max(LHS, RHS).

 

[Bart]

There isn't any overflow, of course, because unsigned types can't overflow.

Are you sure? That would be a very useful property.

 

[Ben Bacarisse]

Are you sure? That would be a very useful property.

Yes. Well I am, and I am pretty sure Richard Heathfield is sure too!

6.2.5 p9 says (in part):

... A computation involving unsigned operands can never overflow,
because a result that cannot be represented by the resulting
unsigned integer type is reduced modulo the number that is one
greater than the largest value that can be represented by the
resulting type.

Outside of the context of standard C, the term overflow is sometimes
used to refer to the warp-around that sometimes happens in both signed
and unsigned arithmetic but, when talking about C, it is better to
stick to the standard terminology.

 

[Bart]

Yes. Well I am, and I am pretty sure Richard Heathfield is sure too!

6.2.5 p9 says (in part):

... A computation involving unsigned operands can never overflow,
because a result that cannot be represented by the resulting
unsigned integer type is reduced modulo the number that is one
greater than the largest value that can be represented by the
resulting type.

Outside of the context of standard C, the term overflow is sometimes
used to refer to the warp-around that sometimes happens in both signed
and unsigned arithmetic but, when talking about C, it is better to
stick to the standard terminology.

That's interesting. So the reason why the following program produces
some 700 million on a 32-bit system instead of 5 billion is nothing to
do with overflow of A+B? It 'wraps' instead?

#include <stdio.h>

void main()
{
unsigned int a,b;

a=3000000000;
b=2000000000;

printf("A = %u\n",a);
printf("B = %u\n",b);
printf("A+B = %u\n",a+b);

}

// Bart

 

[CBFalconer]

Yes. Well I am, and I am pretty sure Richard Heathfield is sure too!

6.2.5 p9 says (in part):

... A computation involving unsigned operands can never overflow,
because a result that cannot be represented by the resulting
unsigned integer type is reduced modulo the number that is one
greater than the largest value that can be represented by the
resulting type.

Outside of the context of standard C, the term overflow is sometimes
used to refer to the warp-around that sometimes happens in both signed
and unsigned arithmetic but, when talking about C, it is better to
stick to the standard terminology.

However it is extremely easy to detect that 'modulo reduction' and
to signal or return the effect of an overflow (in unsigned
arithmetic). Signed is another matter.

 

[Richard Heathfield]

Bart said:

So the reason why the following program produces
some 700 million on a 32-bit system instead of 5 billion is nothing to
do with overflow of A+B? It 'wraps' instead?

Since unsigned types can't overflow, the behaviour of your program cannot
be due to overflow of unsigned types as far as the rules of C are
concerned...

#include <stdio.h>

void main()

....but this line means that your program's behaviour is not governed by the
rules of C.

 

[Ben Bacarisse]

That's interesting. So the reason why the following program produces
some 700 million on a 32-bit system instead of 5 billion is nothing to
do with overflow of A+B? It 'wraps' instead?

It's a matter of terminology, nothing else. The C standard wants to
keep the term "overflow" for those bad cases where the result does not
fit and a signal might have to be raised.

C's arithmetic on unsigned types is arithmetic modulo a power of 2
(determined by the number of values bits in the particular type) and
thus the result always fits. Nothin bad can happen. I don't think of
it as wrapping, I just think of it as modulo arithmetic.

The closer you are to people who the C standard for fun, the more
likely it is that you will be told that unsigned arithmetic can not
overflow. Return to the water-cooler, and you can probably talk about
unsigned overflow without any confusion.

 

[Philip Potter]

Bart said:



Since unsigned types can't overflow, the behaviour of your program cannot
be due to overflow of unsigned types as far as the rules of C are
concerned...


...but this line means that your program's behaviour is not governed by the
rules of C.

Except in the unlikely case that his implementation specifies void
main() as an acceptable prototype.