Polynomial evaluation

Suppose you had to evaluate $5x^4$ $+$ $3x^3$ $+$ $7x^2$ $+$ $2x$ $+$ $9$, given $x=7$. The straightforward approach would sum up $5*x*x*x*x$ $+$ $3*x*x*x$ $+$ $7*x*x$ $+$ $2*x$ $+$ $9$ -- 10 multiplications 4 additions. Although multiplication and division don't generate as much error at a single step as catastrophic cancellation (the operations are done in double precision, and then converted to float), the errors accumulate (and multiplication is computationally expensive). A better approach is to re-write the polynomial using Cramer's rule:

$$((((5x + 3)x + 7)x + 2)x + 9$$

This uses 4 multiplications (the degree of the polynomial) and 4 additions. A small re-arrangement makes a large difference (for a degree 100 polynomial, the first method would use 5050 multiplications versus 100 multiplications if re-arranged).