Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming / 1 / a / 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 isThe 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 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.