= Solution
Avoid forming the enormous powers in the original ratios. Put $a=1+1/n$, $b=1+1/(n-1)$ and $k=n-1$; algebra gives
$$
e_c(n)=(n+1)a\,a^k-nb^k.
$$
Use <simultaneous exponentiation by squaring> to compute the two powers with one loop and a shared remaining exponent:
``
def ec(n: Int): Double = {
require(n > 1)
val dn = n.toDouble
val a = 1.0 + 1.0 / dn
val b = 1.0 + 1.0 / (dn - 1.0)
var remaining = n - 1
var u = a
var v = b
var pa = 1.0
var pb = 1.0
while (remaining > 0) {
if (remaining % 2 == 1) {
pa *= u
pb *= v
}
u *= u
v *= v
remaining /= 2
}
((dn + 1.0) * a) * pa - dn * pb
}
``
The exact-arithmetic <loop invariant> is $remaining\geq0$, $pa\,u^{remaining}=a^{n-1}$ and $pb\,v^{remaining}=b^{n-1}$. The <even integer> and <odd integer> cases preserve both equalities in parallel. The <loop variant> is `remaining`. On termination, the displayed expression is exactly the desired approximation in the ideal arithmetic model. For $L=\lfloor\log_2(n-1)\rfloor+1$, the loop uses at most $4L$ multiplications, followed by three more: \b[$O(\log n)$ multiplications and one loop].
Converting `n` to `Double` before adding one also avoids overflowing `n + 1` at `Int.MaxValue`. The algebra avoids power overflow but does not remove <catastrophic cancellation>: the final subtraction combines quantities of order $n e$ to obtain a result of order $e$. For sufficiently large $n$, <floating-point rounding> can outweigh the mathematical truncation error. For example, at `n == 1000000` this `Double` computation returns approximately \b[`2.7180521293`], although the exact formula is approximately \b[`2.71828182845916`]. Arbitrarily many requested decimal digits require increased arithmetic precision, not simply a larger `Int` argument.
Back to article page
