Tricki
a repository of mathematical know-how

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.