Algoritmi di elevamento a potenza

In informatica, per algoritmi di elevamento a potenza si intende la serie di passaggi elementari che una generica CPU deve compiere per eseguire l'operazione di elevamento a potenza.

Pseudo-codice e complessità

Algoritmo banale

L'algoritmo di elevamento a potenza più semplice si basa sulla definizione matematica dell'operazione di potenza:

${\begin{matrix}a^{n}:=&\underbrace {a\cdot a\cdot a\cdots a} \\&n{\mbox{ volte}}\end{matrix}}$

Di seguito la versione iterativa dell'algoritmo:

 function POWER(base, exponent)
     result = 1;
     for i = 1 to exponent
       result = result * base;

Tale algoritmo ha complessità $O(n)$ , poiché vengono effettuate $n$ moltiplicazioni.

Algoritmo ottimo

Vediamo ora un algoritmo più efficiente:

 function POWER(base, exponent)
     if exponent == 0 
       return 1;
     if exponent == 1
       return base;
     if (exponent % 2) == 0
       return POWER(base * base, exponent/2);
     else
       return base * POWER(base * base, exponent/2);
 return 0;

L'equazione di ricorrenza è la seguente: $T(n)={\begin{cases}{\Theta }(1),&{\mbox{se }}n{\mbox{ ≤ 1}}\\T(n/2)+{\Theta }(1),&{\mbox{se }}n>1\end{cases}}$ .

Poiché essa è del tipo $T(n)=aT\left({\frac {n}{b}}\right)+f(n)$ , può essere risolta utilizzando il metodo dell'esperto.

Il costo in tempo di questo algoritmo è $O(\log n)$ , quindi asintoticamente migliore rispetto al precedente.

Bibliografia

Thomas Cormen, Charles E. Leiserson, Ronald Rivest, Introduction, in Introduction to Algorithms, 2ª ed., Cambridge, Massachusetts, The MIT Press, 1998.

Voci correlate

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica