La forma más eficiente de implementar una función de potencia basada en números enteros pow(int, int)
¿Cuál es la forma más eficiente de elevar un número entero a la potencia de otro número entero en C?
// 2^3
pow(2,3) == 8
// 5^5
pow(5,5) == 3125
Exponenciación al cuadrado.
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 una exponenciación modular para números enormes en criptografía asimétrica.
Tenga en cuenta que la exponenciación al cuadrado no es el método más óptimo. Probablemente sea lo mejor que puedes hacer como método general que funciona para todos los valores de exponente, pero para un valor de exponente específico podría haber una secuencia mejor que necesite menos multiplicaciones.
Por ejemplo, si quieres calcular x^15, el método de exponenciación elevando al cuadrado te 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 mediante exponenciación en cadena de suma .
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 existen algoritmos eficientes para encontrar esta secuencia óptima de multiplicaciones. De Wikipedia :
El problema de encontrar la cadena de suma más corta no puede resolverse mediante programación dinámica porque 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 suma para las potencias más pequeñas pueden estar relacionadas (para compartir cálculos). Por ejemplo, en la cadena de suma más corta para a¹⁵ anterior, el subproblema para a⁶ debe calcularse como (a³)² ya que a³ se reutiliza (a diferencia de, digamos, a⁶ = a²(a²)², que también requiere tres multiplicaciones ).
Si necesitas elevar 2 a una potencia. La forma más rápida de hacerlo es cambiar de bits mediante la potencia.
2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)
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;
}
