Número de FLOPs (operações de ponto flutuante) para exponenciação

7

Qual é o número de operações de ponto flutuante necessárias para executar a exponenciação (potência de)?

Supondo que a multiplicação de dois carros alegóricos use um FLOP, o número de operações para xn será n1. No entanto, existe uma maneira mais rápida de fazer isso? Como isso funciona sen não é um número inteiro?

Mr. Eivind
fonte

Respostas:

6

Supondo que a multiplicação entre dois números use um FLOP, o número de operações para xn será n1. No entanto, existe uma maneira mais rápida de fazer isso ...

Certamente, existe uma maneira mais rápida de fazer isso para potências inteiras não negativas. Por exemplo,x14=x8x4x2. É preciso uma multiplicação para calcularx2, mais um para calcular x4, mais um para calcular x8e mais dois para multiplicar esses três números. Isso sugere um custo simples e um algoritmo simples.

  • Converta a potência inteira não negativa para a base 2.
  • Conte o número de unidades nesta representação.
  • Adicione a potência de dois correspondentes ao bit diferente de zero mais significativo nesta representação.
  • Subtraia um.

Isso gera um algoritmo conciso para qualquer potência inteira não negativa. Esse algoritmo é o mais eficiente, atéx14. Esse algoritmo sugere que são necessárias seis multiplicações para calcularx15 Desde a x15=x8x4x2x. No entanto, 15 é 120 na base 3 e 30 na base 5, os quais implicam que apenas cinco multiplicações são necessárias para calcularx15: x15=(x3)4x3 da representação de base três e x15=(x5)3da representação da base cinco. O número mínimo de multiplicações necessárias para calcularxn Onde né um número inteiro não negativo é de fato um problema NP-completo . Mas é muito menos do quen1 multiplicações.

... e como funciona se n não é um número inteiro?

Existem alguns truques que se pode usar se né um racional. Mas sex é real e né um real não negativo, é preciso recorrer a técnicas de aproximação. (Por exemplo, técnicas de aproximação são usadas duas vezes no cálculoexp(nln(x)).)

David Hammen
fonte
Tem certeza de que calcula o número de multiplicações necessárias no NP-complete? Este parece ser um problema dependente da fatoração, que se acredita ser NP-Intermediário.
Stux
Você tem uma referência para a complexidade das cadeias de adição?
Yuval Filmus
@stux: Só porque fatorações produzir soluções candidatos não implica que todas as soluções são baseadas em fatoração ...
user21820
@ user21820: isso é verdade, daí a minha pergunta e redação. Se todas as soluções são direcionadas pela fatoração, o problema (provavelmente) não pode ser NP-completo. Caso contrário, o link fornecido não inclui uma referência que comprove a completude do NP.
stux 3/03/19
2
@stux - Downey, Peter, Benton Leong e Ravi Sethi. "Computando seqüências com cadeias de adição". SIAM Journal on Computing 10.3 (1981): 638-646.
David Hammen 3/03/19
5

Usar multiplicações n-1 seria um tanto estúpido. Por exemplo, se n = 1024, você apenas x dez vezes. O pior caso é 2 * log_2 (n). Você pode consultar Donald Knuth, arte da programação de computadores, para obter alguns detalhes de como fazê-lo mais rapidamente. Existem algumas situações, como n = 1023, em que você quadraria x dez vezes dando x ^ 1024 e depois dividir por x.

gnasher729
fonte
Obrigado, não sei por que isso não me veio à mente ...
Sr. Eivind
4

Você pode usar a fórmula

xy=exp(ylnx).

Se você deseja usar apenas multiplicações, quando né um número natural, você pode usar o quadrado repetido , que usaO(logn)multiplicações. Para outron, a multiplicação sozinha não é suficiente.

Yuval Filmus
fonte
3

As pessoas disseram o que acontece quando n é um número inteiro.

Em relação a isso, talvez não exista uma maneira de fazer exponenciação de ponto flutuante.

Chama -se Dilema do Criador de Tabelas , que diz que a quantidade de memória necessária é ilimitada:

Não existe uma maneira geral de prever quantos dígitos extras serão necessários para calcular uma expressão transcendental e arredondá-la corretamente para um número pré-atribuído de dígitos.
Mesmo o fato (se verdadeiro) de que um número finito de dígitos extras será suficiente pode ser um teorema profundo.

user541686
fonte
Para aritmética de ponto flutuante, é óbvio que um número finito de dígitos extras será suficiente, porque existe um conjunto finito de entradas.
precisa saber é o seguinte
@ gnasher729: Sim ... eu não teria postado isso no StackOverflow, mas, como no CS.SE, não tinha certeza de como interpretar literalmente a palavra "ponto flutuante" na pergunta. Eu pensei que havia uma chance decente de ter sido usado apenas como sinônimo de "não inteiro", então achei que mencionaria o caso transcendental de integridade.
user541686
11
Possivelmente relacionada a isso está a (antiga) lentidão extraordinária da implementação da antiga biblioteca matemática do gcc pow(x,y)para algumas entradas . Ele se esforçou muito (sem dúvida se esforçou demais) para perseguir a elusiva metade da precisão da ULP.
David Hammen 3/03/19
0

Se você é sério sobre o problema, pode não tentar encontrar uma solução com o menor número de multiplicações, mas com o menor tempo de execução.

Considere um modelo em que você possa iniciar uma multiplicação em cada ciclo, mas cada multiplicação leva um número fixo de ciclos, digamos 3 ciclos. Um método que calcula x ^ n com k multiplicações pode levar 3k ciclos (se cada multiplicação depender de um resultado que foi calculado antes), enquanto um método que usa mais multiplicações pode ser executado mais rapidamente.

Por exemplo: Para calcular x ^ 15, você pode calcular nessa ordem x ^ 2 = x * x, x ^ 3 = (x ^ 2) * x, x ^ 6 = (x ^ 3) ^ 2, x ^ 7 Se x = x ^ 6 * x, x ^ 14 = (x ^ 7) ^ 2, x ^ 15 = x ^ 14 * x. Seis multiplicações, mas cada uma depende da anterior.

Ou calcule x ^ 2, x ^ 4 = (x ^ 2) ^ 2, x ^ 3 = x ^ 2 * x, x ^ 5 = (x ^ 4) * x, x ^ 15 = x ^ 5 * x ^ 3, então você tem apenas quatro multiplicações, dependendo dos resultados anteriores.

gnasher729
fonte
O último parágrafo está errado. x5x3 é x8, não x15. Cálculox15 requer pelo menos cinco multiplicações (ou quatro multiplicações para produzir x16, seguido por uma divisão por x, mas isso é mais caro que cinco multiplicações).
David Hammen 3/03/19