컴퓨터가 실수를 연분수 표현(continued fraction)으로 나타내는 방법

1. 유리수의 continued fraction

 

continued fraction은 실수를 수렴하는 유리수의 수열로 표현하는 것이다.

 

이는 problem solving에서 유용할 수 있는데, 쉽게 계산될 수 있으며, 실수의 최적 유리수 근사를 찾는데 효과적으로 사용될 수 있어서 그렇다.

 

게다가 정수론에서 유용하게 사용되는 유클리드 알고리즘과 연관되어있다.

 

어떤 정수 $a_{0}, a_{1}, ..., a_{k}$에 대하여, $a_{1}, a_{2}, ... , a_{k}$가 1이상의 자연수일때,

 

$$r = a_{0} + \frac{1}{a_{1} + \frac{1}{... + \frac{1}{a_{k}}}}$$ 를 유리수 r의 연분수 표현(continued fraction)이라고 부른다.

 

이를 r을 간단하게 $r = [a_{0}; a_{1}, a_{2}, ..., a_{k}]$로 쓴다.

 

1-1) 성질

 

임의의 유리수 r에 대하여 연분수 표현을 정확히 다음 2가지중 하나로 나타낼 수 있다.

 

$$r = [a_{0};a_{1},...,a_{k},1] = [a_{0};a_{1}, ... , a_{k}+1]$$

 

그런가..??

 

모든 유리수 p/q의 continued fraction은 위와 같은 유일한 2가지 유한집합으로 표현할 수 있다는 것이다.

 

여기서 $a_{0}$는 정수이고 $a_{1}, a_{2}, ... , a_{k}$는 자연수이다.

 

 

2. 무리수의 continued fraction

 

$r_{k} = [a_{0}; a_{1}, ... , a_{k}]$에 대하여, 무리수 r의 continued fraction은...

 

$$r = a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2} + ...}} = \lim_{k \to \infty} r_{k}$$

 

이때 $r = [a_{0};a_{1},a_{2},...]$으로 나타낸다.

 

여기서 몇가지를 관찰할 수 있는데..

 

1) 먼저 정수 k에 대하여...

 

$$r + k = [a_{0} + k; a_{1},...]$$ 이다.

 

2) r에 대해 역수를 취하면...?

 

$$\frac{1}{r} = [0;a_{0}, a_{1}, ...], a_{0} > 0$$

 

$$\frac{1}{r} = [a_{1};a_{2}, ... ], a_{0} = 0$$ 이다.

 

3) 모든 무리수는 연분수 표현이 무한집합이다. 무한집합으로 나타난 연분수 표현은 무리수가 된다.

 

3. complete quotients

 

$s_{k} = [a_{k}; a_{k+1}, a_{k+2},....]$라고 정의되는 $s_{k}$를 r의 k번째 complete quotient라고 한다.

 

이를 이용하면.. 무리수 r의 연분수 표현은..

 

$$r = [a_{0}; a_{1}, ... , a_{k-1}, s_{k}]$$

 

특히 정의로부터 $s_{0} = [a_{0};a_{1},...] = r$이다.

 

또한 $$s_{k} = [a_{k};s_{k+1}] = a_{k} + \frac{1}{s_{k+1}}$$ 이다.

 

이는 $a_{k}$는 $s_{k}$보다 작거나 같은 최대의 정수 $a_{k} = \left \lfloor s_{k} \right \rfloor$이다.

 

그리고 $a_{k}$, $s_{k}$를 모두 안다면.. $s_{k+1}$은...

 

$s_{k+1} = \frac{1}{(s_{k} - a_{k})}$로 구할 수 있다.

 

 

4. 구현 예시 - rational to continued fraction

 

유리수 r에 대하여, complete quotients $s_{k}$에서 $s_{k+1}$로 가는 점화식은...

 

$$s_{k} = \left \lfloor s_{k} \right \rfloor + \frac{1}{s_{k+1}}$$

 

따라서, $$s_{k+1} = (s_{k} - \left \lfloor s_{k} \right \rfloor)^{-1}$$

 

r이 유리수라면, $s_{k}$도 유리수이므로, $s_{k} = \frac{p_{k}}{q_{k}}$라고 하자.

 

여기서 $p_{k}, q_{k}$는 정수이다.

 

$$s_{k+1} = (\frac{p_{k}}{q_{k}} - \left \lfloor \frac{p_{k}}{q_{k}} \right \rfloor)^{-1}$$

 

여기서 $\left \lfloor \frac{p_{k}}{q_{k}} \right \rfloor$은 $p_{k}$를 $q_{k}$로 나눈 몫이므로,

 

$$p_{k} = q_{k} * (\left \lfloor \frac{p_{k}}{q_{k}} \right \rfloor)  + p_{k} mod q_{k}$$

 

양변을 $q_{k}$로 나눠서 다음과 같이 쓸 수 있다.

 

$$s_{k+1} = (\frac{p_{k} mod q_{k}}{q_{k}})^{-1} = \frac{q_{k}}{p_{k} mod q_{k}}$$

 

따라서 $r = s_{0} = \frac{p_{0}}{q_{0}}$부터 시작해서, $p_{k+1} = q_{k}$, $q_{k+1} = p_{k} mod q_{k}$로

 

$q_{k}$가 0이 아닐 때까지 반복적으로 구하면 된다.

 

여기서 당연하지만 p,q는 서로소이다.

 

