Implementazioni di algoritmi/Elevazione a potenza

Wikibooks, manuali e libri di testo liberi.

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.

[modifica] Implementazione in C/C++ – versione ricorsiva

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:

[modifica] Implementazione in C/C++ – versione non ricorsiva

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 ; 
} ;

[modifica] Implementazione in Pascal – non ricorsivo

La funzione lavora con base razionale e esponente intero relativo (ad esempio o 3 ^{− 2}).

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;

[modifica] Implementazione in Python – ricorsiva

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)

[modifica] Implementazione in Python – non ricorsiva

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

[modifica] Algoritmi con complessità minore

Oltre 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).

[modifica] Implementazione in C/C++ - versione ricorsiva

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; 
} ;

[modifica] Implementazione in C - versione non ricorsiva

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;
}

[modifica] Implementazione in Ruby - versione non ricorsiva

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

[modifica] Implementazione in Python - versione non ricorsiva

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
      else:
        base*=base
        esp=esp>>1
    return result