एक लंबी सरणी

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% तेज है।