precisão da avaliação polinomial, multiplicação versus divisão

Question

Digamos que eu tenha polinomial em x, dividido por um poder de x:

p = (a + x(b + x(c + ..)))/(x**n)

eficiência à parte, que seria mais preciso computação numericamente, o acima ou usando a divisão:

p = (((a/x + b)/x + c)/x + ...)

obrigado

Answer 1

Eu acho que a diferença é mínima, a menos que haja uma chance de que x**n transbordam ou sob fluxos, caso em que você deve usar a segunda expressão.

As duas expressões diferem em dois lugares:

1. A ordem de avaliação é revertida (..., c, b, a) para a primeira expressão e (a, b, c, ...) para a segunda expressão. Qual é o melhor depende do valor dos coeficientes.
2. A primeira expressão tem o .../x**n no final. Como Jonathan explica, por esse motivo, pode -se esperar que a segunda expressão seja mais precisa, porque possui menos operações. No entanto, acho que o .../x**n causa apenas uma perda mínima de precisão (em comparação com outros lugares onde você perde a precisão), a menos que o x**n transborda ou fluxos.

Answer 2

Em teoria, não deve haver diferença - se os valores forem calculados com precisão "infinita".

Kernighan e Plauger estado em seu livro antigo, mas excelente 'Elementos do estilo de programação', este:

Um programador sábio disse uma vez: "Os números de ponto flutuante são como pequenas pilhas de areia; toda vez que você se move, você perde um pouco de areia e ganha um pouco de sujeira".

A divisão tem um pouco menos de operações em geral, o que significa que há um pouco menos de oportunidade de perder areia e ganhar sujeira.

Uma análise detalhada provavelmente exigiria uma olhada nos coeficientes (a, b, c, etc), talvez como o valor de x - o que funciona quando x é enorme pode não funcionar bem quando X está próximo de zero, nem vice -versa.

Answer 3

Infelizmente, as respostas fornecidas estão erradas.

A segunda equação p = (((a/x + b)/x + c)/x + ...) é apenas pior marginal para precisão e muito, muito pior para a velocidade.

Por quê ? Os erros relativos para a multiplicação possuem apenas o termo linear principal e um pequeno termo quadrático. A divisão, em contraste, apresenta termos mais altos, mas muito pequenos (cúbico, quartico):

e = erro relativo, assumido constante para ambos os termos

a*b = a (1+e)B (1+e) = Ab (1+2e+e^2) // multiplicação

a/b = a (1+e)/b (1+e) = a/b (1+e) (1+e+e^2+e^3+... série geométrica) // divisão

Portanto, a divisão é sempre um pouco pior que a multiplicação. Para considerações de velocidade: as divisões são sempre mais lentas que as multiplicações, o fator normal pode variar de 3x - 10x. Portanto, as divisões aninhadas são muito mais lentas que as multiplicações aninhadas se você não calcular o último fator x^n não por pow (), mas por multiplicação aninhada.

O x^n pode ser facilmente calculado por um loop multiplicando o resultado duplo potência = x; para (n-1) potência *= x;

Se você usar o Pow (), esteja ciente de que ele é convenientemente calculado por exponencial e logaritmo, levando muito mais tempo do que o necessário (100X).

Você está ciente de que, embora o erro entre resultado duplo e exato permaneça pequeno, os resultados polinominais são muito sensível a mudanças de x para n's mais altos?! Portanto, se você usar N mais alto, esteja ciente de que suas respostas podem estar totalmente erradas, porque pequenos erros em x são amplificados astronomicamente.