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

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:

322/7333/106355/113103993/33102104348/33215208341/66317312689/99532833719/2653811146408/3649134272943/13601205419351/172503380143857/25510582165707065/52746197245850922/78256779411557987/1310029761068966896/3402627312549491779/8115284386167950454/196331960714885392687/473816765221053343141/67014872591783366216531/5676630974083587785776203/11420276820755371151992734/17096907794838958937768937/2851718461558139755218526789/44485467702853428224593349304/1363081215701175706674932067741/18164910481143746134899525417045/195279916968449130246273033735921/962768772685233866627445592888887/21208174623389167430010946591069243/1368767354671873402646693125139304345/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. ^_^)