Fractional Approximations of Pi

Now that we are just past Pi Approximation Day (22/7 or July 22), I thought about how to find other fractional approximations of \(\pi\) with small numerators and denominators. Instead of using things like continued fractions and Stern-Brocot trees, I decided that I was going to brute force this thing, just because I can.

To find the best fractional approximation \(n/d\) (such as 22/7) for pi, given a denominator \(d\), lets do the following. For each \(d\), compute \(\pi d\) and then take the floor (the greatest integer less than or equal, written as \(\lfloor x\rfloor\)) and the ceiling (the smallest integer greater than or equal, written as \(\lceil x\rceil\)) of \(\pi d\). This results in two fractions,

\[\frac{\lfloor\pi d\rfloor}{d}\]

and

\[\frac{\lceil\pi d\rceil}{d}.\]

One of these must be the best approximation for the given \(d\), because \(\lfloor\pi d\rfloor/d\lt\pi\), \(\lceil\pi d\rceil/d\gt\pi\), and \(\lceil\pi d\rceil=\lfloor\pi d\rfloor+1\).

I’ve then written the following Python program that tries all denominators from 1 to 10000 and prints out a line when it finds a new best approximation.

from __future__ import print_function
from __future__ import division
 
import numpy as np
 
best_diff = 1
for d in range(1, 10001):
    nf = int(np.floor(np.pi * d))
    nc = int(np.ceil(np.pi * d))
    nf_diff = np.abs(nf / d - np.pi)
    nc_diff = np.abs(nc / d - np.pi)
    if nf_diff < best_diff:
        best_diff = nf_diff
        print('{} / {}: {:.2e}'.format(nf, d, best_diff))
    elif nc_diff < best_diff:
        best_diff = nc_diff
        print('{} / {}: {:.2e}'.format(nc, d, best_diff))

Running this program, so with the denominator going up to 10000, produces the following output.

3 / 1: 1.42e-01
13 / 4: 1.08e-01
16 / 5: 5.84e-02
19 / 6: 2.51e-02
22 / 7: 1.26e-03
179 / 57: 1.24e-03
201 / 64: 9.68e-04
223 / 71: 7.48e-04
245 / 78: 5.67e-04
267 / 85: 4.16e-04
289 / 92: 2.88e-04
311 / 99: 1.79e-04
333 / 106: 8.32e-05
355 / 113: 2.67e-07

This output lists each fraction that breaks the record for being closer to \(\pi\), ordered by increasing accuracy. 22/7 is found, and the other well-known approximation of 355/113 also turns up. The fact that no new best is found for a denominator up to 10000 shows that 355/113 is an exceptionally good approximation. The record is only beaten next by 52163/16604.

Philip Sanders (not verified)

Mon, 12/06/2021 - 20:57

What cacthes the eye: 201/64 is a very "binary" solution: 0xC9/0x40.
Hence, if in need for times_Pi, one can approximate with (R*0xC9)>>6, with less than 0.1% error
Interesting... but no idea (yet) where to use it...

Unfortunately, "a >> b" won't make any sense on floats and won't have the required precision on an integer.

Add new comment

The content of this field is kept private and will not be shown publicly.
Spam avoidance measure, sorry for this.

Restricted HTML

  • Allowed HTML tags: <a href hreflang> <em> <strong> <cite> <blockquote cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd> <h2 id> <h3 id> <h4 id> <h5 id> <h6 id>
  • Lines and paragraphs break automatically.
  • Web page addresses and email addresses turn into links automatically.
Submitted on 28 July 2020