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.

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:

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

Implementazione in Pascal – non ricorsivo

La funzione lavora con base razionale e esponente intero relativo (ad esempio ${\left({3 \over 2}\right)}^{2}$ 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;

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)

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

Implementazione in Java - ricorsiva

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

Implementazione in Lisp - ricorsiva

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

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

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

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

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

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