Implementazioni di algoritmi/Elevazione a potenza
In matematica l'elevamento a potenza è un'operazione che associa ad una coppia di numeri naturali a e n – detti rispettivamente base ed esponente – il numero dato dalla moltiplicazione di a per sé stesso iterata per n volte se n è maggiore di 1, restituisce a stesso se n è uguale a 1 e restituisce 1 se n è uguale a 0. Questa funzione non è definita se la base e l'esponente valgono entrambi 0.
unsigned int pow_n(int a,unsigned int ex) {
if(ex==0) {
return 1 ; } ;
if(ex==1) {
return a; }
else{
return a*(pow_n(a,(ex-1)));} ;
return a ;
} ;
Tuttavia la versione ricorsiva presenta alcune limitazioni per quanto riguarda i linguaggi C-like, quindi:
unsigned int pow_n(int a,unsigned int ex) {
if(ex==0) {
return 1 ; } ;
if(ex==1) {
return a; } ;
int c=a ;
for(ex;ex!=1;ex--) {
a=a*c ; } ;
return a ;
} ;
La funzione lavora con base razionale e esponente intero relativo (ad esempio o ).
function potenza (b: real; e: integer): real;
var r: real; i : integer;
begin
if (b=0) and (e=0) then {verifica il caso 0^0 }
writeln('Errore: l''espressione non ha significato')
else
begin
r := 1; {valore di partenza}
{calcola b^abs(e) }
for i := 1 to abs(e) do
r := r * b;
{inverte il risultato se necessario}
if e < 0 then
r := 1/r;
{restituisce il valore}
potenza := r;
end;
end;
La funzione presuppone che l'esponente sia un numero naturale.
def potr(base, esp):
if base==0:
if esp==0:
return "err"
else:
return 0
else:
return _potr(base, esp)
def _potr(base, esp):
if esp == 0:
return 1
return base*_potr(base, esp-1)
La funzione presuppone che l'esponente sia un numero naturale.
def pot(base, esp):
if base == 0:
if esp == 0:
return "err"
else:
return 0
else:
result = 1
while esp:
result *= base
esp -= 1
return result
La funzione presuppone che l'esponente sia un numero naturale.
public static long pow_n(int a, float ex)
{
if (ex == 0)
{
return 1;
}
else if (ex == 1)
{
return a;
}
else
{
return a * pow_n(a,ex-1);
}
}
La funzione presuppone che l'esponente sia un numero naturale.
; Interprete: GNU CLISP 2.49
(defun Pot(a b)
(if (eq b 0) 1
(* a (Pot a (- b 1))))
)
Algoritmi con complessità minore
modificaOltre a queste versioni semplici esistono anche modi per diminuire la complessità operazionale come ad esempio l'algoritmo di elevazione a potenza binario o quello, probabilmente il migliore per le operazioni molto complesse, che fa uso della ricerca della catena di addizione più corta (vedi addition-chain exponentiation).
unsigned int sq_pow_n(int a,unsigned int ex) {
if(ex==0)
return 1;
if(ex==1)
return a;
if(ex%2==0)
return sq_pow_n(a*a,(ex/2));
else
return a*(sq_pow_n(a*a,(ex/2)));
return 0;
}
long pow(long x, long n)
{
long result = 1;
while ( n ) {
if ( n & 1 ) {
result = result * x;
n = n-1;
}
x = x*x;
n = n/2;
}
return result;
}
def power(x,n)
result = 1
while n.nonzero?
if n[0].nonzero?
result = result * x
n = n-1
end
x = x*x
n = n/2
end
return result
end
def pot2(base, esp):
if base == 0:
if esp == 0:
return "err"
else:
return 0
else:
result = 1
while esp:
if esp&1:
result *= base
esp -= 1
base*=base
esp=esp>>1
return result