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

Use exponentiation by squaring, retaining the unprocessed exponent in k:Writing $A=1+1/n$, the loop invariant is $k\ge 0$ and $resultbas{e}^k=A^n$. If the old exponent is $2q+b$, $b\in \{0,1\}$, multiplying the accumulator by $bas{e}^b$ and replacing the remaining power by $(bas{e}^2{)}^q$ preserves the invariant. When $q=0$, the unused squaring may be omitted. The nonnegative integer k is a loop variant, since $\lfloor k/2\rfloor <k$ for $k>0$. At exit the remaining power is one, giving $result=e_a(n)$. There are $\lfloor {\log }_{2}n\rfloor +1$ iterations, at most one accumulator multiplication and one squaring per iteration, hence $O(\log n)$ multiplications and constant space.