Tea-shop PI- VI

How could you find the best rational approximation of π?

The fact is that rational approximations of π are not obtained directly from a formula generating π such as the Mahdava's arctan series which is by far the oldest of its kind (around 1400 AD) and the BBP-type formulas of today. The BBP (David Bailey, Peter Borwein and Simon Plouffe, 1995) algorithm is the type of algorithms known as digit extraction algorithms which allows digits of a given number to be calculated without requiring the computation of earlier digits.

The way you get a rational approximation of π is first to have some accurate approximation such as a decimal approximation of π to 15 decimal digits or more and then work from it to get the desired rational approximation.
In 2008 S K Sen and R P Agarwal suggested four procedures for finding best rational approximations, namely, (i) Exhaustive search, (ii) Principal convergents of continued fraction based procedure, (iii) Best rounding procedure for rational approximation, and (iv) Continued fraction based algorithm with intermediate convergents (Agarwal et al, Birth, growth and computation of pi to ten trillion digits, 2013).
Consequently they have demonstrated that the absolute best k-digit rational approximation of π will be as good as 2k-digit decimal approximation of π. That means, for example, that 355/133 which is the best rational approximation with three digits in the numerator (k = 3) would be as good as the decimal approximation of π with six digits. Sen and Agarwal developed their procedures based on MATLAB, a well known commercial numerical computing environment and programming language. However, these should be implementable with other programming languages including R which is available for free.
The best 3-digits rational approximation for π is 355/113 = 3.1415929203..., correct to six decimals shown in bold figures. We have seen a popular belief circulated on some websites that you could easily obtain a rational approximation by taking the (i) decimal representation of π, (ii) take any denominator of your choice, (iii) multiply i) by ii), (iv) round the result of last step and you get the numerator. It is not that simple to get the best approximation. For example, you take 111 as denominator because it looks pretty and try that procedure:

3.141592 x 111 = 348.716712 and rounding to 349, then

349/111 =  3.144144144 which is correct to 2 decimals only

Note that it is only as good as 22/7 in terms of correct number of decimal digits. But 22/7 has an absolute error of 0.001264489267350 while 349/111 has a worse absolute error of 0.002551490554350.

The continued fraction of a number is of the form:

For π = 3.141592653589793... , the continued fraction representation is:

To get the continued fraction you calculate this way:

The first integer term 3 is the integer part of π.

The second integer term 7 in the denominator is obtained by taking the integer part obtained from taking the reciprocal of the decimal part = 1/0.141592653589793 = 7.062513305931057.

The third integer term 15 in the denominator is obtained by taking the integer part of obtained from taking the reciprocal of the decimal part = 1/0.062513305931057 = 15.99659440668285.

Then 1/0.99659440668285 =  1.003417231016262.

Then 1/0.003417231016262 =  292.634590766962, and if you go on calculating this way you will get the continued fraction shown above.

Since the continued fraction for π never ends, you stop where you want to stop and calculate the result.

Thus to estimate π ignoring all fractional parts we take π = 3/1.

To estimate using two terms we have π = 3 +(1/7) = 22/7.

Using four terms we have π = 3 + 1/(7 + 1/(15+1)) = 3 + (16/113) = 355/113.

Each of such values obtained by taking only a part of the continued fraction is known as a partial convergent. It is known that the partial convergent just before a large denominator, here 15 and 292 give particularly accurate approximations. If you go on with the continued fraction you will find such termination points before the denominator 84 and 99 among others.

It is not practicable to compute the terms of continued fraction for π by hand for more than a few terms as the scale of arithmetic will be getting too big. A convenient way is to use the R package "contfrac". You can try running this in R:

Then you should get the output:

$A

[1]       3      22     333     355  103993  104348  208341  312689  833719

[10] 1146408

$B

[1]      1      7    106    113  33102  33215  66317  99532 265381 364913

If you want to look at the continued fraction:

> x

You get the output:

[1]   3   7  15   1 292   1   1   1   2   1

Even simpler is to read off the numerator and denominator with desired number of digits from the lists provided by OEIS (On-Line Encyclopedia of Integer Sequences) at https://oeis.org/.

You can search for the following sequences.

A002485 – Numerators of convergents to Pi

3, 22, 333, 355, 103993, 104348, 208341, 312689, 833719, 1146408, 4272943, 5419351, 80143857, 165707065, 245850922, 411557987, 1068966896, 2549491779, 6167950454, 14885392687, 21053343141, 1783366216531, 3587785776203, 5371151992734, 8958937768937

A002846 – Denominators of convergents to Pi

1, 7, 106, 113, 33102, 33215, 66317, 99532, 265381, 364913, 1360120, 1725033, 25510582, 52746197, 78256779, 131002976, 340262731, 811528438, 1963319607, 4738167652, 6701487259, 567663097408, 1142027682075, 1709690779483, 2851718461558, 44485467702853

You can also look for longer lists of numerators and denominators by following the links provided in their descriptive texts.