= Solution
Generate each reciprocal <factorial> from the preceding one, instead of recomputing a <factorial> for every summand:
``
def eb(n: Int): Double = {
require(n >= 0)
var i = 0
var term = 1.0
var sum = 1.0
while (i < n) {
i += 1
term /= i.toDouble
sum += term
}
sum
}
``
The <loop invariant> is $0\leq i\leq n$, $term=1/i!$, and $sum=\sum_{j=0}^{i}1/j!$. Initially $i=0$ and $0!=1$. The division produces $1/(i+1)!$, which is then added to the previous partial <sum>. The <loop variant> is $n-i$. Consequently \b[the returned value is $e_b(n)$], using exactly $n$ divisions and $n$ additions, no multiplications, and $O(n)$ <time complexity>. The slightly weaker <precondition> also permits the useful zero-term boundary case. For `Double`, small positive terms eventually cease to change `sum` because of <floating-point rounding>.
Back to article page
