This site is supported by donations to The OEIS Foundation.

User:Daniel Mondot/Continued Fraction

From OeisWiki
Jump to: navigation, search

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
Number
Integer
part
remainder
part
Reciprocal
of r
1
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
Fraction
Simplify Simplify
again
Simplify
further
Simplify
further
Simplify
further
Value 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:

Brute-forcing all possible fractions for
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:

Selecting best fractions based on increasingly better final error
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.