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.

103393/33102

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...

## Add new comment