def continued_fraction(p,q):
    
    s = []
    
    while q:
        
        s.append(p//q)
        p,q = q,p%q
    
    return s

 

5. convergent

 

유리수 $r_{0}, r_{1}, ...$은 r의 convergent라고 부른다.

 

각각의 $r_{k} = [a_{0};a_{1}, ... , a_{k}] = \frac{p_{k}}{q_{k}}$는 k번째 convergent라고 부른다.

 

여기서 $r_{k} = \frac{p_{k}}{q_{k}}$라고 할 때, 다음 식이 성립한다.

 

$$\frac{p_{k}}{q_{k}} = \frac{a_{k}p_{k-1} + p_{k-1}}{a_{k}q_{k-1} + q_{k-2}}$$

 

단, $p_{-1} = 1, p_{-2} = 0, q_{-1} = 0, q_{-2} = 1$이다.

 

 

연분수 표현 $[a_{0};a_{1}, a_{2}, ... , a_{n}]$이 주어진다고 해보자.

 

이를 유리수 $r_{n} = \frac{p_{n}}{q_{n}}$으로 나타내고 싶다면, 위 점화식으로부터 n번째 p,q 항까지 반복적으로 구하면 된다.

 

k = 0이라면,

 

$\frac{p_{0}}{q_{0}} = \frac{a_{0}*p_{-1} + p_{-2}}{a_{0}*q_{-1} + q_{-2}} = \frac{a_{0}*1+0}{a_{0}*0+1}$

 

여기서 $p_{0}, q_{0}$를 구할 수 있고,

 

k = 1이라면,

 

$\frac{p_{1}}{q_{1}} = \frac{a_{1}*p_{0} + p_{-1}}{a_{1}*q_{0} + q_{-1}}$ 으로 $p_{1}, q_{1}$을 구할 수 있다.

 

이런식으로 모든 $a_{0}, a_{1}, ... , a_{n}$까지 순회하여 $p_{n}, q_{n}$을 구한다면, 그것이 유리수 표현이 된다.

 

def convergent(f):
    
    p = [0,1]
    q = [1,0]

    for a in f:
        
        p.append(p[-1]*a + p[-2])
        q.append(q[-1]*a + q[-2])
    
    return p[-1],q[-1]

 

 

6. 연습문제

 

10386번: $\text{Con}+\cfrac{\text{tin}}{\text{ued}+\cfrac{\text{Frac}}{\text{tions}}}$ (acmicpc.net)

10386번: $\text{Con}+\cfrac{\text{tin}}{\text{ued}+\cfrac{\text{Frac}}{\text{tions}}}$

 

7. 풀이

 

유리수의 연분수 A,B가 주어질때, A+B, A-B, A*B, A/B를 연분수로 나타내는 문제

 

연분수에 대한 사칙연산 알고리즘이 있는것 같은데 무슨 말인지 모르겠더라고...(기회가 있으면 다시 보도록 하고..)

 

다행히 n이 작다보니 연분수를 유리수 p/q로 나타내고, 유리수에 대한 사칙연산을 직접 구한 다음

 

기약분수로 나타내고, 이를 다시 연분수로 표현하는 과정을 거치면 된다

 

당연히 예를 들어 합의 경우는 p1/q1 + p2/q2 = (p1*q2 + p2*q1)/q1*q2 처럼 통분해서 (p1*q2+p2*q1), (q1*q2)를 구하고 기약분수로 나타내야한다.

 

유리수 a/b를 기약분수로 나타낼려면?

 

a,b의 최대공약수 g를 구하면 a = gr, b = gk, (r,k는 서로소)이므로 a//g, b//g를 구하면 된다.

 

#연분수의 사칙연산
#연분수 > 유리수 > 사칙연산(합,차,곱,나눗셈) > 기약분수 > 연분수

#연분수를 유리수로 바꾸는 함수
#p_k = a_k*p_(k-1) + p_(k-2)
#q_k = a_k*q_(k-1) + q_(k-2)

#p_(-1) = 1, p_(-2) = 0
#q_(-1) = 0, q_(-2) = 1
def convergent(f):
    
    p = [0,1]
    q = [1,0]

    for a in f:
        
        p.append(p[-1]*a + p[-2])
        q.append(q[-1]*a + q[-2])
    
    return p[-1],q[-1]

#유리수 p/q를 연분수로 나타내는 함수
#p,q는 서로소
def continued_fraction(p,q):
    
    f = []

    while q:
        
        f.append(p//q)
        p,q = q,p%q
    
    return f

#a,b의 최대공약수를 구하는 유클리드 알고리즘
def gcd(a,b):
    
    while b != 0:
        
        a,b = b,a%b
    
    return a

#유리수 p/q를 기약분수로 나타내는 함수
#p,q의 최대공약수 g에 대하여 p = gr, q = gk, r,k는 서로소
#p//g, q//g가 기약분수
def reduced(p,q):
    
    g = gcd(p,q)

    return p//g, q//g

t = 1

while 1:
    
    n1,n2 = map(int,input().split())

    if n1 == 0 and n2 == 0:
        
        break
    
    else:
        
        #연분수
        f1 = list(map(int,input().split()))
        f2 = list(map(int,input().split()))
        
        #연분수 > 유리수
        p1,q1 = convergent(f1)
        p2,q2 = convergent(f2)
        
        #유리수 사칙연산
        #> 기약분수
        #> 연분수
        add = continued_fraction(*reduced(p1*q2+p2*q1,q1*q2))
        minus = continued_fraction(*reduced(p1*q2-p2*q1,q1*q2))
        multiply = continued_fraction(*reduced(p1*p2,q1*q2))
        divide = continued_fraction(*reduced(p1*q2,q1*p2))

        print(f'Case {t}:')
        print(' '.join(map(str,add)))
        print(' '.join(map(str,minus)))
        print(' '.join(map(str,multiply)))
        print(' '.join(map(str,divide)))
        t += 1