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 número 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 hacer exponenciación modular para grandes cantidades 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 puede 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 necesita 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 la 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 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 puede resolverse mediante programación dinámica, ya que no satisface el supuesto 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 adición 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 (en oposición a, por ejemplo, a⁶ = a² (a²) ², que también requiere tres multiplicados )

Si necesitas subir 2 a una potencia. La forma más rápida de hacerlo es cambiar un poco el poder.

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

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 a la potencia de algo, siempre es mejor usar la opción shift:

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

Esto es mucho más eficiente.

power()función 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))

power()función para trabajar para exp negativo 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))

Un caso extremadamente especializado es, cuando necesita decir 2 ^ (- x a la y), donde x, por supuesto, es negativo e y es demasiado grande para hacer un cambio 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);
}

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

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

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

La ventaja de este enfoque es que se ejecuta en tiempo log (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 + usando el enfoque ingenuo.

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

Editar:

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

Tarde a la fiesta:

A continuación se muestra una solución que también trata de la y < 0mejor manera posible.

1. Utiliza un resultado de intmax_tpara el rango máximo. No hay disposición para respuestas que no encajan intmax_t.
2. powjii(0, 0) --> 1lo cual 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(;;)para siempre para evitar el base *= basecomún final en otras soluciones en bucle. Esa multiplicación es 1) no necesaria y 2) podría ser int*intdesbordamiento, que es UB.

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

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

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

Además de la respuesta de Elias, que causa un comportamiento indefinido cuando se implementa con enteros con signo, y valores incorrectos para una entrada alta cuando se implementa con enteros sin signo,

Aquí hay una versión modificada de Exponentiation by Squaring que también funciona con tipos enteros con signo y no da valores incorrectos:

#include <stdint.h>

#define SQRT_INT64_MAX (INT64_C(0xB504F333))

int64_t alx_pow_s64 (int64_t base, uint8_t exp)
{
    int_fast64_t    base_;
    int_fast64_t    result;

    base_   = base;

    if (base_ == 1)
        return  1;
    if (!exp)
        return  1;
    if (!base_)
        return  0;

    result  = 1;
    if (exp & 1)
        result *= base_;
    exp >>= 1;
    while (exp) {
        if (base_ > SQRT_INT64_MAX)
            return  0;
        base_ *= base_;
        if (exp & 1)
            result *= base_;
        exp >>= 1;
    }

    return  result;
}

Consideraciones para esta función:

(1 ** N) == 1
(N ** 0) == 1
(0 ** 0) == 1
(0 ** N) == 0

Si se va a producir un desbordamiento o envoltura, return 0;

Solía int64_t, pero cualquier ancho (con o sin signo) se puede usar con poca modificación. Sin embargo, si necesita usar un tipo entero de ancho no fijo, deberá cambiar SQRT_INT64_MAXpor (int)sqrt(INT_MAX)(en el caso de usar int) o algo similar, que debe optimizarse, pero es más feo y no una expresión constante C. Además, emitir el resultado de sqrt()a intno es muy bueno debido a la precisión de coma flotante en el caso de un cuadrado perfecto, pero como no conozco ninguna implementación donde, INT_MAXo el máximo de cualquier tipo, sea un cuadrado perfecto, puedes vivir con ese.

He implementado un algoritmo que memoriza todas las potencias calculadas y luego las 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 tomó de la tabla en lugar de calcularlo nuevamente. Esto es básicamente la implementación de la respuesta @Pramod (pero en C #). La cantidad de multiplicación necesaria 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);
}

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

En caso de que conozca el exponente (y es un número entero) en tiempo de compilación, puede usar plantillas para desenrollar el bucle. 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 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;
}