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

Question 1

¿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

Question 2

Tenga en cuenta que exponenciación al cuadrado 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 necesite menos multiplicaciones.

Por ejemplo, si desea calcular x^15, el método de exponenciación al cuadrado 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 exponenciación de la 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. Desde 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 ).

Question 3

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

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

Question 4

Un caso extremadamente especializado es, cuando necesitas decir 2^(-x a la y), donde x, por supuesto, es negativa 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;
    u.f = 2.0;
    // Change the exponent part of the float
    u.brokenOut.exponent += (exponent - 1);
    return (u.f);
}

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

También existe la posibilidad de que aprender más sobre flotadores IEEEpodrían presentarse otros casos especiales de exponenciación.

Question 5

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

¿Ha sido útil esta solución?