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?