Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Imperative programming (resit) / 1 / a / ii

Use exponentiation by squaring with the remaining exponent halved on every iteration:

def eaFast(n: Int): Double = {
  require(n > 0)
  var remaining = n
  var base = 1.0 + 1.0 / n.toDouble
  var result = 1.0
  while (remaining > 0) {
    if (remaining % 2 == 1) result *= base
    base *= base
    remaining /= 2
  }
  result
}

Writing $a=1+1/n$, the exact-arithmetic loop invariant is $remaining\ge 0$ and $resultbas{e}^{remaining}=a^n$. For an even integer exponent $2q$, replace the base by its square and the exponent by $q$. For an odd integer exponent $2q+1$, first multiply the accumulator by the base and then make the same replacement. Both preserve the product. The loop variant is remaining, which strictly decreases while positive. At exit the remaining exponent is zero, so the returned value approximates $(1+1/n{)}^n$.

There are $L=\lfloor {\log }_{2}n\rfloor +1$ iterations, $L$ squarings and one accumulator multiplication for each set bit of $n$: between $L+1$ and $2L$ multiplications. Thus the bound is $\Theta (\log n)$ as $n\to \infty$, or $\Theta (1+\log n)$ including the small case $n=1$. All power variables are Double; no unintended Int squaring occurs.