컴퓨터가 실수를 연분수 표현(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. 연습문제
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
'대수학' 카테고리의 다른 글
Fast Fourier Transform을 이용한 빠른 다항식 곱셈 공부하기 (0) | 2023.08.29 |
---|---|
키타마사 법(kitamasa method, きたまさ法)에 대한 공부 (0) | 2023.08.27 |
다항식의 곱셈과 나눗셈 기본 컴퓨터 구현 방법 배우기 (0) | 2023.08.26 |