2 ms·
That article is a truly marvelous article and very worth reading for anyone interested in either continued fractions or rational approximations. For those who
by jostylr 3y ago
That article is a truly marvelous article and very worth reading for anyone interested in either continued fractions or rational approximations.
For those who are curious, a simple algorithm for generating these good approximations and continued fractions is to take the mediant of a Farey pair that enclose the given number, such as [3/1, 4/1], here 7/2, and then choose the sub-interval that contains the desired number. Repeat as desired. This first step has [3/1, 7/2] as the next interval to look at as 3/1 < 3.213432 < 7/2. When doing this to generate the continued fraction representation, start with the nominal interval [0/1, 1/0].
A few steps:
0/1 : 1/1 : 1/0 R
1/1 : 2/1 : 1/0 R
2/1 : 3/1 : 1/0 R
3/1 : 4/1 : 1/0 L
3/1 : 7/2 : 4/1 L
3/1 : 10/3 : 7/2 L
3/1 : 13/4 : 10/3 L
3/1 : 16/5 : 13/4 R
16/5 : 29/9 : 13/4 L
16/5 : 45/14 :29/9 L
16/5 : 61/19 : 45/14 R
61/19 : 106/33 : 45/14 R
...
The number 106/33 is 3.2121... and is generated by easy computation of the mediants.
Each time the direction of selection is changed, this results in having an ultra-best approximation. If we count the number of steps in between the switches, we get the continued fraction representation: [3; 4, 1, 2, ...].
This is also related to the Stern-Brocot tree, for those interested.
Playing around with these ideas led me to the idea of defining a real number as a number that, given a rational interval, says Yes or No depending on whether it ought to be in that interval. To define the space of such objects, I used properties that the Yes/No answers have to satisfy. The key property is that if you split a Yes interval into two pieces, one of the pieces should be Yes and the other No (unless the splitting point is the real number).
If curious for details, my paper repository on this matter is at https://github.com/jostylr/Reals-as-Oracles https://github.com/jostylr/Reals-as-Oracles where I not only prove that it all works out as it should, but also give an example of doing continued fraction arithmetic in section 7.9 of the main paper for those who just love continued fractions.