Efficienza del mio metodo di alimentazione Java?

Question

Così sono andato in un colloquio di lavoro e mi hanno chiesto di scrivere un metodo di alimentazione rapido calcolo su un bordo bianco e questo è ciò che ho messo lì

public static double pow(double base, double power) { 
    double result = 1.0; 
    for(double x = 0; x < power; x++) { 
     result = result * base; 
    } 

    return result; 
} 

Questo ha funzionato e sono stati soddisfatti con esso, ma poi ho continuato a chiedermi come avrei potuto renderlo più efficiente e non ho avuto risposta. Quindi la mia domanda è: puoi essere più efficiente di questo o è solo una domanda per farmi sudare un po '? Sto pensando che potrebbe esserci qualche soluzione di trasferimento di bit diretta ma non sono esattamente sicuro, penso che si applicherebbe solo per le potenze di 2? Qualche idea?

* EDIT Scusa se ho dimenticato di dire che che la firma metodo è stato dato a me (i doppi come input) e mi è stato detto che non potevo utilizzare librerie matematiche built-in.

Answer 1

http://en.wikipedia.org/wiki/Exponentiation_by_squaring Il "metodo di base" è O (log n), al contrario di questo algoritmo O (n). (Guava ha un'implementazione non ricorsiva.)

Inoltre, il parametro di alimentazione dovrebbe essere quasi certamente un int. (Se davvero si vuole implementare un algoritmo per aumentare i numeri di poteri non interi, si sta andando ad avere bisogno di molto di più per la matematica.)

Answer 2

Moltiplicando la risposta contro se stessa e altri multipli possono produrre determinati con differenti poteri, che ti possono avvicinare alla soluzione più velocemente. Il wiki Louis fornisce è buono. Se si desidera una spiegazione generica, prendere in considerazione:

2^1 * 2^1 = 2^2 
2^2 * 2^2 = 2^4 
2^4 * 2^4 = 2^8 
... 

Questa grande opera per potenze di due. Tuttavia ho trovato divertente giocare con non poteri di due. Quindi se volessi 2^13 come potrei farlo?

2^1 * 2^1 = 2^2 
2^1 * 2^2 = 2^3 
2^3 * 2^3 = 2^6 
2^6 * 2^6 = 2^12 
2^12 * 2^1 = 2^13 

L'esempio precedente mostra che non è necessario giocare solo con i quadrati. Se giochi con questo, con vari poteri, scoprirai che a volte puoi fare di meglio che usare solo i poteri di 2 ... è un divertente problema di matematica con cui giocare.

Answer 3

Pensando fuori dagli schemi un po ', c'è generalmente un compromesso tra memoria e velocità. C'è il concetto di memoization.

È possibile aggiungere una doppia [] [] cache statica che memorizza il risultato per qualsiasi valore specifico.

Qualcosa di simile:

// look for the value in the cache, if it is there return it. 

for(double x = 0; x < power; x++) { 
    result = result * base; 
    // store result in the cache 
} 

Questo potrebbe funzionare, ma avrebbe usato un sacco di memoria.