da vict85 » 13/02/2020, 14:57
Tu stai trasformando \[3\cdot x \cdot x \cdot x \cdot x + 4 \cdot x \cdot x \cdot x + 2 \cdot x \cdot x + 5 \cdot x - 4\] in \[-4 + x \cdot \biggl( 5 + x \cdot \Bigl( 2 + x \cdot \bigl( 4 + x \cdot 3 \bigr) \Bigr) \biggr)\]
Ho esplicitato tutte le somme e i prodotti.
Il primo è equivalente al seguente:
\[\begin{align*}
m_1 &\leftarrow 3 \cdot x \\
m_2 &\leftarrow m_1 \cdot x \\
m_3 &\leftarrow m_2 \cdot x \\
m_4 &\leftarrow m_3 \cdot x \\
& \\
m_5 &\leftarrow 4 \cdot x \\
m_6 &\leftarrow m_5 \cdot x \\
m_7 &\leftarrow m_6 \cdot x \\
& \\
a_1 &\leftarrow m_4 + m_6 \\
& \\
m_8 &\leftarrow 2 \cdot x \\
m_9 &\leftarrow m_5 \cdot x \\
& \\
a_2 &\leftarrow a_1 + m_9 \\
& \\
m_{10} &\leftarrow 5 \cdot x \\
& \\
a_3 &\leftarrow a_2 + m_{10} \\
a_4 &\leftarrow a_3 - 4
\end{align*}\]
Invece, usindo l'algoritmo di Horner hai che:
\[\begin{align*}
m_1 &\leftarrow 3 \cdot x \\
a_1 &\leftarrow m_1 + 4 \\
& \\
m_2 &\leftarrow a_1 \cdot x \\
a_2 &\leftarrow m_2 + 2 \\
& \\
m_3 &\leftarrow a_2 \cdot x \\
a_3 &\leftarrow m_3 + 5 \\
& \\
m_4 &\leftarrow m_3 \cdot x \\
a_4 &\leftarrow m_4 - 4
\end{align*}\]
Nota che per i floating points, è spesso disponibile una operazione chiamata fused multiply–add (FMA). Quindi, per certi versi, si può dire che l'algorigmo di Horner usa 4 FMA.