长数组的精确和

Question

为了获得 long[] 的准确总和，我使用了以下代码段。

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));
}

通过处理分成两半的数字并最终合并部分和，它工作得很好。令人惊讶的是，这个方法也有效：

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));
}

我不相信fastestSum应该按原样工作。我相信它可以工作，但在最后一步必须做更多的事情。但是，它通过了我所有的测试（包括大型随机测试）。所以我想问：有人能证明它有效或找到反例吗？

Answer 1

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

Answer 2

这似乎有效。鉴于我的测试没有发现我的普通版本的问题，我不确定它是否正确。欢迎各位大侠分析：

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));
}

它可能比正常版本快 30%。

长数组的精确和

Exact sum of a long array

java

sum

integer-arithmetic