Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 1 / b

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.

 Ancestors (11)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 1 / b

Solution

 Ancestors (11)

 Discussion (0)  Subscribe (1) New discussion

 Articles by others on the same topic (0)

 Discussion (0) New discussion