= Solution
Use a `Double` base so that the reciprocal is not truncated by <integer division>. Repeated multiplication gives the requested linear-work approximation to <Euler's number>.
``
def eaLinear(n: Int): Double = {
require(n > 0)
val base = 1.0 + 1.0 / n.toDouble
var i = 0
var result = 1.0
while (i < n) {
result *= base
i += 1
}
result
}
``
In exact arithmetic over the <real numbers>, the <loop invariant> is $0\leq i\leq n$ and $result=base^i$. It holds initially, one multiplication establishes the next exponent, and at exit $i=n$ gives the specified power. The nonnegative <loop variant> is $n-i$. \b[There are exactly $n$ loop multiplications], hence $\Theta(n)$ in <asymptotic analysis>, and one division to form the base. With <floating-point arithmetic>, the invariant describes the intended exact result; the actual output has the corresponding rounding errors.
Back to article page
