A maneira mais eficiente de implementar uma function de poder baseada em inteiro pow (int, int)

Qual é a maneira mais eficiente dada para elevar um inteiro à potência de outro inteiro em C?

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

Exponenciação por quadratura.

 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 é o método padrão para fazer exponenciação modular para grandes números em criptografia assimétrica.

Note que a exponenciação por quadratura não é o método mais ideal. É provavelmente o melhor que você pode fazer como um método geral que funciona para todos os valores de expoentes, mas para um valor de expoente específico pode haver uma seqüência melhor que precisa de menos multiplicações.

Por exemplo, se você quiser calcular x ^ 15, o método de exponenciação por quadratura dará a você:

 x^15 = (x^7)*(x^7)*xx^7 = (x^3)*(x^3)*xx^3 = x*x*x 

Este é um total de 6 multiplicações.

Acontece que isso pode ser feito usando “apenas” 5 multiplicações via exponenciação de cadeia de adição .

 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 

Não há algoritmos eficientes para encontrar essa seqüência ideal de multiplicações. Da Wikipedia :

O problema de encontrar a cadeia de adição mais curta não pode ser resolvido por programação dinâmica, porque não satisfaz a suposição de uma subestrutura ótima. Ou seja, não é suficiente decompor o poder em poderes menores, cada um dos quais é computado minimamente, uma vez que as cadeias de adição para as potências menores podem estar relacionadas (para compartilhar cálculos). Por exemplo, na cadeia de adição mais curta para α acima, o subproblema para a⁶ deve ser calculado como (a³) ², pois a³ é reutilizada (em oposição a, digamos, a⁶ = a² (a²) ², que também requer três multiplicações ).

Se você precisa aumentar 2 para um poder. A maneira mais rápida de fazer isso é mudar o bit pelo poder.

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

Aqui está o método em 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); } 

Se você quiser obter o valor de um inteiro para 2 elevado ao poder de alguma coisa, é sempre melhor usar a opção shift:

pow(2,5) pode ser substituído por 1<<5

Isso é muito mais eficiente.

Um caso extremamente especializado é, quando você precisa dizer 2 ^ (- x para y), onde x, é claro, é negativo e y é muito grande para mudar em um int. Você ainda pode fazer 2 ^ x em tempo constante enroscando com um flutuador.

 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; uf = 2.0; // Change the exponent part of the float u.brokenOut.exponent += (exponent - 1); return (uf); } 

Você pode obter mais potências de 2 usando um duplo como o tipo base. (Muito obrigado aos comentaristas por ajudarem a eliminar este post).

Há também a possibilidade de aprender mais sobre flutuadores do IEEE , outros casos especiais de exponenciação podem se apresentar.

Apenas como um seguimento aos comentários sobre a eficiência da exponenciação pela quadratura.

A vantagem dessa abordagem é que ela é executada no log (n) time. Por exemplo, se você fosse calcular algo grande, como x ^ 1048575 (2 ^ 20 – 1), você só precisa passar pelo loop 20 vezes, e não 1 milhão + usando a abordagem ingênua.

Além disso, em termos de complexidade de código, é mais simples do que tentar encontrar a sequência mais adequada de multiplicações, à sugestão de Pramod.

Editar:

Eu acho que deveria esclarecer antes que alguém me identifique pelo potencial de estouro. Essa abordagem pressupõe que você tenha algum tipo de biblioteca enormeint.

function power() para trabalhar somente para números inteiros

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

Complexidade = O (log (exp))

function power() para trabalhar para exp negativo e 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 } } 

Complexidade = O (log (exp))

Tarde para a festa:

Abaixo está uma solução que também lida com y < 0 melhor forma possível.

  1. Ele usa um resultado de intmax_t para alcance máximo. Não há previsão para respostas que não se encheckboxm em intmax_t .
  2. powjii(0, 0) --> 1 que é um resultado comum para este caso.
  3. pow(0,negative) , outro resultado indefinido, retorna 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 um loop permanente for(;;) para evitar a base *= base final base *= base comum em outras soluções em loop. Essa multiplicação é 1) não necessária e 2) poderia ser int*int estouro que é UB.

Mais uma implementação (em Java). Pode não ser a solução mais eficiente, mas o número de iterações é igual ao da solução 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; } } 

solução mais genérica considerando 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); } 

Eu implementei um algoritmo que memoriza todos os poderes computados e depois os usa quando necessário. Então, por exemplo, x ^ 13 é igual a (x ^ 2) ^ 2 ^ 2 * x ^ 2 ^ 2 * x onde x ^ 2 ^ 2 é retirado da tabela em vez de ser computado novamente. O número de multiplicação necessário é 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); } 

Eu uso recursiva, se o exp é mesmo, 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); } } 

Meu caso é um pouco diferente, estou tentando criar uma máscara a partir de um poder, mas pensei em compartilhar a solução que encontrei de qualquer maneira.

Obviamente, só funciona para potências de 2.

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

Caso você conheça o expoente (e é um inteiro) em tempo de compilation, você pode usar modelos para desenrolar o loop. Isso pode se tornar mais eficiente, mas eu queria demonstrar o princípio básico aqui:

 #include  template unsigned long inline exp_unroll(unsigned base) { return base * exp_unroll(base); } 

Terminamos a recursion usando uma especialização de modelo:

 template<> unsigned long inline exp_unroll<1>(unsigned base) { return base; } 

O expoente precisa ser conhecido em tempo de execução,

 int main(int argc, char * argv[]) { std::cout << argv[1] <<"**5= " << exp_unroll<5>(atoi(argv[1])) << ;std::endl; } 

Ignorando o caso especial de 2 elevado a um poder, a maneira mais eficiente será a iteração simples.

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

EDIT: Como foi apontado, esta não é a maneira mais eficiente ... desde que você defina a eficiência como ciclos de CPU que eu acho que é justo o suficiente.