Repeated Mediants Lead to Iterative Brackets

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

This Demonstration shows initial steps in the iterative bracket method for creating the gold list of increasingly close rational approximants of a given real number target. (See the Details for definitions and examples.)

[more]

Select the target and iteration step. The initial bracket is the pair of fractions and with smallest possible denominators such that both approximate the target and lie to its left and right. (We always take ; in the initial bracket, .) The number line shows the sequence of repeated mediants of the bracket elements, monotonically approaching the target from the side, before crossing over to the side at the mediant.

Use the interval sliders to set the focus to any part of the sequence. All repeated mediants between the and the are guaranteed to be in the gold list, shown with darker points and labels. Below the number line is a summary of the important values for each iteration: the repeated mediants most closely bracketing the target become the bracket elements for the next iteration step.

Options toggle the display of the bracket's alternating orientation and its width, which decreases by a factor of at least 2, but is generally much faster.

The lower-right panel shows either the whole gold list up to the current step or only the newly added entries. For comparison, you can choose to see the continued fraction representation of the target.

[less]

Contributed by: R. Lewis Caviness and Kenneth E. Caviness (December 2020)
Open content licensed under CC BY-NC-SA


Snapshots


Details

The iterative bracket method used here is based on several related concepts; you can experiment with all of them.

An approximant of a real number target is a rational approximation to , with the best choice of numerator for the given denominator. For example, if , then 22 is the best numerator for the denominator 7.

The list of approximants of , with every integral denominator, starts as:

.

This list reduces to the gold list by excluding all entries that are not closer to the target than previous entries: . For example, and are dropped from the list because they are not closer to than ; similarly these are dropped because they are not closer to than , and so on.

The original motivation for the iterative bracket algorithm was this serendipitous observation: generally, the fractions formed from differences in numerators and denominators of successive gold list entries are themselves previous gold list entries! In the case of , these fractional differences are . Beyond the runs of and , we also noticed a run of , an even better approximation to .

Of course, fractions are not added or subtracted this way, as generations of basic math teachers have explained to their students. But surprisingly, in most cases each new gold list element is the mediant, also known as the Farey mean or "freshman sum", of earlier entries. Many consecutive subsequences of the gold list consist of weighted mediants of fractions with smaller denominators.

Definition: The mediant of fractions and is .

Definition: The weighted mediant of fractions and with weighting factor is , where the nonnegative integer weights the earlier fraction , the one with the smaller denominator.

Example: For , the subsequence is formed by four weighted mediants of and : .

Definition: The nonnegative fraction pair forms a bracket for the positive real-number target if and only if or . By convention, the earlier fraction, the one with the smaller denominator, is written first, that is, , where . Each bracket is associated with an interval, either or , where here the usual convention lists the interval endpoints in ascending order. The real number is considered to lie inside the bracket if it is in the corresponding interval. The length of bracket is given by . For irrational targets, all intervals are open. For a rational target, however, it is possible for the target to equal the later fraction. (All the targets listed are irrational with the possible exception of Euler .)

Example: The first bracket for is ; the second, generated iteratively from the first, is ; the third is .

The number line plot shows the sequence of weighted mediants formed by a bracket , consisting of two fractions on opposite sides of the target. The weighted mediants move monotonically from , past the target, toward (the one with the smaller denominator). Coloring indicates which are in the gold list, and arrows show which two are closest to the target, bracketing it more closely. Below the number line, on the left, a table provides information regarding each iterative bracket; and on the right, optionally, you can choose to display either newly added elements of the gold list or the entire gold list.

Snapshot 1: The first bracket of approximants of , , together with calculated values of and , allowing identification of , and (weighted mediants with weight factors , and ) as three additional gold list elements. On the number line, the current and next brackets are identified by parentheses symbols, colored blue or green, respectively. The target is identified by the red point and arrow.

Snapshot 2: The second bracket of approximants of , , together with calculated values of and , allowing identification of 10 additional gold list elements, including the well-known "Chinese estimate" of , . The first six weighted mediants, shown in gray, although approaching , are farther from it than , and are therefore not in the gold list. Adjust the interval sliders to focus on later weighted mediants. In the table of bracket information, bracket width is shown to be rapidly decreasing.

Snapshot 3: Step 6 in the iterative bracket method with target , a case of intermittent approach, some steps dividing the bracket width by 2, some far more. Continued fraction coefficients and convergents are shown.

Snapshot 4: Step 15 in the iterative bracket method applied to the golden ratio, the case of slowest approach, with each step dividing the bracket width by slightly more than 2. Here , allowing the addition of only one new gold list entry at each step.

Iterative bracket algorithm, for a target :

In the following, let and be the functions for rounding and taking the fractional part; let and be the floor and ceiling functions.

1. The earlier element of the initial bracket, is . The later element is the first approximant on the other side of . So by definition, lies between the bracket elements. Write the bracket as , listing first the earlier element, which has the the smaller denominator.

2. For any bracket , define , where . The next bracket consists of the and repeated mediants of the current bracket, that is, . Each successive iteration more tightly brackets the target, generally decreasing the bracket width by at least a factor of 2, often much more. Note: After is found, all further ones can also be generated iteratively by an equivalent condition: . (This is reminiscent of the way continued fraction coefficients are found.)

3. For any bracket, define , where . All weighted mediants between the and the are automatically in the gold list. In addition, the mediant of the current bracket (which becomes the later element of the next bracket, ) is in the gold list if and only if . These steps are sufficient to generate the entire gold list for any arbitrary target .

An interesting side note: The -sequence generated as part of the iteration process specified above becomes identical (after at most two terms) to the continued fraction coefficients for all targets considered. A column showing the beginning of the continued fraction representation can be toggled on/off, and with it the sequence of convergents. These convergents, which are rational truncations of the continued fraction, closely mirror the sequence of entries from the iterative bracket algorithm.

Other Demonstrations dealing with mediants and gold list approximants are listed under "Related Links". See [1] for a derivation of the algorithm, proofs of these statements and a comparison of the ultra-rapid iterative bracket method with the painfully slow method based on the gold list definition: test each approximant and discard or save. A similar approach, considered in [2], uses lower and upper rational bounds to bracket the values of logarithms.

Reference

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

[2] T. Apostol and M. Mnatsakanian, "Good Rational Approximations to Logarithms," College Mathematics Journal, 32(3), 2001 pp. 172–179. https://doi.org/10.1080/07468342.2001.11921872.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send