= Solution
First rearrange the ratios so that the intermediate powers remain moderate:
$$
e_c(n)=(n+1)\left(1+\frac1n\right)^n-n\left(1+\frac1{n-1}\right)^{n-1}.
$$
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>:
``
def ec(n: Int): Double = {
require(n > 1)
val dn = n.toDouble
var x = 1.0 + 1.0 / dn
var y = 1.0 + 1.0 / (dn - 1.0)
var k = n
var l = n - 1
var p = 1.0
var q = 1.0
while (k > 0 || l > 0) {
if (k > 0) {
if ((k & 1) != 0) p *= x
k /= 2
if (k > 0) x *= x
}
if (l > 0) {
if ((l & 1) != 0) q *= y
l /= 2
if (l > 0) y *= y
}
}
(dn + 1.0) * p - dn * q
}
``
With $A=1+1/n$ and $B=1+1/(n-1)$, the <loop invariant> is $k,l\geq0$, $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 \b[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.
Back to article page
