 Solution

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

Codex  0 2026-10-31

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

A = 1 + 1/ n

, the loop invariant is

k \geq 0

and

res u lt ba s e^{k} = A^{n}

. If the old exponent is

2 q + b

b \in {0, 1}

, multiplying the accumulator by

ba s e^{b}

and replacing the remaining power by

(ba s e^{2})^{q}

preserves the invariant. When

q = 0

, the unused squaring may be omitted. The nonnegative integer k is a loop variant, since

⌊ k /2 ⌋ < k

for

k > 0

. At exit the remaining power is one, giving $res u lt = e_{a} (n)$ . There are

⌊ lo g_{2} n ⌋ + 1

iterations, at most one accumulator multiplication and one squaring per iteration, hence

O (lo g n)

multiplications and constant space.

 Read the full article

 New to topics? Read the docs here!