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

249

¿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
Doug T.
fuente
3
Cuando dices "eficiencia", debes especificar eficiente en relación con qué. ¿Velocidad? ¿Uso de memoria? Tamaño del código? Mantenibilidad?
Andy Lester
¿C no tiene una función pow ()?
jalf
16
sí, pero eso funciona en flotadores o dobles, no en ints
Nathan Fellman
1
Si te apegas a la ints real (y no a una clase de int. Enorme), se desbordarán muchas llamadas a ipow. Me hace preguntarme si hay una manera inteligente de calcular previamente una tabla y reducir todas las combinaciones que no se desbordan a una simple búsqueda de tabla. Esto requeriría más memoria que la mayoría de las respuestas generales, pero quizás sea más eficiente en términos de velocidad.
Adrian McCarthy
pow()no es una función segura
EsmaeelE

Respuestas:

391

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.

Elias Yarrkov
fuente
38
Probablemente debería agregar un cheque que "exp" no es negativo. Actualmente, esta función dará una respuesta incorrecta o se repetirá para siempre. (Dependiendo de si >> = en un int con signo hace relleno de cero o extensión de signo, los compiladores de C pueden elegir cualquier comportamiento).
user9876
23
Escribí una versión más optimizada de esto, que se puede descargar gratuitamente aquí: gist.github.com/3551590 En mi máquina era aproximadamente 2.5 veces más rápido.
orlp
10
@AkhilJain: Es perfectamente bueno C; para que sea válido también en Java, reemplace while (exp)y if (exp & 1)con while (exp != 0)y if ((exp & 1) != 0)respectivamente.
Ilmari Karonen
3
Su función probablemente debería tener unsigned exp, o bien manejar negativamente expcorrectamente.
Craig McQueen
55
@ZinanXing Multiplicar n veces da como resultado más multiplicaciones y es más lento. Este método ahorra multiplicaciones al reutilizarlas efectivamente. Por ejemplo, para calcular n ^ 8, el método ingenuo de n*n*n*n*n*n*n*nutiliza 7 multiplicaciones. Este algoritmo calcula m=n*n, entonces o=m*m, entonces p=o*o, donde p= n ^ 8, con solo tres multiplicaciones. Con grandes exponentes, la diferencia en el rendimiento es significativa.
bames53
69

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 )

Pramod
fuente
44
@JeremySalwen: Como dice esta respuesta, la exponenciación binaria no es en general el método más óptimo. No hay algoritmos eficientes actualmente conocidos para encontrar la secuencia mínima de multiplicaciones.
Eric Postpischil
2
@EricPostpischil, eso depende de su aplicación. Por lo general, no necesitamos un algoritmo general para trabajar con todos los números. Ver El arte de la programación de computadoras, vol. 2: Algoritmos Seminuméricos
Pacerier
3
Hay una buena exposición de este problema exacto en From Mathematics to Generic Programming por Alexander Stepanov y Daniel Rose. Este libro debería estar en el estante de cada profesional de software, en mi humilde opinión.
Toby Speight
2
Ver también en.wikipedia.org/wiki/… .
lhf
Esto podría optimizarse para los enteros porque hay menos de 255 potencias enteras que no causarán desbordamiento para los enteros de 32 bits. Puede almacenar en caché la estructura de multiplicación óptima para cada int. Me imagino que el código + datos aún sería más pequeño que simplemente almacenar en caché todos los poderes ...
Josiah Yoder
22

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)
Jake
fuente
¿Hay una manera elegante de hacer esto para que 2 ** 0 == 1?
Rob Smallshire
16
2 ** 0 == 1 << 0 == 1
Jake
14

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;
}
usuario1067920
fuente
no funciona para grandes cantidades, por ejemplo, pow (71045970,41535484)
Anushree Acharjee
16
@AnushreeAcharjee, por supuesto que no. Calcular ese número requeriría una aritmética de precisión arbitraria.
David Etler
Use BigInteger # modPow o Biginteger # pow para números grandes, los algoritmos apropiados basados ​​en el tamaño de los argumentos ya están implementados
Raman Yelianevich
¡Esta NO es una pregunta de Java!
Cacahuete Frito
7
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);
}
Chris Cudmore
fuente
No es mi voto, pero pow(1, -1)no deja el rango de int a pesar de un exponente negativo. Ahora que uno trabaja por accidente, como lo hace pow(-1, -1).
MSalters
El único exponente negativo que puede no hacerte abandonar el rango de int es -1. Y solo funciona si la base es 1 o -1. Entonces, solo hay dos pares (base, exp) con exp <0 que no conducirían a potencias no enteras. A pesar de que soy un matematician y me gusta cuantificadores, creo que en este caso, en la práctica, está bien decir que un exponente negativo hace que salga el reino entero ...
bartgol
6

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.

aditya
fuente
6

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

