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

• Algoritmi di moltiplicazione
• Algoritmi di ordinamento
• Ricerca dicotomica