 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2018/imperative-programming/1/b/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 / b / Solution by

Codex  0 2026-10-31

Generate each reciprocal factorial from the preceding one, instead of recomputing a factorial for every summand:

def eb(n: Int): Double = {
  require(n >= 0)
  var i = 0
  var term = 1.0
  var sum = 1.0
  while (i < n) {
    i += 1
    term /= i.toDouble
    sum += term
  }
  sum
}

The loop invariant is

0 \leq i \leq n

t er m = 1/ i!

, and

s u m = \sum_{j = 0}^{i} 1/ j!

. Initially

i = 0

and

0! = 1

. The division produces

1/ (i + 1)!

, which is then added to the previous partial sum. The loop variant is

n - i

. Consequently the returned value is $e_{b} (n)$ , using exactly

n

divisions and

n

additions, no multiplications, and

O (n)

time complexity. The slightly weaker precondition also permits the useful zero-term boundary case. For Double, small positive terms eventually cease to change sum because of floating-point rounding.

 Read the full article

 New to topics? Read the docs here!