= Solution
Use <exponentiation by squaring>, retaining the unprocessed exponent in `k`:
``
def eaBinary(n: Int): Double = {
require(n > 0)
var base = 1.0 + 1.0 / n.toDouble
var k = n
var result = 1.0
while (k > 0) {
if ((k & 1) != 0) result *= base
k = k / 2
if (k > 0) base *= base
}
result
}
``
Writing $A=1+1/n$, the <loop invariant> is $k\geq0$ and $result\,base^k=A^n$. If the old exponent is $2q+b$, $b\in\{0,1\}$, multiplying the accumulator by $base^b$ and replacing the remaining power by $(base^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 \b[$result=e_a(n)$]. There are $\lfloor\log_2n\rfloor+1$ iterations, at most one accumulator multiplication and one squaring per iteration, hence $O(\log n)$ multiplications and <constant space>.
Back to article page
