Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Imperative programming (resit) / 1 / a

Use a Double base so that the reciprocal is not truncated by integer division. Repeated multiplication gives the requested linear-work approximation to Euler's number.

def eaLinear(n: Int): Double = {
  require(n > 0)
  val base = 1.0 + 1.0 / n.toDouble
  var i = 0
  var result = 1.0
  while (i < n) {
    result *= base
    i += 1
  }
  result
}

In exact arithmetic over the real numbers, the loop invariant is

0 \leq i \leq n

and

res u lt = ba s e^{i}

. It holds initially, one multiplication establishes the next exponent, and at exit

i = n

gives the specified power. The nonnegative loop variant is

n - i

. There are exactly $n$ loop multiplications, hence

Θ (n)

in asymptotic analysis, and one division to form the base. With floating-point arithmetic, the invariant describes the intended exact result; the actual output has the corresponding rounding errors.

Solution

 0  0

Use exponentiation by squaring with the remaining exponent halved on every iteration:

def eaFast(n: Int): Double = {
  require(n > 0)
  var remaining = n
  var base = 1.0 + 1.0 / n.toDouble
  var result = 1.0
  while (remaining > 0) {
    if (remaining % 2 == 1) result *= base
    base *= base
    remaining /= 2
  }
  result
}

Writing

a = 1 + 1/ n

, the exact-arithmetic loop invariant is

re mainin g \geq 0

and

res u lt ba s e^{re mainin g} = a^{n}

. For an even integer exponent

2 q

, replace the base by its square and the exponent by

q

. For an odd integer exponent

2 q + 1

, first multiply the accumulator by the base and then make the same replacement. Both preserve the product. The loop variant is remaining, which strictly decreases while positive. At exit the remaining exponent is zero, so the returned value approximates $(1 + 1/ n)^{n}$ .

There are