La forma más eficiente de implementar una función de potencia basada en enteros pow (int, int)

¿Cuál es la forma más eficiente de elevar un número entero a la potencia de otro entero en C?

// 2^3 pow(2,3) == 8 // 5^5 pow(5,5) == 3125 

Exponenciación por cuadratura.

 int ipow(int base, int exp) { int result = 1; for (;;) { if (exp & 1) result *= base; exp >>= 1; if (!exp) break; base *= base; } return result; } 

Este es el método estándar para realizar la exponenciación modular para grandes cantidades en criptografía asimétrica.

Tenga en cuenta que exponenciación por cuadratura no es el método más óptimo. Probablemente sea lo mejor que puede hacer como método general que funciona para todos los valores de exponente, pero para un valor de exponente específico puede haber una secuencia mejor que necesita menos multiplicaciones.

Por ejemplo, si quiere calcular x ^ 15, el método de exponenciación por cuadratura le dará:

 x^15 = (x^7)*(x^7)*xx^7 = (x^3)*(x^3)*xx^3 = x*x*x 

Este es un total de 6 multiplicaciones.

Resulta que esto se puede hacer usando “solo” 5 multiplicaciones a través de la exponenciación de la cadena de adición .

 n*n = n^2 n^2*n = n^3 n^3*n^3 = n^6 n^6*n^6 = n^12 n^12*n^3 = n^15 

No hay algoritmos eficientes para encontrar esta secuencia óptima de multiplicaciones. De la Wikipedia :

El problema de encontrar la cadena de adición más corta no puede resolverse mediante progtwigción dinámica, porque no satisface la suposición de una subestructura óptima. Es decir, no es suficiente descomponer la potencia en potencias más pequeñas, cada una de las cuales se calcula mínimamente, ya que las cadenas de sum para las potencias menores pueden estar relacionadas (para compartir cálculos). Por ejemplo, en la cadena de adición más corta para a¹⁵ arriba, el subproblema para a⁶ debe calcularse como (a³) ² dado que a³ se reutiliza (en oposición a, digamos, a⁶ = a² (a²) ², que también requiere tres multiplicaciones )

Si necesita boost 2 a una potencia. La forma más rápida de hacerlo es cambiar el bit por la potencia.

 2 ** 3 == 1 << 3 == 8 2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte) 

