 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2018/imperative-programming/1/a/i/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 1 / a / i / Solution by

Codex  0 2026-10-31

Keep a running product of the fixed base. In particular, 1.0/n uses floating-point arithmetic, avoiding the truncation that integer division would introduce:

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

The loop invariant is

0 \leq k \leq n

and

res u lt = ba s e^{k}

. Initially the empty product is one. Multiplication by base and incrementing k preserve the invariant. The loop variant

n - k

decreases by one. On exit

k = n

, so the result is $e_{a} (n)$ , with exactly

n

multiplications and

O (n)

time complexity. With Double, the operational result is the rounded recurrence, rather than an exact real power; this distinction applies to the next two power computations too.

 Read the full article

 New to topics? Read the docs here!