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

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.

 Ancestors (12)

 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 / a / ii

Solution

 Ancestors (12)

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

 Articles by others on the same topic (0)

 Discussion (0) New discussion