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

algorithm math

Question

¿Cuál es la forma más eficiente de aumentar un entero a la potencia de otro entero en C?

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

Answer 1

Aquí está 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;
}

Answer 2

Exposiciónció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 hacer exponenciación modular para grandes números en criptografía asimétrica.

Answer 3

Función power() para trabajar solo para enteros

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

Función power() para trabajar con exp negativa y 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))

Answer 4

He implementado un algoritmo que memoriza todos los poderes computados 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 computarlo 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);
}

Answer 5

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

int pow(int base, int pow) {
int res = 1;
for(int i=pow; i<pow; i++)
res *= base;
return res;
}

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

Answer 6

Mi caso es un poco diferente, estoy tratando de crear una máscara de un poder, pero pensé que iba a compartir 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;

Answer 7

Si conoce el exponente (y es un número entero) en tiempo de compilación, puede usar plantillas para desenrollar el ciclo. Esto puede hacerse más eficiente, pero quería demostrar el principio básico aquí:

#include <iostream>
template<unsigned long N>
unsigned long inline exp_unroll(unsigned base) {
return base * exp_unroll<N-1>(base);
}

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

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

El exponente debe 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;
}

Answer 8

Si desea obtener el valor de un entero para 2 elevado a la potencia 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.

Answer 9

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

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

Answer 10

Solo como seguimiento a los comentarios sobre la eficiencia de la exponenciación por escuadrado.

La ventaja de este enfoque es que se ejecuta en tiempo de registro (n). Por ejemplo, si iba a calcular algo enorme, como x ^ 1048575 (2 ^ 20 - 1), solo tiene que pasar por el bucle 20 veces, no 1 millón o más con el método ingenuo.

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

Editar:

Supongo que debería aclarar antes de que alguien me etiquete por el potencial de desbordamiento. Este enfoque asume que tienes algún tipo de biblioteca enorme.

Answer 11

Solución más genérica considerando 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);
}

Answer 12

Tarde a la fiesta:

A continuación se muestra una solución que también trata con y < 0 lo mejor que pueda.

1. Utiliza un resultado de intmax_t para el rango máximo. No hay provisión para respuestas que no encajen 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 es necesaria y 2) podría ser int*int overflow que es UB.

Answer 13

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

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

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

Esto 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 Wikipedia :

El problema de encontrar la cadena de adición más corta no se puede resolver con la programación dinámica, ya que no satisface el supuesto de 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 adición para las potencias más pequeñas pueden estar relacionadas (para compartir cálculos). Por ejemplo, en la cadena de adición más corta para a¹⁵ anterior, el subproblema para a⁶ debe calcularse como (a³) ², ya que a³ se reutiliza (a diferencia de, por ejemplo, a⁶ = a² (a²) ², que también requiere tres multiplicados ).

Answer 14

Un caso extremadamente especializado es, cuando se necesita decir 2 ^ (- x a la y), donde x, por supuesto, es negativo y y es demasiado grande para hacer un cambio en un int. Aún 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;
u.f = 2.0;
// Change the exponent part of the float
u.brokenOut.exponent += (exponent - 1);
return (u.f);
}

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

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

Answer 15

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

Answer 16

Uso recursivo, si la 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);
}
}

Answer 17

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