Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 1 / b / Solution

Generate each reciprocal factorial from the preceding one, instead of recomputing a factorial for every summand:The loop invariant is $0\le i\le 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 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.