# cfLib.py

import math
import decimal
from decimal import Decimal as D


def cf(numer, denom, maxTerms=10):
  # Return the terms of the continued fraction for 
  # the numerator and denominator as a list
  terms = []
  quotient = numer//denom 
  rem = numer - quotient*denom
  count = 0

  while (rem != 0) and (count < maxTerms):
    terms.append(quotient)
    count += 1
    prev_r = rem
    quotient = denom//prev_r
    rem = denom - quotient*prev_r
    denom = prev_r
  terms.append(quotient)
  return terms

def cfList(x, maxTerms=10):
  cfs = []
  i = 0
  for val in cfY(x):
    # print(val)
    cfs.append(val)
    i += 1
    if i > maxTerms:
      break
  return cfs


def cfY(x):
  while x != int(x):
    a = int(x)
    x = 1/(x-a)
    yield a


def cfDecList(x, maxTerms=20):
  cfs = []
  i = 0
  for val in cfDecY(x):
    # print(val)
    cfs.append(val)
    i += 1
    if i > maxTerms:
      break
  return cfs


def cfDecY(x):
  decimal.getcontext().prec = 100
  d1 = D(1)
  dx = D(x)
  while dx != math.trunc(dx):
    a = math.trunc(dx)
    dx = d1/(dx-a)
    yield a


# Get best rational approximations of a continued fraction.
def approxCF(x, maxDenom=1000):
  n2, d2 = int(x), 1
  for n1, d1 in approxCFY(x):
    if d1 > maxDenom:
      return n2, d2
    n2, d2 = n1, d1


def approxCFY(x):
  cfGen = cfY(x)
  n1, n2 = 1, 0
  d1, d2 = 0, 1
  for a in cfGen:
    for b in range((a+1)//2, a+1):
      yield (b*n1+n2, b*d1+d2)
    n1, n2 = a*n1+n2, n1
    d1, d2 = a*d1+d2, d1


def convergentsErr(cfList, minErr=1e-5):
  p0 = 1; q0 = 0 
  p = cfList[0]; q = 1
  i = 1
  err = 1
  cs = [(1,1)]
  while (i < len(cfList)) and (abs(err) > minErr):
    a = cfList[i]
    if a < 1:
      break
    # update the numerator of the convergent
    p1 = a*p + p0
    p0 = p
    p = p1
    # update the denominator
    q1 = a*q + q0
    q0 = q
    q = q1
    # calculate the relative error
    err = (p/q - p0/q0) * q0/p0
    print(f"{p}/{q} = {p/q} ; rel error: {err}")
    cs.append((p,q))
    i += 1
  return cs


def cf2rat(cfList):
  # finite continued fraction to rational
  n = len(cfList)
  numer = 1
  denom = 0
  for i in range(n-1, -1, -1):
    n1 = numer*cfList[i] + denom
    denom = numer
    numer = n1
  return (numer, denom)


def convergents(cfList, numRats=10):
  p0 = 1; q0 = 0 
  p = cfList[0]; q = 1
  i = 1
  err = 1
  cs = [(1,1)]
  while i < len(cfList) and (i < numRats):
    a = cfList[i]
    if a < 1:
      break
    # update the numerator of the convergent
    p1 = a*p + p0
    p0 = p
    p = p1
    # update the denominator
    q1 = a*q + q0
    q0 = q
    q = q1
    cs.append((p,q))
    i += 1
  return cs


# ------------------------------

if __name__ == "__main__":
  f = float(input("f? "))
  cfs = cfList(f)
  print(cfs)

  approxs = approxCF(f)
  print(approxs)

  cs = convergents(cfs)
  print(cs)

  print(cf2rat(cfs))