= Solution
Keep a running <product> of the fixed base. In particular, `1.0/n` uses <floating-point arithmetic>, avoiding the truncation that <integer division> would introduce:
``
def eaLinear(n: Int): Double = {
require(n > 0)
val base = 1.0 + 1.0 / n.toDouble
var k = 0
var result = 1.0
while (k < n) {
result *= base
k += 1
}
result
}
``
The <loop invariant> is $0\leq k\leq n$ and $result=base^k$. Initially the empty <product> is one. Multiplication by `base` and incrementing `k` preserve the <invariant>. The <loop variant> $n-k$ decreases by one. On exit $k=n$, so \b[the result is $e_a(n)$], with exactly $n$ multiplications and $O(n)$ <time complexity>. With `Double`, the operational result is the rounded recurrence, rather than an exact real power; this distinction applies to the next two power computations too.
Back to article page
