Algoritmi di elevamento a potenza

Template:S 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{array}{cc}{a}^n:=& \underbrace{a\cdot a\cdot a\cdots a}\\ & n\text{ volte}\end{array}$

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{array}{cc}\mathrm{\Theta }(1),& \text{se }n\text{ ≤ 1}\\ T(n/2)+\mathrm{\Theta }(1),& \text{se }n>1\end{array}$.

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

• Template:Cita libro

Voci correlate

• Algoritmi di moltiplicazione
• Algoritmi di ordinamento
• Ricerca dicotomica