Sqrt(n) 의 연분수 표현 구하기

Sqrt(n) 의 연분수를 정확하게 구하기.

sqrt(n) 의 연분수는 [ a_0;a_1, a_2, ... ] 이고 유리수 소수표현처럼 순환마디가 있을거다.

a_n = [ b_n ] 으로 정의되고, b_{n+1} = 1 / ( b_n - a_n ) 이고, b_0 = sqrt(n)

b_n 은 어떻게든 분모를 유리화할수 있고, b_n = x_n sqrt(n) + y_n  (x_n, y_n 은 유리수) 로 표현이 가능하다. 그래서, x_n, y_n 은 언젠가는 동일한 것이 나와서 순환할 것.

sqrt(2) = [ 1; 2, 2, 2, ... ] 이다.

sqrt(3) = [ 1; 1, 2, 1, 2, ... ] 

이 과정을 프로그래밍해 본다.

#!/usr/bin/env python
# -------------------------------------------------------------
# Calculates continued fraction for numbers of following form
#
#       n     .__
#       - ( |/ r   + b )
#       m
#
#  m, n, r, b in |N
# -------------------------------------------------------------
from functools import lru_cache


def gcd(m, n):
    if m < n:
        m, n = n, m
    if m % n == 0:
        return n
    else:
        return gcd(n, m % n)

@lru_cache()
def f(r, b, n, m):

    a = 0
    while n * n * r > (m * a - n * b) * (m * a - n * b):
        a += 1
    a -= 1

    rr, bb, nn, mm = r, m * a - b, m, n * (r - (b - m * a) * (b - m * a))

    nn, mm = nn // gcd(nn, mm), mm // gcd(nn, mm)

    return a, rr, bb, nn, mm


if __name__ == "__main__":
    # --- main ---
    # develops continued fraction of sqrt(23)
    p = f(23, 0, 1, 1)
    cf = []
    for i in range(33):
        print(p)
        cf.append(p[0])
        p = f(p[1], p[2], p[3], p[4])

    print(f"sqrt(23) = cf({cf})")