4 ms·
The numbers that you're producing can be better produced by the following Python code: from fractions import Fraction as frac def continued_fraction(x,
by drostie 14y ago
The numbers that you're producing can be better produced by the following Python code:
from fractions import Fraction as frac
def continued_fraction(x, n=10):
"""Represent x as a continued fraction out to n places."""
last = int(x)
out = []
for i in range(n):
x = 1/(x - last)
last = int(x)
out.append(last)
return out
def bras(x, n=10):
"""Compute the best rational approximations to x."""
base = int(x)
nums = continued_fraction(x, n)
S = lambda depth, i = 0: \
frac(1, nums[i]) if depth == 0 else 1 / (nums[i] + S(depth - 1, i + 1))
return ', '.join(str(x) for x in (base,) + tuple(base + S(k) for k in range(n)))
from decimal import Decimal
print(bras(Decimal('3.1415926535897932384626433832795028841971693993')))
# 3, 22/7, 333/106, 355/113, 103993/33102, 104348/33215, 208341/66317,
# 312689/99532, 833719/265381, 1146408/364913, 4272943/1360120
These are the best rational approximations to pi, which are determined by the continued fraction of pi:
pi ~= 3 + 1/(7 + 1/(15 + ...))
pi = 3 + [7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, ...]
Large numbers are opportunities to "grab a lot of extra digits" and thus the large qualities come when we truncate after 7, 15, 292, and 14.
You may wonder what the "most irrational" number is, in the sense that all of its best-rational-approximations are of low quality. That distinction belongs to:
phi = (1 + Decimal(5).sqrt()) / 2 # golden ratio
continued_fraction(phi) # [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
bras(phi) # 1, 2, 3/2, 5/3, 8/5, 13/8, 21/13, 34/21, 55/34, 89/55, 144/89
Those last numbers you may recognize from your intro to programming as the Fibonaccis.
- abecedarius 14y agoHere's some simpler code that computes the same result -- I'm too tired and dumb to work out if it will for any number: def rationalizations(x): """Generate good rational approximations of x in order of increasing denominator.""" assert 0 <= x ix = int(x) yield ix, 1 if x != ix: for numer, denom in rationalizations(1.0/(x-ix)): yield denom + ix * numer, numer import itertools, math def show(x, n): return list(itertools.islice(rationalizations(x), n)) print show(math.pi, 11) # [(3, 1), (22, 7), (333, 106), (355, 113), (103993, 33102), # (104348, 33215), (208341, 66317), (312689, 99532), # (833719, 265381), (1146408, 364913), (4272943, 1360120)] From https://github.com/darius/sketchbook/blob/master/misc/rationalize.py https://github.com/darius/sketchbook/blob/master/misc/ration...
- drostie 14y agoIt's true, my code is longer because it computes an explicit continued fraction representation (and also because it's not written as two generator scripts).