# RationalApprox.py
'''
  Compute the best rational approximation to x using Stern-Brocot
  tree.
 
  > python RationalApprox.py
  x=? 2.71828182845904523536028747135
  1 2 3 5/2 8/3 11/4 19/7 49/18 68/25 87/32 106/39 193/71 685/252 878/323 ...
 
  > python RationalApprox.py
  x=? 3.14159265358979323846264338328
  1 2 3 13/4 16/5 19/6 22/7 179/57 201/64 223/71 245/78 267/85 289/92 311/99 333/106
 
'''
EPS = 1E-5

def mediant(f1, f2):
  return (f1[0] + f2[0], f1[1] + f2[1])

def toFloat(f):
  return f[0]/f[1]

x = float(input("x=? "))
left  = (0, 1)
right = (1, 0)
best = left
bestError = abs(x)
# Stern-Brocot binary search
while bestError > EPS:
  # compute next possible rational approx
  med = mediant(left, right)
  if x < toFloat(med):
    right = med    # go left
  else:
    left = med     # go right
  # check if better and update
  error = abs(toFloat(med) - x)
  if error < bestError:
    best = med
    bestError = error
    print(best, end=' ')
print()