Como expoentes são calculados?

Question

Eu estou tentando determinar o tempo de execução assintótica de um dos meus algoritmos, que usa expoentes, mas eu não tenho certeza de como expoentes são calculados por meio de programação.

Eu estou procurando especificamente para o pow () algoritmo usado para precisão dupla, números de ponto flutuante.

Answer 1

Eu tive a chance de olhar para a implementação do fdlibm. Os comentários descrevem o algoritmo usado:

 *                    n
 * Method:  Let x =  2   * (1+f)
 *      1. Compute and return log2(x) in two pieces:
 *              log2(x) = w1 + w2,
 *         where w1 has 53-24 = 29 bit trailing zeros.
 *      2. Perform y*log2(x) = n+y' by simulating muti-precision
 *         arithmetic, where |y'|<=0.5.
 *      3. Return x**y = 2**n*exp(y'*log2)

seguido por uma listagem de todos os casos especiais manipulados (0, 1, inf, nan).

As maioria das seções intensas do código, depois de toda a manipulação do caso especial, envolver os cálculos log2 e 2**. E não há loops em um desses. Assim, a complexidade das primitivas de ponto flutuante não obstante, parece que um algoritmo assintoticamente de tempo constante.

especialistas de ponto flutuante (de que eu não sou um) são bem-vindos para comentar. : -)

Answer 2

A menos que eles descobriram uma maneira melhor de fazer isso, eu acredito que os valores aproximados para trig, logarítmica e funções exponenciais (para crescimento exponencial e decadência, por exemplo) são geralmente calculadas usando regras aritméticas e Série Taylor expansões para produzir um resultado aproximado com precisão de precisão solicitado. (Veja qualquer livro de cálculo para obter detalhes sobre séries de potência, série de Taylor, e expansões série de Maclaurin de funções.) Por favor, note que ele tem sido um tempo desde que eu fiz nada disso, então eu não poderia dizer-lhe, por exemplo, exatamente como calcular o número de termos na série, você precisa incluir garantia de um erro que pequeno o suficiente para ser insignificante em um cálculo de precisão dupla.

Por exemplo, a expansão da série de Taylor / Maclaurin para e ^ x é o seguinte:

      +inf [ x^k ]           x^2    x^3      x^4        x^5
e^x = SUM  [ --- ] = 1 + x + --- + ----- + ------- + --------- + ....
      k=0  [  k! ]           2*1   3*2*1   4*3*2*1   5*4*3*2*1

Se você pegar todos os termos (k de 0 a infinito), essa expansão é exacta e completa (sem erro).

No entanto, se você não tomar todos os termos indo ao infinito, mas você parar depois de dizer 5 termos ou 50 termos ou qualquer outra coisa, você produz um aproximado resultado que difere do e real ^ x valor da função por um restante que é bastante fácil de calcular.

A boa notícia para exponenciais é que ela converge bem e os termos de sua expansão polinomial são bastante fáceis de código de forma iterativa, assim você pode (repetição, PODER - lembre-se , tem sido um tempo) não precisa mesmo de pré-calcular quantos termos que você precisa para garantir o seu erro é menor do que a precisão porque você pode testar o tamanho da contribuição a cada iteração e parada quando se torna suficientemente perto de zero. Na prática, eu não sei se esta estratégia é viável ou não - eu teria que tentar. Há detalhes importantes que eu já há muito esquecido. Coisas como:. Precisão da máquina, erro da máquina e erros de arredondamento, etc

Além disso, observe que, se você não estiver usando e ^ x, mas você está fazendo crescimento / decaimento com outra base, como 2 ^ x ou 10 ^ x, os aproximam alterações função polinomial.

Answer 3

A abordagem usual, para levantar um ao b, para um expoente inteiro, é algo como isto:

result = 1
while b > 0
  if b is odd
    result *= a
    b -= 1
  b /= 2
  a = a * a

Em geral, é logarítmica no tamanho do expoente. O algoritmo é baseado no invariante "a ^ b * result = a0 ^ b0", onde a0 e b0 são os valores iniciais de um e b.

Para expoentes negativos ou não-inteiros, logaritmos e aproximações e análise numérica são necessários. O tempo de execução vai depender do algoritmo usado eo que precisão a biblioteca está atento para.

Edit:. Como não parece haver algum interesse, aqui está uma versão sem a multiplicação adicional

result = 1
while b > 0
  while b is even
    a = a * a
    b = b / 2
  result = result * a
  b = b - 1

Answer 4

Se eu estivesse escrevendo uma função pow alvo Intel, eu gostaria de voltar exp2 (log2 (x) * y). microcódigo da Intel para log2 é certamente mais rápido do que qualquer coisa que eu seria capaz de código, mesmo que eu poderia lembrar o meu primeiro cálculo ano e análise numérica pós-graduação.

Answer 5

Você pode usar exp (n * ln (x)) para calcular x ⁿ . Ambos X e n pode ser de precisão dupla, números de ponto flutuante. logaritmo natural e função exponencial pode ser calculado usando séries de Taylor. Aqui você pode encontrar fórmulas: http://en.wikipedia.org/wiki/Taylor_series