To find a rational with low denominator near a given real, use continued fractions

Quick description

Suppose that you are given a real number, to many significant figures, told that it is close to a rational with small denominator, and asked to find that rational. Can this be done efficiently (where "efficient" means that you can identify the rational $p/q$ in a time that depends polynomially on the number of digits of $q$ )? Yes it can, with the help of continued fractions.

Prerequisites

Elementary number theory, continued fractions.

Example 1

Suppose you are told that the number $2.571439$ is very close to a fraction $p/q$ such that $q<20$ . How can you find this fraction? For numbers this small, trial and error would work fine. (For each $q$ less than $20$ , one could find the $p$ that makes $p/q$ closest to $2.571439$ and wait until you hit it almost exactly.) But for larger numbers, trial and error would take a hopelessly long time.

There is a simple method for solving this computational problem. First, let us imagine that the number in question actually equals $p/q$ . Then we can express $p/q$ as a continued fraction, which takes a time that is at worst proportional to the number of digits of $q$ (assuming that $p$ and $q$ are of roughly comparable size). For example, if the number were $17/13$ (but we didn't know that) then we would write it as $1+4/13=1+1/(3+1/4)$ . But then we note that if our number is merely very close to $17/13$ , then we will write it as $1+1/(3+1/\theta)$ , where $\theta$ is very close to $4$ . At that point, we recognise that we are very close to the rational $17/13$ .

In our example, we see that

$2.571439\approx 2+1/1.749968\approx 2+1/(1+1/1.33339)\approx 2+1/(1+1/(1+1/2.99949)),$

at which point we recognise that the original fraction was very close to $2+1/(1+1/(1+1/3))=2+1/(1+3/4)=18/7$ .

General discussion

This method plays an important role in Shor's quantum algorithm for factorizing, since the procedure outputs a real number that is close to a rational and one needs an efficient way of finding the denominator of that rational.