roottraveller
fuente
¿Cómo es esto diferente de las respuestas de Abhijit Gaikwad y chux ? Argumente el uso de floaten el segundo bloque de código presentado (considere mostrar cómo power(2.0, -3)se calcula).
barba gris
@greybeard He mencionado algunos comentarios. puede ser que pueda resolver su consulta
roottraveller
1
GNU Scientific Library ya tiene su segunda función: gnu.org/software/gsl/manual/html_node/Small-integer-powers.html
Cacahuete Frito
@roottraveller, ¿podría explicar la negative exp and float basesolución? ¿Por qué usamos temp, separamos exp por 2 y verificamos exp (par / impar)? ¡Gracias!
Lev
6

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.

Doug T.
fuente
¿Solución ingeniosa, pero sin ser esclavo?
paxdiablo
Un flotador IEEE es base x 2 ^ exp, cambiar el valor del exponente no conducirá a nada más que una multiplicación por una potencia de dos, y las posibilidades son altas, desnormalizará el flotador ... su solución está mal IMHO
Drealmer
Todos están en lo correcto, recordé mal que mi solución fue escrita originalmente, hace mucho tiempo, para poderes de 2 explícitamente. He reescrito mi respuesta para que sea una solución de caso especial al problema.
Doug T.
En primer lugar, el código se rompe según lo citado y requiere edición para que se compile. En segundo lugar, el código se rompe en un core2d usando gcc. ver este basurero Quizás hice algo mal. Sin embargo, no creo que esto funcione, ya que el exponente de flotación IEEE es la base 10.
espacio libre
3
Base 10? Uh no, es base 2, a menos que
quisieras
4

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.

Jason Z
fuente
2

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.

chux - Restablece a Monica
fuente
powjii(INT_MAX, 63)causa UB en base *= base. Considere verificar que puede multiplicar o pasar a sin firmar y dejar que se ajuste.
Cacahuete Frito
No hay razón para haber expsido firmado. Complica el código debido a la extraña situación en la que (-1) ** (-N)es válido, y cualquiera abs(base) > 1será 0para valores negativos de exp, por lo que es mejor tenerlo sin firmar y guardar ese código.
Cacahuete Frito
1
@CacahueteFrito Es cierto que, ytal como se firmó, no es realmente necesario y trae las complicaciones que comentó, pero la solicitud de OP fue específica pow(int, int). Por lo tanto, esos buenos comentarios pertenecen a la pregunta del OP. Como OP no ha especificado qué hacer en caso de desbordamiento, una respuesta incorrecta bien definida es solo marginalmente mejor que UB. Dada la "forma más eficiente", dudo que a OP le importe OF.
chux - Restablecer Monica
1

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);
}
Abhijit Gaikwad
fuente
1
la división de enteros da como resultado un entero, por lo que su exponente negativo podría ser mucho más eficiente ya que solo devolverá 0, 1 o -1 ...
jswolf19
pow(i, INT_MIN)podría ser un bucle infinito.
chux - Restablece a Mónica el
1
@chux: Podría formatear su disco duro: el desbordamiento de enteros es UB.
MSalters
@MSalters pow(i, INT_MIN)no es un desbordamiento de enteros. La asignación de ese resultado tempciertamente puede desbordarse, lo que puede causar el fin del tiempo , pero me conformaré con un valor aparentemente aleatorio. :-)
chux - Restablecer Monica
0

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;
    }       
}
Vaibhav Fouzdar
fuente
¡No es una pregunta de Java!
Cacahuete Frito
0

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);
   }
}
kyorilys
fuente
0

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.

Cacahuete Frito
fuente
0

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);
}
rango1
fuente
public? 2 funciones con el mismo nombre? Esta es una pregunta C.
Cacahuete Frito
-1

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;
MarcusJ
fuente
Intenté eso, no funciona durante 64 bits, está desactivado para que nunca regrese, y en este caso específico, estoy tratando de establecer todos los bits más bajos que X, inclusive.
MarcusJ
¿Fue por 1 << 64? Eso es un desbordamiento. El número entero más grande está justo debajo de eso: (1 << 64) - 1.
Michaël Roy
1 << 64 == 0, por eso. Quizás tu representación sea la mejor para tu aplicación. Prefiero cosas que se pueden poner en una macro, sin una variable adicional, como #define MASK(e) (((e) >= 64) ? -1 :( (1 << (e)) - 1)), por lo que se pueden calcular en tiempo de compilación
Michaël Roy
Sí, sé lo que es un desbordamiento. El hecho de que no haya usado esa palabra no es una invitación a ser innecesariamente condescendiente. Como dije, esto funciona para mí y me costó un poco descubrirlo, por lo tanto, compartirlo. Es así de simple.
MarcusJ
Lo siento si te ofendí. Realmente no quise hacerlo.
Michaël Roy
-1

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;
}
Johannes Blaschke
fuente
1
Claramente, esta no es una pregunta de C ++. (c != c++) == 1
Cacahuete Frito