= Solution
Use <Horner's method>, accumulating the high-degree coefficients before the low-degree ones:
``
def eval(x: Double): Double = {
var i = a.length
var value = 0.0
while (i > 0) {
i -= 1
value = a(i) + x * value
}
value
}
``
At each <while loop> head the <loop invariant> is
$$
0\leq i\leq n,\qquad \mathrm{value}=\sum_{j=i}^{n-1}a(j)x^{j-i}.
$$
The initial sum is empty. Decreasing `i` and replacing the accumulator by `a(i) + x * value` extends that sum by one coefficient with the required powers shifted. The <loop variant> is `i`; on exit it is zero, so the accumulator equals $p(x)$. The code uses \b[exactly $n$ <multiplications> and $O(n)$ time], with constant auxiliary space, and also handles the empty coefficient <array> as the zero <polynomial>. Initializing from the last coefficient instead would save one <multiplication> for nonempty <arrays>.
The invariant is an exact-arithmetic specification. With `Double`, each arithmetic operation rounds; consequently the code evaluates the Horner expression in <floating-point arithmetic>, rather than guaranteeing the exact real value for arbitrary coefficients.
Back to article page
