Ridicare la putere în timp logaritmic

Doresc să pun în evidenţă o modalitate simplă de calcul a valorii expresiei xn, unde x este un număr real, iar n este număr natural. O primă variantă, cea care se învaţă odată cu instrucţiunile repetitive, este bazată pe relaţia:

xn = x * x * ... * x, adică înmulţire repetată de n ori a lui x

Funcţia care realizează acest lucru este:

double Putere(double x, int n) { double p = x ; for (int i = 1 ; i < n ; i++) p *= x ; return p ; }

Există însă o soluţie mai rapidă, bazată pe relaţiile următoare:

• dacă n este impar, atunci xn = xn-1 * x
• dacă n este par, atunci xn = xn/2 * xn/2

În acest fel, numărul total de operaţii de înmulţire va scădea semnificativ. De exemplu pentru calculul lui x13 se vor efectua numai 5 înmulţiri, iar x100 doar 8 înmulţiri. Funcţia este următoarea:

double PutereLogaritmic(double x, int n) { double p = 1 ; while (n > 0) { if (n & 1) // n este impar { p *= x; n-- ; } x = x * x ; n >>= 1 ; // sau n = n / 2 } return p ; }