연분수(continued fraction)를 이용한 선형 디오판토스 방정식의 해를 구하는 방법

1. 연분수 표현에서 a,b의 최대공약수를 바로 구하는 방법 $\frac{A}{B}$의 연분수 표현을 구하고자 한다면, A/B가 기약분수 형태로 들어가줘야한다. 기약분수로 바꿀려면 A,B의 최대공약수가 g = gcd(A,B)일때, $p_{k} = A/g, q_{k} = B/g$이고 그래서 $\frac{A}{B} = \frac{p_{k}}{q_{k}}$이다. 따라서, A/B가 기약분수가 아닐때, 연분수 표현 p,q를 구한 다음 A를 p[-1]로 나눠주면 A,B의 최대공약수가 된다. #A/B가 기약분수가 아닐때, A,B의 최대공약수 구하기 def continued_fraction(p,q): f = [] while q != 0: f.append(p//q) p,q = q,p%q return f def conve..

• format_list_bulleted 정수론
• · 2023. 9. 29.
• textsms

컴퓨터가 실수를 연분수 표현(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을 간단하..

• format_list_bulleted 대수학
• · 2023. 9. 20.
• textsms