A maneira mais eficiente de implementar uma função de potência baseada em número inteiro pow (int, int)

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

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

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

Exponenciação ao quadrado.

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

Observe que a exponenciação ao quadrado não é o método mais ideal. Provavelmente é o melhor que você pode fazer como método geral que funciona para todos os valores de expoente, mas para um valor específico de expoente pode haver uma sequência melhor que precise de menos multiplicações.

Por exemplo, se você quiser calcular x ^ 15, o método de exponenciação ao quadrado fornecerá:

x^15 = (x^7)*(x^7)*x 
x^7 = (x^3)*(x^3)*x 
x^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 da 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 sequência ótima de multiplicações. Da Wikipedia :

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

Se você precisar aumentar 2 para uma potência. A maneira mais rápida de fazer isso é mudar a potência.

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ê deseja obter o valor de um número inteiro para 2 elevado ao poder de algo, é sempre melhor usar a opção shift:

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

Isso é muito mais eficiente.

power()função para trabalhar somente com 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))

power()função para trabalhar para exp negativa e base flutuante .

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

Um caso extremamente especializado é que, quando você precisa dizer 2 ^ (- x para y), onde x, é claro que é negativo e y é muito grande para alterar um int. Você ainda pode fazer 2 ^ x em tempo constante apertando 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;
    u.f = 2.0;
    // Change the exponent part of the float
    u.brokenOut.exponent += (exponent - 1);
    return (u.f);
}

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

Há também a possibilidade de que, aprendendo mais sobre flutuadores IEEE , outros casos especiais de exponenciação possam se apresentar.

Apenas como acompanhamento de comentários sobre a eficiência da exponenciação por quadratura.

A vantagem dessa abordagem é que ela é executada no tempo de log (n). Por exemplo, se você fosse calcular algo enorme, 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 do código, é mais simples do que tentar encontrar a seqüência mais ótima de multiplicações, como a sugestão de Pramod.

Editar:

Acho que devo esclarecer antes que alguém me marque o potencial de estouro. Essa abordagem pressupõe que você tenha algum tipo de biblioteca enorme.

Atrasado para a festa:

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

1. Ele usa um resultado de intmax_tpara o alcance máximo. Não há provisão para respostas que não se encaixem intmax_t.
2. powjii(0, 0) --> 1o 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;
   }

Esse código usa um loop for(;;)para sempre para evitar o base *= basecomum final em outras soluções em loop. Essa multiplicação é 1) não necessária e 2) pode estar int*intexcedendo, o que é UB.

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

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

Eu uso recursivo, se o exp for 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);
   }
}

Além da resposta de Elias, que causa Comportamento indefinido quando implementado com números inteiros assinados e valores incorretos para entrada alta quando implementada com números inteiros não assinados,

aqui está uma versão modificada da exponenciação por esquadro que também funciona com tipos inteiros assinados e não fornece valores incorretos:

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

Considerações para esta função:

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

Se ocorrer algum transbordamento ou encapsulamento, return 0;

Eu usei int64_t, mas qualquer largura (assinada ou não) pode ser usada com poucas modificações. No entanto, se você precisa usar um tipo inteiro não de largura fixa, você terá de mudar SQRT_INT64_MAXpor (int)sqrt(INT_MAX)(no caso de usar int) ou algo semelhante, que deve ser otimizado, mas é mais feio, e não uma expressão C constante. Também converter o resultado de sqrt()para um intnão é muito bom por causa da precissão de ponto flutuante no caso de um quadrado perfeito, mas como não conheço nenhuma implementação em que INT_MAX- ou o máximo de qualquer tipo - seja um quadrado perfeito, você pode viver com isso.

Eu implementei um algoritmo que memoriza todos os poderes computados e os utiliza quando necessário. Assim, por exemplo, x ^ 13 é igual a (x ^ 2) ^ 2 ^ 2 * x ^ 2 ^ 2 * x onde x ^ 2 ^ 2 foi retirado da tabela em vez de computá-lo novamente. Isso é basicamente a implementação da resposta @Pramod (mas em C #). 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);
}

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

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

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

Caso você saiba o expoente (e é um número inteiro) no tempo de compilação, você pode usar modelos para desenrolar o loop. Isso pode ser mais eficiente, mas eu queria demonstrar o princípio básico aqui:

#include <iostream>

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

Encerramos a recursão 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;
}