This site is supported by donations to The OEIS Foundation.
User:Daniel Mondot/Continued Fraction
Contents
Process giving a series of convergent fraction via the Continued Fraction method
Any real number, rational or irrational (but it can be extended to complex numbers as well), can be expressed as a continued fraction of the form:
where a_0, a_1, ... a_i can be any natural numbers.
Let's take the number 2.718281828... as an example to show the process for finding the continued fraction:
Finding the simple continued fraction for Step Real
NumberInteger
partremainder
partReciprocal
of r1 2 3 4 5 Continued fraction form for
Which can be written: :
From this we can generate a series of fractions convergents:
Converting the continued fraction to a series of converging fractions Step Partial Continued
FractionSimplify Simplify
againSimplify
furtherSimplify
furtherSimplify
furtherValue Absolute Error Error (%) 1 2 3 4 5
So, for , the series of convergent fractions obtained from the continued fraction is:
Note that the error falls alternatively above and below the target number.
Brute force
A simple technique would be to try every possible integer denominators and check which ones gives increasingly better results:
Denom- inator |
Times | Rounded to |
resulting fraction |
Value | Error |
---|---|---|---|---|---|
1 | 3.14159265... | 3 | 3 / 1 | 3.00000000... | .141592653... |
2 | 6.28318530... | 6 | 6 / 2 | 3.00000000... | .141592653... |
3 | 9.42477796... | 9 | 9 / 3 | 3.00000000... | .141592653... |
4 | 12.5663706... | 13 | 13 / 4 | 3.25000000... | .108407346... |
5 | 15.7079632... | 16 | 16 / 5 | 3.20000000... | .058407346... |
6 | 18.8495559... | 19 | 19 / 6 | 3.16666666... | .025074013... |
7 | 21.9911485... | 22 | 22 / 7 | 3.14285714... | .001264489... |
8 | 25.1327412... | 25 | 25 / 8 | 3.12500000... | .016592653... |
9-55 | skipped... | not better | |||
56 | 175.929188... | 176 | 176 / 56 | 3.14285714... | .001264489... |
57 | 179.070781... | 179 | 179 / 57 | 3.14035087... | .001241776... |
58-63 | skipped... | not better | |||
64 | 201.061929... | 201 | 201 / 64 | 3.14062500... | .000967653... |
65-70 | skipped... | not better | |||
71 | 223.053078... | 223 | 223 / 71 | 3.14084507... | .000747583... |
72-77 | skipped... | not better | |||
78 | 245.044226... | 245 | 245 / 78 | 3.14102564... | .000567012... |
79-84 | skipped... | not better | |||
85 | 267.035375... | 267 | 267 / 85 | 3.14117647... | .000416183... |
86-91 | skipped... | not better | |||
92 | 289.026524... | 289 | 289 / 92 | 3.14130434... | .000288305... |
93-98 | skipped... | not better | |||
99 | 311.017672... | 311 | 311 / 99 | 3.14141414... | .000178512... |
100-105 | skipped... | not better | |||
106 | 333.008821... | 333 | 333 / 106 | 3.14150943... | .000083219... |
107-112 | skipped... | not better | |||
113 | 354.999969... | 355 | 355 / 113 | 3.14159292... | .000000266... |
In green are fractions that are given by the continued fraction process. They give a smaller error than previous fractions.
In yellow are fractions that are not given by the continued fraction process. They also give a smaller error than previous fractions.
In red are fractions that give an equal or worse result that the previous best fraction.
Of course to get any significant number of digits, brute-forcing is not the answer.
So, we need a process that will give us the fractions in the the yellow and green lines, directly.
Technique equivalent to the continued fraction process
If we look at the fractional part of the value of the denominator times , we notice that on the green lines, it gets closer and closer to .000... or .999... with each new green line.
Furthermore, the absolute value of the difference between that number and the closest integer gets smaller with each new number on the green lines.
So we can make up a test to see if the resulting fraction will be in a green box or not, but to avoid testing every possible denominators, we need a way to skip most of them.
Ideally, we need a denominator such as that number times , let's call it X, is near-integer, i.e. when we round it to an integer, the change is minimal.
On the first green line, the distance between X and the nearest integer (or positive offset) is 0.14159265... slightly above 0.
On the second green line, the distance between X and the nearest integer (or negative offset) is 21.9911485-22... = -0.0088514..., slightly below zero.
So, we can take the last best denominator, i.e. 7, and add the second best denominator, i.e. 1. we get 8.
A denominator of 8 isn't very good to give us a better fraction (it's red on the above table), but it is very good because we now have a better positive offset of 0.1327412...
When we repeat the process, the next denominator to try is now 7 (best negative offset) + 8 (best positive offset) = 15. There is no need to try any other denominator between 8 and 15.
A denominator of 15 doesn't give us a better fraction, but again we get a better positive offset.
The next denominator to try is now 7 (best negative offset) + 15 (best positive offset) = 22, and again we get a better positive offset.
The next denominator to try is now 7 (best negative offset) + 22 (best positive offset) = 29, and again we get a better positive offset.
The next denominator to try is now 7 (best negative offset) + 29 (best positive offset) = 36, and again we get a better positive offset.
The next denominator to try is now 7 (best negative offset) + 36 (best positive offset) = 43, and again we get a better positive offset.
The next denominator to try is now 7 (best negative offset) + 43 (best positive offset) = 50, and again we get a better positive offset.
The next denominator to try is now 7 (best negative offset) + 50 (best positive offset) = 57, and again we get a better positive offset.
The next denominator to try is now 7 (best negative offset) + 57 (best positive offset) = 64, and again we get a better positive offset.
The next denominator to try is now 7 (best negative offset) + 64 (best positive offset) = 71, and again we get a better positive offset.
The next denominator to try is now 7 (best negative offset) + 71 (best positive offset) = 78, and again we get a better positive offset.
The next denominator to try is now 7 (best negative offset) + 78 (best positive offset) = 85, and again we get a better positive offset.
The next denominator to try is now 7 (best negative offset) + 85 (best positive offset) = 92, and again we get a better positive offset.
The next denominator to try is now 7 (best negative offset) + 92 (best positive offset) = 99, and again we get a better positive offset.
The next denominator to try is now 7 (best negative offset) + 99 (best positive offset) = 106.
This time not only we get a better positive offset, but this positive offset is better than the negative one: .008821...(from 106 ) is smaller than 0.0088514 (from 7 )
The next denominator to try is now 7 (best negative offset) + 106 (best positive offset) = 113, and now we get a new best negative offset: 0.000030...
The next denominator to try is now 113 (best negative offset) + 106 (best positive offset) = 219, and again we get a better positive offset.
The next denominator to try is now 113 (best negative offset) + 219 (best positive offset) = 332, and again we get a better positive offset.
We will successively try denominators of 219, 332, 445, 558, 671, 784, ... each time adding 113, until we reach 33102, and then 33215.
Then we will keep adding 33102 to 33215, etc...
At each step of the process, we add the denominator for the lowest positive offset to the denominator of the lowest negative offset to get a new denominator.
We test if this denominator gives us a better negative or positive offset, and replace it.
At each step, if the absolute value of the new offset is smaller then previous best absolute offset, we record the corresponding fraction.
The result of this process gives us the same fractions given by the continued fraction process, but we haven't done any single division to obtain them.
Extending the technique to get all fractions
Now, at each step, if, instead of looking at the absolute value of the new offset, we actually calculate the value of the resulting fraction, look at the error, and record a new fraction when the absolute error is better than the previous one, we get all the increasingly better fractions (lines in green and yellow in the above table. This gives us this table of fractions:
Denom- inator |
Times | Rounded to |
resulting fraction |
Value | Error | Denominator best under |
Numerator best under |
---|---|---|---|---|---|---|---|
1 | 3.14159265358979323... | 3 | 3 / 1 | 3.00000000000000000... | .141592653589793238... | ||
4 | 12.5663706143591729... | 13 | 13 / 4 | 3.25000000000000000... | .108407346410206761... | yes | |
5 | 15.7079632679489661... | 16 | 16 / 5 | 3.20000000000000000... | .058407346410206761... | ||
6 | 18.8495559215387594... | 19 | 19 / 6 | 3.16666666666666666... | .025074013076873428... | ||
7 | 21.9911485751285526... | 22 | 22 / 7 | 3.14285714285714285... | .001264489267349618... | yes | |
57 | 179.070781254618214... | 179 | 179 / 57 | 3.14035087719298245... | .001241776396810782... | ||
64 | 201.061929829746767... | 201 | 201 / 64 | 3.14062500000000000... | .000967653589793238... | ||
71 | 223.053078404875319... | 223 | 223 / 71 | 3.14084507042253521... | .000747583167258027... | ||
78 | 245.044226980003872... | 245 | 245 / 78 | 3.14102564102564102... | .000567012564152212... | yes | |
85 | 267.035375555132425... | 267 | 267 / 85 | 3.14117647058823529... | .000416183001557944... | ||
92 | 289.026524130260977... | 289 | 289 / 92 | 3.14130434782608695... | .000288305763706281... | ||
99 | 311.017672705389530... | 311 | 311 / 99 | 3.14141414141414141... | .000178512175651824... | yes | |
106 | 333.008821280518083... | 333 | 333 / 106 | 3.14150943396226415... | .000083219627529087... | ||
113 | 354.999969855646635... | 355 | 355 / 113 | 3.14159292035398230... | .000000266764189062... | yes | yes |
16604 | 52163.0044202049269... | 52163 | 52163 / 16604 | 3.14159238737653577... | .000000266213257463... | ||
16717 | 52518.0043900605735... | 52518 | 52518 / 16717 | 3.14159239097924268... | .000000262610550551... | ||
16830-20672 | skipped for clarity | 35 more fractions | slightly better | ||||
20785 | 65298.0033048638524... | 65298 | 65298 / 20785 | 3.14159249458744286... | .000000159002350371... | yes | |
20898 | 65653.0032747194990... | 65653 | 65653 / 20898 | 3.14159249688965451... | .000000156700138726... | ||
21011-32763 | skipped for clarity | 105 more fractions | slightly better | ||||
32876 | 103283.000079418042... | 103283 | 103283 / 32876 | 3.14159265117410877... | .000000002415684466... | ||
32989 | 103638.000049273689... | 103638 | 103638 / 32989 | 3.14159265209615326... | .000000001493639975... | ||
33102 | 103993.000019129335... | 103993 | 103993 / 33102 | 3.14159265301190260... | .000000000577890634... | ||
33215 | 104347.999988984982... | 104348 | 104348 / 33215 | 3.14159265392142104... | .000000000331627806... | ||
66317 | 208341.000008114318... | 208341 | 208341 / 66317 | 3.14159265346743670... | .000000000122356532... | ||
99532 | 312688.999997099300... | 312689 | 312689 / 99532 | 3.14159265361893662... | .000000000029143384... | yes | |
265381 | 833719.000002312919... | 833719 | 833719 / 265381 | 3.14159265358107777... | .000000000008715467... | yes | |
364913 | 1146407.99999941222... | 1146408 | 1146408 / 364913 | 3.14159265359140397... | .000000000001610740... | ||
995207 | 3126535.00000113735... | 3126535 | 3126535 / 995207 | 3.14159265358865040... | .000000000001142837... | yes | |
1360120 | 4272943.00000054957... | 4272943 | 4272943 / 1360120 | 3.14159265358938917... | .000000000000404066... | ||
1725033 | 5419350.99999996179... | 5419351 | 5419351 / 1725033 | 3.14159265358981538... | .000000000000022144... | yes | yes |
13435351 | 42208400.0000002821... | 42208400 | 42208400 / 13435351 | 3.14159265358977223... | .000000000000021002... | ||
15160384 | 47627751.0000002439... | 47627751 | 47627751 / 15160384 | 3.14159265358977714... | .000000000000016092... | ||
16885417 | 53047102.0000002057... | 53047102 | 53047102 / 16885417 | 3.14159265358978105... | .000000000000012186... | ||
18610450 | 58466453.0000001675... | 58466453 | 58466453 / 18610450 | 3.14159265358978423... | .000000000000009004... | ||
20335483 | 63885804.0000001293... | 63885804 | 63885804 / 20335483 | 3.14159265358978687... | .000000000000006361... | ||
22060516 | 69305155.0000000911... | 69305155 | 69305155 / 22060516 | 3.14159265358978910... | .000000000000004132... | ||
23785549 | 74724506.0000000529... | 74724506 | 74724506 / 23785549 | 3.14159265358979101... | .000000000000002227... | ||
25510582 | 80143857.0000000147... | 80143857 | 80143857 / 25510582 | 3.14159265358979265... | .000000000000000579... | ||
52746197 | 165707064.999999991... | 165707065 | 165707065 / 52746197 | 3.14159265358979340... | .000000000000000164... | ||
78256779 | 245850922.000000006... | 245850922 | 245850922 / 78256779 | 3.14159265358979316... | .000000000000000078... | yes | yes |
Example of usage
One possible usage of this method would be to find the best fraction for a denominator with a specific number of digits.
For this, look at the penultimate column on the above table. Most of these fall in green lines (also found with the continued fraction process), except for 311/99 and 3126535/995207.
Similarly, if we want to use these fractions to estimate pi with a using typical computer variable sizes (8 bit, 16 bit, 32bit, 64 bit, etc...) we might want to look at the last column. About half of them would not have been found with the continued fraction method.