6.4: An Application

Last updated
Save as PDF

Page ID: 8855

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Consider the following problem which may be of certain practical interest. Assume that we calculate certain quantity using a computer. Also assume that we know in advance that the quantity in question is a rational number. The computer returns a decimal which has high accuracy and is pretty close to our desired answer. How to guess the exact answer?

To be more specific consider an example.

Assume that the desired answer is \[\frac{123456}{121169}\] and the result of computer calculation with a modest error of \(10^{-15}\) is \[\begin{array}{l} \alpha = 123456/121169 + 10^{-15} = \\ 1.01887446459077916933374047817511079566555802226642127937013592 \\ 5855623137931319066757999158200529838490042832737746453300761745 \\ 9911363467553582186862976503891259315501489654944746593600673439576129207 \end{array}\] with some two hundred digits of accuracy which, of course come short to help in guessing the period and the exact denominator of \(121169\).

Solution. Since \(123456/121169\) is a good (just in a naive sense) approximation to \(\alpha\), it should be among its convergents. This is not an exact statement, but it offers a hope! We have \[\alpha = [1; 52, 1, 53, 2, 4, 1, 2, 1, 68110, 4, 1, 2, 106, 22, 3, 1, 1, 10, 2, 1, 3, 1, 3, 4, 2, 11].\]

We are not going to check all convergents, because we notice the irregularity: one element, \(68110\) is far more than the others. In order to explain this we use the left inequality from Theorem [inequ] together with the formula ([main]). Indeed, we have an approximation of \(\alpha\) which is unexpectedly good: \(\vert \alpha - p_k/q_k \vert\) is very small (it is around \(10^{-15}\)) and with a modest \(q_k\) too. We have \[q_k(q_{k+1} + q_k) = q_k(a_{k+1} q_k + q_{k-1}) = q_k^2(a_{k+1} + q_{k-1}/q_k)\] and \[\left\vert \alpha - \frac{p_k}{q_k} \right\vert \geq \frac{1}{q_k^2(a_{k+1} + q_{k-1}/q_k)}.\] It follows that \(1/q_k^2(a_{k+1} + q_{k-1}/q_k)\) is small (smaller than \(10^{-15}\)) and therefore, \(a_{k+1}\) should be big. This is exactly what we see. Of course, our guess is correct: \[\frac{123456}{121169} = [1, 52, 1, 53, 2, 4, 1, 2, 1].\]

In this way we conclude that in general an unexpectedly big element allows to cut the continued fraction (right before this element) and to guess the exact rational quantity. There is probably no need (although this is, of course, possible) to quantify this procedure. I prefer to use it just for guessing the correct quantities on the spot from the first glance.

Contributors and Attributions

Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.