java.math.BigInteger pow (esponente) domanda

StackOverflow https://stackoverflow.com/questions/2932869

  •  05-10-2019
  •  | 
  •  

Domanda

Ho fatto alcuni test metodo su pow (esponente). Purtroppo, le mie abilità matematiche sono abbastanza forte per gestire il seguente problema.

Sto usando questo codice: 

BigInteger.valueOf(2).pow(var);

Risultati:

  • var | tempo in ms
  • 2000000 | 11450
  • 2500000 | 12471
  • 3000000 | 22379
  • 3500000 | 32147
  • 4000000 | 46270
  • 4500000 | 31459
  • 5000000 | 49922

Vedi? 2.500.000 esponente è calcolato quasi veloce come 2.000.000. 4.500.000 è calcolato molto più veloce quindi 4.000.000.

Perché?

Per dare qualche aiuto, ecco l'implementazione originale di BigInteger.pow (esponente): 

 public BigInteger pow(int exponent) {
    if (exponent < 0)
        throw new ArithmeticException("Negative exponent");
    if (signum==0)
        return (exponent==0 ? ONE : this);

    // Perform exponentiation using repeated squaring trick
        int newSign = (signum<0 && (exponent&1)==1 ? -1 : 1);
    int[] baseToPow2 = this.mag;
        int[] result = {1};

    while (exponent != 0) {
        if ((exponent & 1)==1) {
        result = multiplyToLen(result, result.length, 
                                       baseToPow2, baseToPow2.length, null);
        result = trustedStripLeadingZeroInts(result);
        }
        if ((exponent >>>= 1) != 0) {
                baseToPow2 = squareToLen(baseToPow2, baseToPow2.length, null);
        baseToPow2 = trustedStripLeadingZeroInts(baseToPow2);
        }
    }
    return new BigInteger(result, newSign);
    }
È stato utile?

Soluzione

Gli usi ripetuti algoritmo squadratura (squareToLen) e moltiplicazione (multiplyToLen). Il tempo per queste operazioni per l'esecuzione dipende dalla dimensione dei numeri coinvolti. Le moltiplicazioni dei grandi numeri verso la fine del calcolo sono molto più costosi di quelli in partenza.

La moltiplicazione avviene solo quando questa condizione è vera: ((exponent & 1)==1). Il numero di operazioni quadrati dipende dal numero di bit del numero (escluse zeri), ma una moltiplicazione è necessaria solo per i bit impostati a 1. È facile vedere le operazioni necessarie osservando il binario rappresentazione del numero: 

2000000: 0000111101000010010000000
2500000: 0001001100010010110100000
3000000: 0001011011100011011000000
3500000: 0001101010110011111100000
4000000: 0001111010000100100000000
4500000: 0010001001010101000100000
5000000: 0010011000100101101000000

Si noti che 2.5M e 4.5M sono fortunati in quanto hanno un minor numero di bit ad alta impostati dei numeri che li circondano. La prossima volta che questo accade è a 8.5M: 

8000000: 0011110100001001000000000
8500000: 0100000011011001100100000
9000000: 0100010010101010001000000

Gli spot dolci sono potenze esatte di 2. 

1048575: 0001111111111111111111111 // 16408 ms
1048576: 0010000000000000000000000 //  6209 ms

Altri suggerimenti

Solo una supposizione:

l'esponente è gestita a poco a poco, e se il bit meno significativo è 1 lavoro supplementare è fatto.

Se L è il numero di bit nella esponente e AL numero di bit che sono 1 e t1 il tempo per elaborare la parte comune e t2 il tempo di elaborazione supplementare quando la LSBit è 1

quindi il tempo di esecuzione sarebbe

L t1 + A T2

o il tempo dipende dal numero di 1 nella rappresentazione binaria.

ora a scrivere un piccolo programma per verificare la mia teoria ...

Non sono sicuro di quante volte hai eseguito il timing. Come alcuni dei commentatori hanno sottolineato, è necessario operazioni di tempo molte, molte volte per ottenere buoni risultati (e possono ancora essere sbagliato).

Supponendo di aver le cose a tempo bene, ricordate che ci sono un sacco di scorciatoie che possono essere adottate in matematica. Non è necessario fare le operazioni di 5 * 5 * 5 * 5 * 5 * 5 per calcolare 5 ^ 6.

Ecco un modo per farlo molto più rapidamente. http://en.wikipedia.org/wiki/Exponentiation_by_squaring

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top