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

Choose the reciprocal-factorial summation eb for asymptotically high accuracy, counting multiplications and divisions as arithmetic work. For tolerance $ϵ$, linear powering in part (a)(i) takes $O({ϵ}^{-1})$ multiplications; binary exponentiation in part (a)(ii) reduces this to $O(\log (1/ϵ))$. Part (c) also has $O(\log (1/ϵ))$ arithmetic work, since its required $n$ grows like ${ϵ}^{-1/2}$, though its constants and cancellation error differ.

By the reciprocal-factorial series remainder bound, the omitted positive tail satisfiesThus the factorial denominator grows much faster than an exponential in the number of iterations. For $d$ decimal places, setting $ϵ$ 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.