= Solution
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\geq0$ and $result\,base^{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 \b[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.
Back to article page
