Complejidad del tiempo de la potencia()

Question

Implementé esta función power() que toma dos argumentos a y b y calcula un ^b.

typedef long long int LL; 

LL power(int a,int b) 
{ 
    int i = 1; 
    LL pow = 1; 
    for(; i <= b ; ++i) 
    pow *= a; 
    return pow; 
} 

Dado: un ^b cae en el rango de long long int.
Problema: ¿Cómo puedo reducir la complejidad del tiempo de mi algoritmo?

Answer 1

Exponencialización por cuadratura.

una implementación no recursiva

LL power(int a, int b) 
{ 
    LL pow = 1; 
    while (b) 
    { 
     if (b & 1) 
     { 
      pow = pow * a; 
      --b; 
     } 
     a = a*a; 
     b = b/2; 
    } 
    return pow; 
} 

Este algoritmo requiere registro b squarings y como máximo registro b multiplicaciones.

El tiempo de ejecución es O (log b)

---

Answer 2

Uso Exponentiation by squaring

Answer 3

que sugeriría: Utilice la función pow() si realmente necesita una función más rápido (con doble largo) o piensa en tu tarea por ti mismo.

Para precisión arbitraria: Ver el GMP lib http://gmplib.org/manual/Integer-Exponentiation.html#Integer-Exponentiation

Answer 4

exponenciación binaria no da el mínimo número de multiplicaciones en todos los casos. Busque "cadenas de adición", "cadenas de Brauer", "cadenas de Hansen" y "conjetura de Scholz".

Answer 5

Utilice la exponenciación por cuadrados. Es decir, si necesitamos a^b, comprobamos si b es par, si b es par, encontramos (a^2)^(b/2), de lo contrario, encontramos a*((a^2)^(b/2)). Puede que este no sea el mejor algoritmo, pero es mejor que el algoritmo lineal.

int Power(int a, int b) 
{ 
    if (b>0) 
    { 
     if (b==0) 
      return 1; 
     if (a==0) 
      return 0; 
     if (b%2==0) { 
      return Power(a*a, b/2); 
     } 
     else if (b%2==1) 
     { 
     return a*Power(a*a,b/2); 
     } 
    } 
    return 0; 
} 

Answer 6

Aquí está la implementación recursiva del código Java de 2 a la potencia de n con O (log n) la complejidad utilizando Exponentiation by squaring

int ans=1; 
public int myTwoPower(int n){ 
    if(n<=0) 
     return 1; 

    if(n%2 !=0){    
     return myTwoPower(n-1)*2; 
    } 
    else{ 
     ans = myTwoPower(n/2); 
     return ans * ans; 
    } 
}