= Solution
\b[Choose the reciprocal-<factorial> summation `eb` for asymptotically high accuracy], counting multiplications and divisions as arithmetic work. For tolerance $\epsilon$, linear powering in part (a)(i) takes $O(\epsilon^{-1})$ multiplications; <binary exponentiation> in part (a)(ii) reduces this to $O(\log(1/\epsilon))$. Part (c) also has $O(\log(1/\epsilon))$ arithmetic work, since its required $n$ grows like $\epsilon^{-1/2}$, though its constants and <cancellation error> differ.
By the <reciprocal-factorial series remainder bound>, the omitted positive tail satisfies
$$
0<e-e_b(n)=\sum_{j=n+1}^{\infty}\frac1{j!}\leq\frac1{(n+1)!}\sum_{r=0}^{\infty}\frac1{(n+2)^r}=\frac{n+2}{(n+1)(n+1)!}.
$$
Thus the <factorial> denominator grows much faster than an exponential in the number of iterations. For $d$ decimal places, setting $\epsilon$ of order $10^{-d}$ gives $n=\Theta(d/\log d)$ by <Stirling's approximation>, rather than $\Theta(d)$ binary-power arithmetic steps. This is a comparison in an exact-arithmetic operation-count model; the stated <Big O notation> does not determine the exact winner for every small tolerance. Taken literally, `eb` uses zero multiplications and only divisions. Fixed <double-precision floating-point format> cannot deliver arbitrarily many correct decimal places, and the precision-dependent cost of <arbitrary-precision arithmetic> is a separate issue.
Back to article page
