Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Imperative programming (resit) / 1 / d

Use the reciprocal-factorial sum for increasing accuracy. Let $d$ be the requested number of decimal places and use absolute error tolerance proportional to $10^{-d}$. Expanding $\log (1+1/n)$ gives $e_a(n)=e-e/(2n)+O(n^{-2})$ and $e_c(n)=e+e/(24n^2)+O(n^{-3})$, so these are genuine first nonzero error orders. The first approximation needs $n$ of order $10^d$. Even its fast implementation therefore uses $\Theta (d)$ multiplications, while the linear version uses exponentially many in $d$. The third approximation needs $n$ of order $10^{d/2}$, but its fast powering still uses $\Theta (d)$ multiplications, with two parallel accumulators and a cancellation-prone subtraction.

For the Taylor series sum, Stirling's formula gives $\log (n!)=\Theta (n\log n)$, so a sufficient term count grows as $n=\Theta (d/\log d)$. Its divisions therefore grow more slowly than the multiplication counts of either fast-power alternative. More concretely, its positive tail satisfiesThe first omitted term also gives a lower bound $1/(n+1)!$. This is the reciprocal-factorial series remainder bound, supplying an explicit stopping certificate rather than relying only on Big O notation. It follows by bounding every successive tail denominator factor below by $n+2$.

The sum also avoids subtraction of nearly equal large values and has small positive terms, making it numerically preferable. For a particular small accuracy request, constants and actual term counts may be compared directly; an asymptotic error bound alone does not prove a universal finite-input operation ranking. With ordinary Double, sufficiently many tiny positive terms stop changing the rounded sum, so beyond machine precision a higher-precision version is necessary regardless of the formula.