A maneira mais eficiente para implementar uma função de potência inteira baseado POW (int, int)

Question

O que é a forma mais eficiente dada a levantar um inteiro para o poder de outro inteiro em C?

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

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

Answer 1

A 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.

Answer 2

Note que 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 expoente, mas para um valor 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 vai lhe dar:

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 de cadeia além exponenciaçã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. De Wikipedia :

O problema de encontrar a cadeia mais curta adição não pode ser resolvido por programação dinâmica, porque ele não satisfaz a assunção de subestrutura ideal. Ou seja, ele não é suficiente para decompor o poder em poderes menores, cada um dos quais é calculado minimamente, uma vez que as cadeias de adição para os poderes menores podem estar relacionados (para cálculos de ações). Por exemplo, na cadeia mais curta adição para a¹5 acima, o subproblema para a6 deve ser calculado como (³) ² desde ³ é (em oposição a, por exemplo, a6 = a² (a²) m², reutilizado, que também requer três multiplica ).

Answer 3

Se você precisa aumentar 2 a uma potência. A maneira mais rápida de fazer isso é a mudança pouco pelo poder.

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

Answer 4

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

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

Se você quiser obter o valor de um inteiro para 2 elevado à potência de algo é sempre melhor usar a opção de mudança:

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

Este é muito mais eficiente.

Answer 7

Um caso extremamente especializada é, quando você precisa dizer 2 ^ (- x ao y), onde x, é, naturalmente, é negativo e y é muito grande para não mudando em um int. Você ainda pode fazer 2 ^ x em tempo constante, enroscando com um float.

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 de base. (Muito obrigado a comentadores para ajudar a enquadrar este post de distância).

Há também a possibilidade de que aprender mais sobre IEEE flutua , outros casos especiais de exponenciação poder apresentar-se.

Answer 8

Assim como um acompanhamento para comentários sobre a eficiência de exponenciação por quadratura.

A vantagem dessa abordagem é que ele é executado em (n) log tempo. Por exemplo, se você estava indo para calcular algo enorme, como x ^ 1048575 (2 ^ 20-1)., Você só tem que atravessar o loop 20 vezes, 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 ideal mais de multiplicações, uma sugestão la de Pramod.

Editar:

Eu acho que deveria esclarecer antes que alguém etiquetas me para o potencial de estouro. Esta abordagem assume que você tem algum tipo de biblioteca hugeint.

Answer 9

função power() de trabalho para Inteiros Só

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

função power() de trabalho para exp negativo 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))

Answer 10

atrasado para a festa:

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

1. Ele usa um resultado de intmax_t para o alcance máximo. Não há provisão para respostas que não se encaixam em intmax_t.
2. powjii(0, 0) --> 1 que é um resultado comum para este caso.

3. pow(0,negative), outro resultado indefinido, retornos 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 for(;;) loop contínuo para evitar o comum base *= base final em outras soluções em loop. Que a multiplicação é 1) não for necessária e 2) poderia ser estouro int*int que é UB.

Answer 11

mais genérico solução considerando negativo expoente

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

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

Answer 13

Eu uso recursivo, se o exp é ainda, 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

Além da resposta de Elias, o que provoca um comportamento indefinido quando implementado com números inteiros assinados e valores incorretos para alta de entrada quando implementado com números inteiros sem sinal,

aqui é uma versão modificada do exponenciação por quadratura que também trabalha com inteiro assinado tipos, e não dá 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 qualquer estouro ou embrulho vai ter lugar, return 0;

Eu costumava int64_t, mas qualquer largura (com ou sem sinal) pode ser utilizado com pouca modificação. No entanto, se você precisa usar um tipo inteiro não de largura fixa, você vai precisar alterar SQRT_INT64_MAX por (int)sqrt(INT_MAX) (no caso de usar int) ou algo semelhante, que deve ser otimizado, mas é mais feio, e não um C expressão constante. Também lançando o resultado de sqrt() a um int não é muito bom, porque de flutuar precission ponto em caso de um quadrado perfeito, mas como eu não sei de qualquer aplicação onde INT_MAX -ou o máximo de qualquer de tipo é um quadrado perfeito, você pode viver com isso.

Answer 15

Eu tenho implementado algoritmo que memoriza todos os poderes computados e então usa-los quando necessário. Assim, por exemplo, x ^ 13 é igual a (x ^ 2) ^ 2 ^ 2 * x ^ 2 ^ 2 * x em que x ^ 2 ^ 2 lo tomado a partir da tabela em vez de computação lo mais uma vez. Este é basicamente implementação de @Pramod resposta (mas em C #). O número de multiplicação é necessário Ceil (N 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

O meu caso é um pouco diferente, eu estou tentando criar uma máscara de um poder, mas eu pensei que eu iria partilhar a solução que eu encontrei qualquer maneira.

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

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

Answer 17

Caso você saiba o expoente (e é um inteiro) em tempo de compilação, você pode usar modelos para desenrolar o loop. Isto pode ser feito 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);
}

Nós terminar 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;
}

Answer 18

Ignorando o caso especial de 2 elevado a uma potência, a forma mais eficiente vai ser iteração simples.

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

  return res;
}

EDIT:. Como tem sido apontado esta não é a forma mais eficiente ... contanto que você definir a eficiência como ciclos de CPU que eu acho que é suficiente justo