Este es el método en Java

 private int ipow(int base, int exp) { int result = 1; while (exp != 0) { if ((exp & 1) == 1) result *= base; exp >>= 1; base *= base; } return result; } 
 int pow( int base, int exponent) { // Does not work for negative exponents. (But that would be leaving the range of int) if (exponent == 0) return 1; // base case; int temp = pow(base, exponent/2); if (exponent % 2 == 0) return temp * temp; else return (base * temp * temp); } 

Si desea obtener el valor de un entero para 2 elevado al poder de algo, siempre es mejor usar la opción de cambio:

pow(2,5) puede ser reemplazado por 1<<5

Esto es mucho más eficiente.

Un caso extremadamente especializado es, cuando se necesita decir 2 ^ (- x a la y), donde x, por supuesto es negativo e y es demasiado grande para hacer cambios en un int. Todavía puedes hacer 2 ^ x en tiempo constante atornillando con un flotador.

 struct IeeeFloat { unsigned int base : 23; unsigned int exponent : 8; unsigned int signBit : 1; }; union IeeeFloatUnion { IeeeFloat brokenOut; float f; }; inline float twoToThe(char exponent) { // notice how the range checking is already done on the exponent var static IeeeFloatUnion u; uf = 2.0; // Change the exponent part of the float u.brokenOut.exponent += (exponent - 1); return (uf); } 

Puedes obtener más poderes de 2 usando un doble como tipo de base. (Muchas gracias a los comentaristas por ayudarnos a cuadrar esta publicación).

También existe la posibilidad de que al aprender más sobre los flotadores IEEE , otros casos especiales de exponenciación se presenten.

Solo como un seguimiento de los comentarios sobre la eficiencia de la exponenciación por cuadratura.

La ventaja de ese enfoque es que se ejecuta en tiempo de registro (n). Por ejemplo, si fuera a calcular algo enorme, como x ^ 1048575 (2 ^ 20 – 1), solo tiene que pasar por el circuito 20 veces, no 1 millón + utilizando el enfoque ingenuo.

Además, en términos de complejidad del código, es más simple que tratar de encontrar la secuencia de multiplicaciones más óptima, a sugerencia de la Pramod.

Editar:

Creo que debería aclarar antes de que alguien me etiquete por el potencial de desbordamiento. Este enfoque asume que tienes algún tipo de librería de gran tamaño.

power() funciona para Integers

 int power(int base, unsigned int exp){ if (exp == 0) return 1; int temp = power(base, exp/2); if (exp%2 == 0) return temp*temp; else return base*temp*temp; } 

Complejidad = O (log (exp))

power() funciona para la exp negativa y la base flotante .

 float power(float base, int exp) { if( exp == 0) return 1; float temp = power(base, exp/2); if (exp%2 == 0) return temp*temp; else { if(exp > 0) return base*temp*temp; else return (temp*temp)/base; //negative exponent computation } } 

Complejidad = O (log (exp))

Tarde a la fiesta:

A continuación hay una solución que también trata con y < 0 lo mejor que puede.

  1. Utiliza un resultado de intmax_t para el rango máximo. No hay ninguna disposición para las respuestas que no encajan en intmax_t .
  2. powjii(0, 0) --> 1 que es un resultado común para este caso.
  3. pow(0,negative) , otro resultado indefinido, devuelve INTMAX_MAX

     intmax_t powjii(int x, int y) { if (y < 0) { switch (x) { case 0: return INTMAX_MAX; case 1: return 1; case -1: return y % 2 ? -1 : 1; } return 0; } intmax_t z = 1; intmax_t base = x; for (;;) { if (y % 2) { z *= base; } y /= 2; if (y == 0) { break; } base *= base; } return z; } 

Este código usa un bucle for(;;) siempre for(;;) para evitar la base *= base final base *= base común en otras soluciones en bucle. Esa multiplicación es 1) no necesaria y 2) podría ser un desbordamiento int*int que es UB.

Una implementación más (en Java). Puede que no sea la solución más eficiente, pero el número de iteraciones es el mismo que el de la solución exponencial.

 public static long pow(long base, long exp){ if(exp ==0){ return 1; } if(exp ==1){ return base; } if(exp % 2 == 0){ long half = pow(base, exp/2); return half * half; }else{ long half = pow(base, (exp -1)/2); return base * half * half; } } 

solución más genérica teniendo en cuenta el exponenet negativo

 private static int pow(int base, int exponent) { int result = 1; if (exponent == 0) return result; // base case; if (exponent < 0) return 1 / pow(base, -exponent); int temp = pow(base, exponent / 2); if (exponent % 2 == 0) return temp * temp; else return (base * temp * temp); } 

Implementé un algoritmo que memoriza todos los poderes calculados y luego los usa cuando es necesario. Entonces, por ejemplo, x ^ 13 es igual a (x ^ 2) ^ 2 ^ 2 * x ^ 2 ^ 2 * x donde x ^ 2 ^ 2 se toma de la tabla en lugar de calcularlo una vez más. El número de multiplicación necesario es Ceil (Log n)

 public static int Power(int base, int exp) { int tab[] = new int[exp + 1]; tab[0] = 1; tab[1] = base; return Power(base, exp, tab); } public static int Power(int base, int exp, int tab[]) { if(exp == 0) return 1; if(exp == 1) return base; int i = 1; while(i < exp/2) { if(tab[2 * i] <= 0) tab[2 * i] = tab[i] * tab[i]; i = i << 1; } if(exp <= i) return tab[i]; else return tab[i] * Power(base, exp - i, tab); } 

Yo uso recursivo, si el exp es par, 5 ^ 10 = 25 ^ 5.

 int pow(float base,float exp){ if (exp==0)return 1; else if(exp>0&&exp%2==0){ return pow(base*base,exp/2); }else if (exp>0&&exp%2!=0){ return base*pow(base,exp-1); } } 

Mi caso es un poco diferente, estoy tratando de crear una máscara a partir de un poder, pero pensé que compartiría la solución que encontré de todos modos.

Obviamente, solo funciona para potencias de 2.

 Mask1 = 1 << (Exponent - 1); Mask2 = Mask1 - 1; return Mask1 + Mask2; 

En caso de que conozca el exponente (y es un número entero) en tiempo de comstackción, puede usar plantillas para desenrollar el ciclo. Esto se puede hacer más eficiente, pero quería demostrar el principio básico aquí:

 #include  template unsigned long inline exp_unroll(unsigned base) { return base * exp_unroll(base); } 

Terminamos la recursión usando una especialización de plantilla:

 template<> unsigned long inline exp_unroll<1>(unsigned base) { return base; } 

El exponente necesita ser conocido en tiempo de ejecución,

 int main(int argc, char * argv[]) { std::cout << argv[1] <<"**5= " << exp_unroll<5>(atoi(argv[1])) << ;std::endl; } 

Ignorando el caso especial de 2 elevado a potencia, la forma más eficiente será la iteración simple.

 int pow(int base, int pow) { int res = 1; for(int i=pow; i 

EDITAR: Como se ha señalado, esta no es la forma más eficiente ... siempre y cuando se defina la eficiencia como ciclos de CPU, que creo que es lo suficientemente justo.