somma esatta di un lungo array

Per ottenere la somma esatta di un long[] sto usando il seguente frammento.somma esatta di un lungo array

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

Funziona bene elaborando i numeri divisi in due metà e infine combinando le somme parziali. Sorprendentemente, questo metodo funziona anche:

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

Io Non credono che il fastestSum dovrebbe funzionare come è. Credo che possa funzionare, ma che qualcosa di più deve essere fatto nella fase finale. Tuttavia, passa tutti i miei test (compresi test casuali di grandi dimensioni). Quindi, sto chiedendo: Qualcuno può provare che funziona o trovare un controesempio?

fonte

2015-06-07 maaartinus

Dovrebbe funzionare, ma, a mia conoscenza, si dipende da un comportamento non definito. Soprattutto [** Gli operatori interi non indicano overflow o underflow in alcun modo **] (https://docs.oracle.com/javase/specs/jls/se8/html/jls-4.html#jls-4.2 .2 # JLS-4.2.2). – dhke

@dhke, forse stai confondendo Java con C. JLS 15.18.2 dice, in parte, "Se un'aggiunta integer sovrasta, il risultato sono i bit di ordine inferiore della somma matematica rappresentati in alcuni due sufficientemente grandi -completamento del formato Se si verifica un overflow, il segno del risultato non è uguale al segno della somma matematica dei due valori dell'operando. " Il linguaggio Java ha un comportamento piccolo, se non definito, almeno per i programmi a thread singolo. –

@JohnBollinger Concordato. Come scrive dhke, non ci sono indicazioni di overflow, ma non ne utilizzo. E il risultato è corretto mod 2 ** 64, quindi i minimi 64 bit sono corretti. Sono solo preoccupato per i 32 bit più alti. – maaartinus

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

fonte

2015-06-07 18:14:17 ZhongYu

È una risposta? :) –

@DmitryGinzburg Incredibile, ma vero! E i miei casi di test "intelligenti" lo mancarono e così fece un milione di test casuali! In realtà, dovrei accettare questa risposta, ma suona noioso e chiederò come risolverlo. – maaartinus

@ bayou.io sonda che il metodo non funziona .. anche se penso che sia un algoritmo interessante là fuori, questa risposta, risponde alla tua domanda. – Victor

Questo sembra funzionare. Dato che i miei test hanno mancato il problema con la mia versione banale, non sono sicuro che sia corretto. Chiunque voglia analizzare questo è il benvenuto:

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

È forse il 30% più veloce rispetto alla versione sana.

fonte

2015-06-07 20:53:00 maaartinus

risposta

Problemi correlati