Muller's Recurrence
The recurrence devised by Jean-Michel Muller[1] and described in a slightly modified form by William Kahan in a 2006 monograph[2] provides an interesting example of how the finite precision of floating point arithmetic can lead to wildly incorrect results in some circumstances.
Consider the function $$ E(y, z) = 108 - \frac{815 - \frac{1500}{z}}{y} $$ and define the recurrence $x_{n+1} = E(x_n, x_{n-1})$, with initial values $x_0=4, x_1=4.25$. Does this recurrence have a limit (that is, does $x_n \rightarrow L$ for some finite $L$ as $n\rightarrow\infty$), and if so what is it? The mathematical analysis described below demonstrates that the limit does exist and that $L=5$. A numerical approach would be to calculate $x_n$ for increasing $n$ until $|x_n - x_{n-1}| < \epsilon$, for some tiny value of $\epsilon$. This can be implemented with floating point arthimetic, and the recurrence does indeed seem to converge by about $n=80$. However, it converges on the wrong limit: $L=100$.
Python has a library module, fraction for exact rational arithmetic, and this can be used to find the correct limit. The code below demonstrates this.; the output columns are the rational arithmetic ("exact") result, the naive floating point implementation result, and the output of a more numerically-stable floating point algorithm derived below.
