Exact sum of a long array

Question

In order to get the exact sum of a long[] I'm using the following snippet.

public static BigInteger sum(long[] a) {
    long low = 0;
    long high = 0;
    for (final long x : a) {
        low += (x & 0xFFFF_FFFFL);
        high += (x >> 32);
    }
    return BigInteger.valueOf(high).shiftLeft(32).add(BigInteger.valueOf(low));
}

It works fine by processing the numbers split in two halves and finally combining the partial sums. Surprisingly, this method works too:

public static BigInteger fastestSum(long[] a) {
    long low = 0;
    long high = 0;
    for (final long x : a) {
        low += x;
        high += (x >> 32);
    }
    // We know that low has the lowest 64 bits of the exact sum.
    // We also know that BigInteger.valueOf(high).shiftLeft(32) differs from the exact sum by less than 2**63.
    // So the upper half of high is off by at most one.
    high >>= 32;
    if (low < 0) ++high; // Surprisingly, this is enough to fix it.
    return BigInteger.valueOf(high).shiftLeft(64).add(BigInteger.valueOf(low));
}

I don't believe that the fastestSum should work as is. I believe that it can work, but that something more has to be done in the final step. However, it passes all my tests (including large random tests). So I'm asking: Can someone prove that it works or find a counterexample?

It should work, but to my knowledge, you are depending on undefined behaviour. Most importantly [**The integer operators do not indicate overflow or underflow in any way**](https://docs.oracle.com/javase/specs/jls/se8/html/jls-4.html#jls-4.2.2#jls-4.2.2). — dhke, Jun 07 '15 at 17:01
@dhke, perhaps you're confusing Java with C. JLS 15.18.2 says, in part, "If an integer addition overflows, then the result is the low-order bits of the mathematical sum as represented in some sufficiently large two's-complement format. If overflow occurs, then the sign of the result is not the same as the sign of the mathematical sum of the two operand values." The Java language has little, if any, undefined behavior, at least for single-threaded programs. — John Bollinger, Jun 07 '15 at 17:06
@JohnBollinger Agreed. As dhke writes, there's no overflow indication, but I'm using none. And the result is correct mod 2**64, so the least 64 bits are right. I'm only concerned about the higher 32 bits. — maaartinus, Jun 07 '15 at 17:10
@JohnBollinger Nice to know that, I simply missed that part of the spec. — dhke, Jun 07 '15 at 17:11
Your algorithm probably makes use of the fact that you cannot define an array of *2^64* elements or more. — Willem Van Onsem, Jun 07 '15 at 17:11
@CommuSoft, yes, in fact the assumptions rely on the fact that the maximum length of a Java array is `Integer.MAX_VALUE`, which is one less than 2^31. — John Bollinger, Jun 07 '15 at 17:12

score 4 · Accepted Answer · answered Jun 07 '15 at 18:14

4

fastestSum(new long[]{+1, -1})  => -18446744073709551616

answered Jun 07 '15 at 18:14

ZhongYu

19,446
5
33
61

Is that an answer? :) – Dmitry Ginzburg Jun 07 '15 at 18:19
@DmitryGinzburg Unbelievable, but true! And my "smart" test cases missed it and so did one million random tests! Actually, I should accept this answer, but this sounds boring and I'm gonna ask how to fix it instead. – maaartinus Jun 07 '15 at 18:20
@bayou.io probes that the method doesn't work.. although i think that is interesting algorithm out there, this answer, answer your question. – Victor Jun 07 '15 at 20:59
juajuajuauja! Good point! But people who looks for a correct answer, need to refer to this answer! – Victor Jun 08 '15 at 21:44

score 1 · Answer 2 · answered Jun 07 '15 at 20:53

This seems to work. Given that my tests missed the problem with my trivial version, I'm not sure if it's correct. Whoever wants to analyze this is welcome:

public static BigInteger fastestSum(long[] a) {
    long low = 0;
    long control = 0;
    for (final long x : a) {
        low += x;
        control += (x >> 32);
    }
    /*
     We know that low has the lowest 64 bits of the exact sum.
     We also know that 2**64 * control differs from the exact sum by less than 2**63.
     It can't be bigger than the exact sum as the signed shift always rounds towards negative infinity.
     So the upper half of control is either right or must be incremented by one.
     */
    final long x = control & 0xFFFF_FFFFL;
    final long y = (low >> 32);
    long high = (control >> 32);
    if (x - y > 1L << 31) ++high;
    return BigInteger.valueOf(high).shiftLeft(64).add(BigInteger.valueOf(low));
}

It's maybe 30% faster than the sane version.

Exact sum of a long array

2 Answers2

Linked