La forma más eficiente para implementar un entero de energía basada en la función pow(int, int)

Question

¿Cuál es la manera más eficiente dado a elevar un número entero a la potencia de otro entero en C?

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

// 5^5
pow(5,5) == 3125

Answer 1

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 hacer exponenciación modular de una enorme cantidad de criptografía asimétrica.

Answer 2

Tenga en cuenta que exponenciación al cuadrado no es el más óptimo método.Es probablemente el mejor que usted puede hacer como un método general que funciona para todos los valores de exponente, pero para un determinado valor de exponente podría ser una mejor secuencia de la que necesita menos multiplicaciones.

Por ejemplo, si desea calcular x^15, el método de exponenciación 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 mediante "sólo" 5 multiplicaciones a través de además de la cadena de exponenciació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 existen algoritmos eficientes para encontrar esta secuencia óptima de las multiplicaciones.De Wikipedia:

El problema de encontrar el menor, además de la cadena no puede ser resuelto mediante la programación dinámica, debido a que no cumple con la asunción de la subestructura óptima.Es decir, no es suficiente para descomponer el poder en pequeños poderes, cada uno de los cuales se calcula mínimamente, ya que la adición de cadenas para los más pequeños poderes pueden estar relacionados con (a compartir sus cálculos).Por ejemplo, en el menor adición de la cadena de a1⁵ anterior, el subproblem para a⁶ debe ser calculada como (a3)2 puesto que a3 es re-utilizado (a diferencia de, digamos, a⁶ = a2(a2)2, que también requiere de tres multiplica).

Answer 3

Si usted necesita para elevar 2 a la potencia.La forma más rápida de hacerlo es la de desplazamiento de bits por el poder.

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

Answer 4

Aquí es 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 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);
}

Answer 6

Si usted desea obtener el valor de un entero por 2 elevado a la potencia de algo siempre es mejor utilizar la opción de cambio:

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

Esto es mucho más eficiente.

Answer 7

Una muy especializados caso es que, cuando usted necesita decir 2^(-x a y), donde x, es, por supuesto, es negativo y y es demasiado grande para hacer el cambio en un int.Usted todavía puede 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);
}

Usted puede obtener más potencias de 2 mediante el uso de un doble como el tipo base.(Muchas gracias a los comentaristas por ayudar a la plaza de este post de distancia).

También existe la posibilidad de que aprender más acerca de IEEE flota, otros casos especiales de exponenciación podría presentar a sí mismos.

Answer 8

Así como un seguimiento a los comentarios sobre la eficiencia de la exponenciación al cuadrado.

La ventaja de este enfoque es que se ejecuta en log(n) tiempo.Por ejemplo, si usted se va a calcular algo enorme, como x^1048575 (2^20 - 1), sólo tienes que ir a través del bucle de 20 veces, no de 1 millón de+ utilizando el enfoque ingenuo.

También, en términos de la complejidad del código, es más fácil que tratar de encontrar la mejor secuencia de multiplicaciones, a la Pramod la sugerencia.

Editar:

Supongo que debo aclarar antes de etiquetas para alguien que me de la posibilidad de desbordamiento.Este enfoque asume que usted tiene algún tipo de hugeint de la biblioteca.

Answer 9

power() función de trabajo para Enteros Sólo

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;

}

La complejidad de la = O(log(exp))

power() función de trabajo para negativo exp y float base.

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 
    }

} 

La complejidad de la = O(log(exp))

Answer 10

Tarde a la fiesta:

A continuación es una solución que se ocupa también de y < 0 lo mejor que puede.

1. Se utiliza un resultado de intmax_t para el máximo rango.No hay ninguna disposición para las respuestas que no encajan en el intmax_t.
2. powjii(0, 0) --> 1 que es un resultado común para este caso.

3. pow(0,negative), otro indefinido resultado, 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 se utiliza un bucle para siempre for(;;) para evitar el final base *= base común en otros bucle soluciones.Que la multiplicación es 1) no se necesitan, y 2) podría ser int*int desbordamiento de que es UB.

Answer 11

más genérico solución considerando negativo exponenet

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

Uno más de la implementación (en Java).No puede ser la solución más eficiente, pero el # 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 13

Yo uso recursivo, si la exp es, incluso,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 14

Además de la respuesta por parte de Elías, lo que provoca un Comportamiento Indefinido cuando se implementa con enteros, y valores incorrectos para la entrada de alta cuando se implementa con los enteros sin signo,

aquí es una versión modificada de la Exponenciación al Cuadrado que también funciona con entero con signo de tipos, y no dar 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 cualquier desbordamiento o envoltura que va a tener lugar, return 0;

He utilizado int64_t, pero en cualquier ancho (con o sin signo) puede ser utilizado con pocas modificaciones.Sin embargo, si usted necesita para usar un ancho fijo de tipo entero, usted tendrá que cambiar SQRT_INT64_MAX por (int)sqrt(INT_MAX) (en el caso de la utilización de int) o algo similar, que debe ser optimizado, pero es más feo, y no una expresión de la constante C.También casting el resultado de sqrt() a un int no es muy buena porque de punto flotante de precisión en el caso de un cuadrado perfecto, pero como no sé de cualquier aplicación donde INT_MAX -o el máximo de cualquier tipo - es un cuadrado perfecto, se puede vivir con eso.

Answer 15

He implementado el algoritmo que memoriza todos los calculada poderes y los utiliza cuando se necesita.Así, por ejemplo, x^13 es igual a (x^2)^2^2 * x^2^2 * x, donde x^2^2 es tomado de la tabla, en lugar de la computación, una vez más.Esta es básicamente la aplicación de @Pramod respuesta (pero en C#).El número de multiplicación necesita 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 16

Mi caso es un poco diferente, estoy tratando de crear una máscara a partir de una potencia, pero yo pensé en compartir la solución que he encontrado de todos modos.

Obviamente, esto sólo funciona para las potencias de 2.

Mask1 = 1 << (Exponent - 1);
Mask2 = Mask1 - 1;
return Mask1 + Mask2;

Answer 17

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

Damos por terminada la recursividad mediante una plantilla de especialización:

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 18

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

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

  return res;
}

EDITAR:Como ha señalado esta no es la forma más eficiente...siempre y cuando usted definir la eficiencia como los ciclos de cpu que supongo que es bastante justo.