A fast computation of the best \(k\)-digit rational approximation to a real number (Q346908): Difference between revisions

Suppose the continued fraction expansion of a real number \(\alpha\) is known to be of the form \([a_0;a_1,a_2,\ldots]=a_0+\sum_{k=1}^\infty \frac{~1~|}{|\,a_k}\) with all \(a_k\) integers, \(a_0\geq0\), \(a_k>0\), \(k\geq 1\). The idea is to find the best rational approximant (\(bra_k\)) whose numerator (but which can be adapted for the denominator) has at most \(k\) digits. It is known that the \(bra_k\) is either a convergent \(s_n=[a_0;a_1,\dots,a_n]\) or a semiconvergent \(s_{n,m}=[a_0;a_1,\ldots,a_n,m]\) with integer \(m\in[1,a_{n+1})\). To make such a decision, also pseudoconvergents, forming a set of Farey fractions are used: \(\tilde{s}_{n,m}=[a_0;a_1,\ldots,a_{n-1},a_n-1,m]\). The \(bra_k\) with exactly \(k\) digits will be either a convergent, a semiconvergent or a pseudoconvergent. The \(s_n\) approximate \(\alpha\) alternatingly from above and below. And with \(m\) increasing, the \(s_{n,m}\) is a sequence monotonically varying between \(s_{n-1}\) and \(s_{n+1}\) while \(\tilde{s}_{n,m}\) is monotonically moving towards \(s_n\). With these properties a very efficient algorithm is given that defines the \(bra_k\) with \(k\) strictly equal to the number of digits or not. Also an error estimate is given for this \(bra_k\).