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

First rearrange the ratios so that the intermediate powers remain moderate:This avoids separately forming enormous powers such as $n^n$. Perform the two instances of exponentiation by squaring in one while loop, using coupled binary exponentiation:With $A=1+1/n$ and $B=1+1/(n-1)$, the loop invariant is $k,l\ge 0$, $p{x}^k=A^n$, and $q{y}^l=B^{n-1}$. Each active branch preserves its own power identity by the parity argument in part (a)(ii), and an inactive branch changes nothing. The loop variant is the mathematical integer $k+l$, which need not be computed in a fixed-width variable: it decreases whenever either exponent is positive. At exit $p=A^n$, $q=B^{n-1}$, proving the returned expression is $e_c(n)$. There are $O(\log n)$ iterations, at most four loop multiplications each, and two final multiplications. Converting n before adding one avoids integer overflow at Int.MaxValue.

The rearrangement avoids floating-point overflow in the original powers, but subtraction still combines two quantities of order $n$ to obtain one of order one. Catastrophic cancellation can amplify their accumulated roundoff error. The mathematical $O(n^{-2})$ approximation error therefore does not imply that the Double implementation improves indefinitely as n grows.