# Determine which sum is larger

Discussion in 'C Programming' started by Peter Ammon, Nov 19, 2007.

1. ### Peter AmmonGuest

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

Peter Ammon, Nov 19, 2007

2. ### Richard HeathfieldGuest

Peter Ammon said:
Hi Peter, ltns.
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.
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.

Richard Heathfield, Nov 19, 2007

3. ### CatsbyGuest

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

Catsby, Nov 19, 2007
4. ### Philip PotterGuest

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.

Philip Potter, Nov 19, 2007
5. ### Richard HeathfieldGuest

Philip Potter said:
See, that's why we have Usenet - so one person can kickstart an idea, and
someone else can carry it on...
....and then consign it to the dustbin of history.

Richard Heathfield, Nov 19, 2007

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

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

7. ### Eric SosmanGuest

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:

unsigned long long abhi, cdhi;
abhi = (a >> 1) + (b >> 1);
cdhi = (c >> 1) + (c >> 1);
if (abhi > cdhi)
else if (abhi < cdhi)
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)
else if (ablo < cdlo)
else
}

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.

Eric Sosman, Nov 19, 2007
8. ### Philip PotterGuest

Exactly the same as for 4+4 compared with 4+4.
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.

Philip Potter, Nov 19, 2007
9. ### Chris TorekGuest

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;

/*
* 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

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

Chris Torek, Nov 19, 2007
10. ### Eric SosmanGuest

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

Eric Sosman, Nov 20, 2007
11. ### Ralf DamaschkeGuest

OK, right so far (assuming the first expression corresponds
to the first function argument).
So you would accept the function's claim "4+4 > 5+3"?

-- Ralf

Ralf Damaschke, Nov 20, 2007
12. ### Philip PotterGuest

Er... no! Good catch.

Philip Potter, Nov 20, 2007

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).

14. ### BartGuest

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

Bart, Nov 21, 2007
15. ### Ben BacarisseGuest

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.

Ben Bacarisse, Nov 21, 2007
16. ### BartGuest

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

Bart, Nov 21, 2007
17. ### CBFalconerGuest

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.

CBFalconer, Nov 21, 2007
18. ### Richard HeathfieldGuest

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.

Richard Heathfield, Nov 21, 2007
19. ### Ben BacarisseGuest

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
unsigned overflow without any confusion.

Ben Bacarisse, Nov 21, 2007
20. ### Philip PotterGuest

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

Philip Potter, Nov 21, 2007