Computing a series of good rational approximations to reals using interval shrinking and the mediant. This relates to the Farey sequence.

rational_approximation_to_real.py

"""
Code also discussed in the video

https://youtu.be/icrXmYHnU9E

Related:
https://en.wikipedia.org/wiki/Mediant_(mathematics)
"""

from fractions import Fraction


class Config:
    INT_MAX = 10**4


def mediant(a, b):
    num = a.numerator + b.numerator
    denom = a.denominator + b.denominator
    return Fraction(num, denom)


class VirtualMachine:  # This part really just abstracts a while-loop
    def __init__(self, update_step, halting_condition):
        self.update_step = update_step
        self.halting_condition = halting_condition

    def run(self, state):
        while(not self.halting_condition(state)):
            state = self.update_step(state)
        return state


def update_step_approx(state):
    x = state['x']
    l = state['l']
    r = state['r']
    approx = mediant(l, r)
    print("{}, {}, {}".format(approx, float(approx), approx - x))

    key = 'l' if x > approx else 'r'
    state[key] = approx
    return state


def halting_condition_approx(state):
    l = state['l']
    r = state['r']
    approx = mediant(l, r)

    too_large = approx.numerator > Config.INT_MAX or \
        approx.denominator > Config.INT_MAX
    return too_large


vm_approx = VirtualMachine(update_step_approx, halting_condition_approx)


def approx(x):
    approx = int(x)
    state = dict(x=x, l=approx-1, r=approx+1, o=int(x))
    state = vm_approx.run(state)

    l = state['l']
    r = state['r']
    approx = mediant(l, r)
    return approx


if __name__ == '__main__':
    from numpy import pi, exp

    print(f"pi is approx. {approx(pi)}")
    print(f"e is approx. {approx(exp(1))}")
    
    """
    Output of the script is, e.g.,
    
    3, 3.0, -0.14159265358979312
    7/2, 3.5, 0.3584073464102069
    10/3, 3.3333333333333335, 0.19174067974354037
    13/4, 3.25, 0.10840734641020688
    16/5, 3.2, 0.05840734641020706
    19/6, 3.1666666666666665, 0.025074013076873403
    22/7, 3.142857142857143, 0.0012644892673496777
    25/8, 3.125, -0.016592653589793116
    47/15, 3.1333333333333333, -0.008259320256459812
    69/22, 3.1363636363636362, -0.0052290172261568735
    91/29, 3.1379310344827585, -0.0036616191070346638
    113/36, 3.138888888888889, -0.0027037647009042765
    135/43, 3.13953488372093, -0.0020577698688630797
    157/50, 3.14, -0.0015926535897929917
    179/57, 3.1403508771929824, -0.0012417763968106676
    201/64, 3.140625, -0.000967653589793116
    223/71, 3.140845070422535, -0.0007475831672580924
    245/78, 3.141025641025641, -0.0005670125641521473
    267/85, 3.1411764705882352, -0.00041618300155787935
    289/92, 3.141304347826087, -0.0002883057637061981
    311/99, 3.1414141414141414, -0.00017851217565167943
    333/106, 3.141509433962264, -8.32196275291075e-05
    355/113, 3.1415929203539825, 2.667641894049666e-07
    688/219, 3.141552511415525, -4.0142174268176234e-05
    1043/332, 3.141566265060241, -2.6388529552168194e-05
    1398/445, 3.141573033707865, -1.9619881928001348e-05
    1753/558, 3.1415770609319, -1.5592657893304107e-05
    2108/671, 3.1415797317436662, -1.2921846126889847e-05
    2463/784, 3.141581632653061, -1.1020936732109021e-05
    2818/897, 3.141583054626533, -9.598963260248894e-06
    3173/1010, 3.1415841584158417, -8.495173951406088e-06
    3528/1123, 3.141585040071238, -7.613518555160681e-06
    3883/1236, 3.1415857605177995, -6.893071993641087e-06
    4238/1349, 3.1415863602668646, -6.293322928563327e-06
    4593/1462, 3.1415868673050618, -5.7862847313572274e-06
    4948/1575, 3.1415873015873017, -5.352002491409991e-06
    5303/1688, 3.1415876777251186, -4.975864674516828e-06
    5658/1801, 3.141588006662965, -4.64692682822232e-06
    6013/1914, 3.1415882967607107, -4.356829082396985e-06
    6368/2027, 3.14158855451406, -4.099075733066115e-06
    6723/2140, 3.141588785046729, -3.8685430641116625e-06
    7078/2253, 3.1415889924545053, -3.661135287824635e-06
    7433/2366, 3.1415891800507185, -3.473539074594356e-06
    7788/2479, 3.1415893505445744, -3.303045218672196e-06
    8143/2592, 3.1415895061728394, -3.147416953730442e-06
    8498/2705, 3.1415896487985213, -3.004791271798979e-06
    8853/2818, 3.1415897799858055, -2.873603987652018e-06
    9208/2931, 3.1415899010576593, -2.752532133776242e-06
    9563/3044, 3.1415900131406045, -2.640449188628935e-06
    9918/3157, 3.1415901171998732, -2.5363899198715956e-06
    pi is approx. 10273/3270
    
    2, 2.0, -0.7182818284590451
    5/2, 2.5, -0.2182818284590451
    8/3, 2.6666666666666665, -0.05161516179237857
    11/4, 2.75, 0.03171817154095491
    19/7, 2.7142857142857144, -0.003996114173330678
    30/11, 2.727272727272727, 0.00899089881368198
    49/18, 2.7222222222222223, 0.00394039376317723
    68/25, 2.72, 0.0017181715409551046
    87/32, 2.71875, 0.0004681715409549092
    106/39, 2.717948717948718, -0.0003331105103270282
    193/71, 2.7183098591549295, 2.8030695884417867e-05
    299/110, 2.7181818181818183, -0.00010001027722683631
    492/181, 2.718232044198895, -4.9784260149898785e-05
    685/252, 2.7182539682539684, -2.7860205076724043e-05
    878/323, 2.718266253869969, -1.557458907619491e-05
    1071/394, 2.718274111675127, -7.716783918088055e-06
    1264/465, 2.718279569892473, -2.2585665719887515e-06
    1457/536, 2.718283582089552, 1.7536305070287028e-06
    2721/1001, 2.7182817182817183, -1.1017732681750658e-07
    4178/1537, 2.718282368249837, 5.39790792064565e-07
    6899/2538, 2.7182821118991334, 2.834400882889554e-07
    9620/3539, 2.7182820005651314, 1.7210608627138413e-07
    e is approx. 12341/4540
    """