[Python] 실수값 연분수로 근사값 분수 찾기, approx real value using continued fraction

import math


def contfrac(x, n=10, mx=1000):
    """
    get continued fraction of real x

                            1
        x = r0 + --------------------------
                                1
                  r1 + --------------------
                                   1
                         r2 + -------------
                                  r3 + ....

    n : maximum length of returning r:list
    mx : maximum ri
    return : continued fraction, list of integers
    """
    r = [int(x)]
    if n == 0 or (x - r[0] < 1 / mx):
        return r
    return r + contfrac(1 / (x - r[0]), n - 1, mx)


def cf2frac(cf):
    """
    convert continued fraction to fraction
    cf : continued fraction, list of integers
    return : (bunja, bunmo), pair of integers
    """
    ja, mo = 1, cf[-1]
    for n in reversed(cf[:-1]):
        ja, mo = mo, ja + n * mo
    return mo, ja


for cf in [[1], [1, 2], [1, 2, 3]]:
    print(cf, cf2frac(cf))

for c in [(1, 2), (33, 23), (36, 357), (325, 22)]:
    frac = c[0] / c[1]
    r = cf2frac(contfrac(frac))
    print(c, r, c[0] * r[1] - c[1] * r[0])

for r in [2.738292, 3.1415927, 323.44, math.pi, math.e]:
    s = cf2frac(contfrac(r))
    print(r, s, r - s[0] / s[1])

for r in [2.738292, 3.1415927, 323.44]:
    s = cf2frac(contfrac(r, n=10, mx=100))
    print(r, s, r - s[0] / s[1])

for r in [2.738292, 3.1415927, 323.44]:
    s = cf2frac(contfrac(r, n=10, mx=50))
    print(r, s, r - s[0] / s[1])

C:\Users\me>py -3 contfrac.py
[1] (1, 1)
[1, 2] (3, 2)
[1, 2, 3] (10, 7)
(1, 2) (1, 2) 0
(33, 23) (33, 23) 0
(36, 357) (12, 119) 0
(325, 22) (325, 22) 0
2.738292 (683579, 249637) 1.602318278060011e-11
3.1415927 (20313108, 6465863) 1.554312234475219e-14
323.44 (8086, 25) 0.0
3.141592653589793 (4272943, 1360120) 4.04121180963557e-13
2.718281828459045 (2721, 1001) 1.1017732681750658e-07
2.738292 (994, 363) -1.101928370772498e-08
3.1415927 (355, 113) -2.2035398261621708e-07
323.44 (8086, 25) 0.0
2.738292 (994, 363) -1.101928370772498e-08
3.1415927 (355, 113) -2.2035398261621708e-07
323.44 (8086, 25) 0.0

 

• https://daewonyoon.tistory.com/426 : 일반적인 sqrt(n)의 연분수 구하기
• https://daewonyoon.tistory.com/431 : sqrt(2) 연분수 표현 관련 오일러프로젝트 문제풀이