Details

This Demonstration lets you experiment with two direct methods for finding increasingly closer rational approximations of real numbers. Use the "target" menu to choose from the sample targets , , and others. Use the "method" button to select which algorithm to use.

The "increment or " method relies on two simple facts:

1. No fraction can be exactly equal to an irrational target number.

2. Incrementing the numerator of a fraction increases the fraction, while incrementing the denominator decreases the fraction.

Start with and compare it to the target, incrementing either the numerator or the denominator by to generate a (hopefully) closer approximation. As can be seen, the approach is sporadic and slow. For example, the familiar approximation of for is reached after 28 steps.

The iteration is displayed in two ways:

1. In the numerator versus denominator graph, repeatedly incrementing produces a series of vertical dots that approach and then surpass the red "target" line. These are followed by one or more horizontal steps as is incremented. The fraction can be seen by hovering over a dot.

2. The list of fractions separated by high or low arrows indicates whether or was incremented. The graphical representation of this algorithm is a path in taxicab space, moving either northward or eastward one "block" at a time. For each denominator, one numerator results in the closest possible approximation to the target. These cases, referred to as approximants, are shown in bold on the graph, one in each vertical run of points.

In the method "increment only" only approximants are shown, using the optimal numerator for each choice of denominator , determined by rounding to the nearest integer. Approach to the target is still sporadic, but faster than method "increment or ". Two graphs show both the error (bounded by ) and the relative error (as a fraction of ) for the various approximants, with better ones represented by points closer to the horizontal axis.

The gold list, shown below the graphs, is produced by keeping only approximants that are progressively closer to the target. A tantalizing feature of this gold list is that most entries can be formed by taking the mediant of two earlier entries. The mediant of fractions and is

.

Long subsequences in any gold list are repeated mediants of the same two approximants, taking the form

.

(Only the first fraction is used repeatedly to generate the next result in the sequence, effectively weighting its contribution by . In the general case, as , the repeated mediant starts at and approaches .)

See "Related Links" for other Demonstrations that deal with mediants and approximants. See [1] for the derivation of a much faster method of generating the gold list of all approximants to any real target.

Snapshot 1: The famous approximation (correct to three decimal digits), known to Archimedes, is reached at step 28 with the method "increment or ". However, further iteration temporarily moves farther away from the target again.

Snapshot 2: The approximants , , and are equally good according to the error graph, but are seen to be progressively worse on the graph of relative error versus denominator. Here, nonreduced fractions will always be farther from the horizontal axis, and only the first (reduced) one is kept in the gold list. It is surprising to note that all but the first two elements of the gold list are mediants of previous entries.

Snapshot 3: Unreduced approximants of the form become visibly worse on the relative error graph, getting farther from the horizontal axis. However, approximants having a denominator of the form become gradually better, until starting with they are in the gold list, eventually reaching . This "Chinese estimate" for has an amazing seven correct decimal digits. Here, all but the first two gold list entries are repeated mediants, having the form of either

or

.

Snapshot 4: The method "increment only" applied to the golden ratio: , a different irrational target. It is well known that the sequence of fractions formed by dividing successive Fibonacci numbers converges to ; interestingly enough, these are precisely the approximants making up the gold list for this case. For comparison, consider the Fibonacci pair , a rational target close to .

Snapshot 5: Applying these algorithms to a rational target requires only one modification: adding a stop condition in the first method, adding nothing to either numerator or denominator when the target itself is eventually reached. This situation is shown here by vertical bars and repetition of the "approximation" from that point on. The "increment only" algorithm needs no modification, continuing to generate the best possible approximant to the target for the specified denominator. Here the target is the Fibonacci pair , which is very close to the golden ratio.

Reference

[1] R. L. Caviness and K. E. Caviness, Making Pi(e) from Scratch, Rapidly and Memorably [Video]. AMATYC Webinar (Sep 27, 2019). https://www.youtube.com/watch?v=JcBr_v-n6AA.