Determine which sum is larger

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

  1. Peter Ammon

    Peter Ammon Guest

    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
    #1
    1. Advertisements

  2. 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
    #2
    1. Advertisements

  3. Peter Ammon

    Catsby Guest

    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
    #3
  4. 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
    #4
  5. 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
    #5
  6. Peter Ammon

    Thad Smith Guest

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

    Shouldn't the result of a comparison have three states?
     
    Thad Smith, Nov 19, 2007
    #6
  7. Peter Ammon

    Eric Sosman Guest

    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.
     
    Eric Sosman, Nov 19, 2007
    #7
  8. 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
    #8
  9. Peter Ammon

    Chris Torek Guest

    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.)
     
    Chris Torek, Nov 19, 2007
    #9
  10. Peter Ammon

    Eric Sosman Guest

    My version could also be improved (although not shortened)
    by corretcing the typo ...
     
    Eric Sosman, Nov 20, 2007
    #10
  11. 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
    #11
  12. Er... no! Good catch.
     
    Philip Potter, Nov 20, 2007
    #12
  13. Peter Ammon

    Tor Rustad Guest

    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).
     
    Tor Rustad, Nov 21, 2007
    #13
  14. Peter Ammon

    Bart Guest

    Are you sure? That would be a very useful property.
     
    Bart, Nov 21, 2007
    #14
  15. 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
    #15
  16. Peter Ammon

    Bart Guest

    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
    #16
  17. Peter Ammon

    CBFalconer Guest

    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
    #17
  18. 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
    #18
  19. 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.
     
    Ben Bacarisse, Nov 21, 2007
    #19
  20. Except in the unlikely case that his implementation specifies void
    main() as an acceptable prototype.
     
    Philip Potter, Nov 21, 2007
    #20
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.