Valutazione polinomi: virgola mobile o problema di ottimizzazione?

Question

Da Numerical Recipes:

Partiamo dal presupposto che si sa mai abbastanza per valutare un polinomio in questo modo: p = c [0] + c [1] * x + c [2] * x * x + c [3] * x * x * x + c [4] * x * x * x * x; ...

Ovviamente non so abbastanza ...

È questo solo un problema di ottimizzazione o è anche una questione di aritmetica in virgola mobile e perché?

Answer 1

È possibile calcolare p=c[0]+c[1]*x+c[2]*x*x+c[3]*x*x*x+c[4]*x*x*x*x; come:

p=c[0]+(c[1]+(c[2]+(c[3]+c[4]*x)*x)*x)*x; 

ci sono molte meno moltiplicazioni nel secondo modulo. Questa seconda forma è chiamata "Horner's".

Questo è solo un problema di ottimizzazione o è anche un problema aritmetico in virgola mobile e perché?

Si tratta principalmente di un problema di ottimizzazione. Tuttavia, alcuni processori moderni hanno un'operazione a virgola mobile per eseguire una moltiplicazione e un'aggiunta in una singola istruzione senza arrotondamenti intermedi per la moltiplicazione, e mentre il vantaggio che la maggior parte dei programmatori vede è ancora l'ottimizzazione, significa anche che il risultato è più accurato .

La forma di Horner è molto ben adattata per il calcolo con questo fused-multiply-add instruction.

---

Infine, vorrei sottolineare per ragioni di completezza che i processori moderni possono essere ancora più efficiente se il polinomio viene presentato loro in una forma con più parallelismo. Si veda ad esempio Estrin's scheme o this blog post per una spiegazione con i piedi per terra. Il tuo libro non allude al requisito di conoscere lo schema di Estrin. Allude solo all'obbligo di conoscere lo schema di Horner.