What is the best rational approximation to pi using a 64-bit numerator and denominator?

Question

What's the most accurate rational pair for Pi representable with two 64 bit integers? Feel free to include other int types if you'd like.

Here's what I came up with, but I'm sure it can get more accurate since the denominator can get substantially bigger - I'm just thinking in base-10. I'm pretty sure the numerator should be something like uint64 max.

// c++
inline constexpr auto pi_num = 3141592653589793238ull;
inline constexpr auto pi_den = 1000000000000000000ull;
// c
const unsigned long long pi_num = 3141592653589793238ull;
const unsigned long long pi_den = 1000000000000000000ull;

Answer 1

You can use continued fractions to get excellent approximations of an irrational number. If you haven't encountered continued fractions before, it's a way of writing a number as nested series of fractions of the form

Adding in more and more terms into a continued fraction gives a better and better approximation as a rational number.

The continued fraction of π is

[3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1, 15, 3, 13, 1, 4, 2, 6, 6, 99, 1, 2, 2, 6, 3, 5, 1, 1, 6, 8, 1, 7, 1, 2, 3, 7, 1, 2, 1, 1, 12, 1, 1, 1, 3, 1, 1, 8, 1, 1, 2, 1, 6, 1, 1, 5, 2, 2, 3, 1, 2, 4, 4, 16, 1, 161, ...]

and so we can write a little Python script to compute approximations based on this continued fraction representation, which is shown here:

from fractions import *

digits = [3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1, 15, 3, 13, 1, 4, 2, 6, 6, 99, 1, 2, 2, 6, 3, 5, 1, 1, 6, 8, 1, 7, 1, 2, 3, 7, 1, 2, 1, 1, 12, 1, 1, 1, 3, 1, 1, 8, 1, 1, 2, 1, 6, 1, 1, 5, 2, 2, 3, 1, 2, 4, 4, 16, 1, 161]

for i in range(len(digits)):
    # Start with the last digit
    f = Fraction(digits[i]);

    # Keep rewriting it as term + 1 / prev
    for j in range(i-1, -1, -1):
        f = digits[j] + 1 / f
    
    # Stop if we overshoot
    if f.numerator >= 2**64 or f.denominator >= 2**64: break
    
    # Print the approximation we found
    print(f)

This prints continued fractions with better and better approximations until we overshoot what fits in a 64-bit integer. Here's the output:

3
22/7
333/106
355/113
103993/33102
104348/33215
208341/66317
312689/99532
833719/265381
1146408/364913
4272943/1360120
5419351/1725033
80143857/25510582
165707065/52746197
245850922/78256779
411557987/131002976
1068966896/340262731
2549491779/811528438
6167950454/1963319607
14885392687/4738167652
21053343141/6701487259
1783366216531/567663097408
3587785776203/1142027682075
5371151992734/1709690779483
8958937768937/2851718461558
139755218526789/44485467702853
428224593349304/136308121570117
5706674932067741/1816491048114374
6134899525417045/1952799169684491
30246273033735921/9627687726852338
66627445592888887/21208174623389167
430010946591069243/136876735467187340
2646693125139304345/842468587426513207

This last approximation is the best approximation of π, I believe, that fits into 64-bit integers. (It's possible that there's a better one that appears between this denominator and the next denominator that you'd get that overflows a 64-bit integer, but this is still pretty close!) Therefore, you'd want

const uint64_t pi_num   = 2646693125139304345u;
const uint64_t pi_denom = 842468587426513207u;

This source reports that this approximation is accurate to 37 decimal places (!):

3.14159265358979323846264338327950288418 (approximation)
3.14159265358979323846264338327950288419 (actual)

This should be more than enough for what you're aiming to do. (Unless, of course, you're trying to set a record for finding digits of π or something like that. ^_^)