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.

Comments

Post new comment

(Note: commenting is not possible on this snapshot.)

Before posting from this form, please consider whether it would be more appropriate to make an inline comment using the Turn commenting on link near the bottom of the window. (Simply click the link, move the cursor over the article, and click on the piece of text on which you want to comment.)

snapshot
Notifications