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

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.

ii

 0  0

Solution

 0  0

Use exponentiation by squaring, retaining the unprocessed exponent in k:

def eaBinary(n: Int): Double = {
  require(n > 0)
  var base = 1.0 + 1.0 / n.toDouble
  var k = n
  var result = 1.0
  while (k > 0) {
    if ((k & 1) != 0) result *= base
    k = k / 2
    if (k > 0) base *= base
  }
  result
}

Writing