연분수

수치해석 마지막 수정: 2026-08-13 04:49:16

1. 개요[편집]

소수 전개는 10이라는 남의 사정을 담고 있다. 연분수는 그 수 자신의 사정만 담는다.

연분수(continued fraction)는 수 또는 함수를 분모에 다시 분수가 들어가는 층층 구조

x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \ddots}}} \;\equiv\; [a_0; a_1, a_2, a_3, \dots]

로 표현하는 방법이다. 부분몫 $a_k$ 가 모두 양의 정수인 경우를 정규 연분수라 부르며, 이때 표현은 (유리수의 마지막 항 관례를 빼면) 유일하다. 유리수는 유한 연분수, 무리수는 무한 연분수가 되고, 유한 단계에서 자른 것을 수렴분수(convergent) $p_k/q_k$ 라 한다.

연분수가 수치해석에서 계속 튀어나오는 이유는 딱 하나로 요약된다. 같은 크기의 분모를 쓸 때 이보다 더 잘 맞는 유리 근사는 없다. 소수 전개는 자릿수를 하나 늘릴 때마다 정확도가 무조건 10배로만 좋아지지만, 연분수는 그 수가 유리수에 얼마나 잘 근사되는지를 부분몫의 크기로 직접 드러낸다. $\pi = [3; 7, 15, 1, 292, \dots]$ 에서 292라는 큰 수가 튀어나오는 자리 직전이 그 유명한 $355/113$ 이다.

2. 유클리드 호제법과 같은 물건[편집]

정규 연분수를 구하는 절차는 이렇다. $x_0 = x$ 에서 시작해

a_k = \lfloor x_k \rfloor, \qquad x_{k+1} = \frac{1}{x_k - a_k}

를 반복한다. 유리수 $p/q$ 에 이걸 돌려 보면, 나오는 몫의 수열이 $\gcd(p,q)$ 를 구하는 유클리드 호제법의 몫 수열과 정확히 같다. 예를 들어 $355/113$ 은 $355 = 3\cdot113 + 16$ , $113 = 7\cdot16 + 1$ , $16 = 16\cdot1$ 이므로 $[3;7,16]$ 이다. 호제법의 반복 횟수가 최악일 때(연속된 피보나치 수 쌍) 부분몫이 전부 1이라는 라메의 고전적 결과도 같은 사실의 다른 얼굴이다.

여기서 두 가지 실용적 함의가 나온다. 첫째, 연분수 전개의 비용은 호제법과 같아 몫의 개수에 선형이고 그 개수는 $O(\log q)$ 다. 둘째, 부동소수점으로 저장된 수의 연분수를 몇 항 뽑아 보면 “원래 어떤 간단한 분수였는지”를 복원할 수 있다 — 컴퓨터 대수 시스템의 유리수 복원(rational reconstruction)과 기어비·근사 상수 역추적이 이 원리로 돌아간다.¹

3. 수렴분수의 점화식[편집]

수렴분수는 층을 실제로 접어 올릴 필요 없이 3항 점화식으로 나온다. $p_{-1}=1, p_{-2}=0, q_{-1}=0, q_{-2}=1$ 에서 출발해

p_k = a_k p_{k-1} + p_{k-2}, \qquad q_k = a_k q_{k-1} + q_{k-2}

행렬로 쓰면 더 깔끔하다.

\begin{pmatrix} p_k & p_{k-1} \\ q_k & q_{k-1}\end{pmatrix} = \begin{pmatrix} a_0 & 1 \\ 1 & 0\end{pmatrix}\begin{pmatrix} a_1 & 1 \\ 1 & 0\end{pmatrix}\cdots\begin{pmatrix} a_k & 1 \\ 1 & 0\end{pmatrix}

양변의 행렬식을 보면 곧바로 핵심 항등식이 떨어진다.

p_k q_{k-1} - p_{k-1} q_k = (-1)^{k-1}

즉 이웃한 두 수렴분수는 항상 서로소이며(약분할 게 없다), 두 분수의 차가 정확히 $1/(q_k q_{k-1})$ 이다. 수렴분수는 참값을 위아래로 번갈아 조이며 접근한다.

\frac{p_0}{q_0} < \frac{p_2}{q_2} < \cdots < x < \cdots < \frac{p_3}{q_3} < \frac{p_1}{q_1}

수치적으로도 이 점화식은 얌전하다. $q_k$ 가 단조 증가하는 양수 수열이라 상쇄가 없고, 부분몫이 전부 최솟값 1이어도 $q_k$ 는 피보나치 수열의 속도로 자란다. 분모가 최소한 지수적으로 커진다는 것이 뒤에 나올 근사 성질의 원동력이다.

4. 최량 유리 근사[편집]

수렴분수의 오차는 다음 부분몫이 직접 통제한다.

\frac{1}{q_k(q_{k+1}+q_k)} \;<\; \left| x - \frac{p_k}{q_k} \right| \;<\; \frac{1}{q_k q_{k+1}} \;\le\; \frac{1}{q_k^{2}}

분모 제곱의 역수보다 잘 맞는다는 것이 요점이고, 게다가 $q_{k+1} = a_{k+1}q_k + q_{k-1}$ 이므로 다음 부분몫 $a_{k+1}$ 이 클수록 그 자리의 근사가 극적으로 좋아진다. $\pi$ 에서 $a_4 = 292$ 가 나오는 덕에 $355/113$ 의 오차가 $2.7\times10^{-7}$ 까지 떨어지는 것 — 분모 세 자리로 소수점 아래 여섯 자리를 맞춘다.

더 강한 주장도 성립한다.

최량 근사 정리. $q \le q_k$ 인 모든 유리수 $p/q$ 에 대해 $|q_k x - p_k| \le |q x - p|$ 이다. 즉 수렴분수는 분모 예산 안에서 최적이다.

르장드르의 역. 거꾸로, $|x - p/q| < 1/(2q^2)$ 을 만족하는 기약분수 $p/q$ 는 반드시 $x$ 의 수렴분수다.

역방향 진술이 특히 유용하다. 어딘가에서 굴러 나온 근사 분수가 “우연히 좋은 것”인지 “구조적으로 좋은 것”인지를 판정해 준다. 그리고 후르비츠 정리는 얼마나 좋을 수 있는지의 한계를 못 박는다 — 임의의 무리수에 대해 $|x - p/q| < 1/(\sqrt5 q^2)$ 인 유리수가 무한히 많고, 상수 $\sqrt5$ 는 더 못 키운다.

5. 황금비 — 가장 근사하기 어려운 수[편집]

후르비츠의 $\sqrt5$ 를 실제로 아슬아슬하게 만드는 수가 황금비다.

\varphi = \frac{1+\sqrt5}{2} = [1;1,1,1,\dots], \qquad \varphi = 1 + \cfrac{1}{\varphi}

부분몫이 전부 1, 즉 가능한 가장 작은 값이다. 그런데 오차는 $1/(q_kq_{k+1})$ 이고 $q_{k+1} = a_{k+1}q_k + q_{k-1}$ 이므로, 부분몫이 작을수록 분모가 천천히 자라고 근사가 나쁘다. 수렴분수는 피보나치 비 $F_{k+1}/F_k$ 이고 오차는 $|\varphi - F_{k+1}/F_k| \approx 1/(\sqrt5 F_k^2)$ — 후르비츠 한계에 정확히 붙는다. 이보다 유리수 근사가 나쁜 수는 없다는 의미에서 황금비는 가장 무리수다운 무리수다. 큰 부분몫은 반대다. $\pi$ 의 292 같은 항은 “여기서 거의 유리수가 된다”는 신호다.

이 사실이 순수 정수론에 머물지 않는 것이 재미있는 지점이다. 준주기 운동에서 공명이 얼마나 위험한가는 회전수가 유리수에 얼마나 잘 근사되는가로 결정된다. KAM 정리의 디오판토스 조건이 요구하는 “유리수로 근사하기 어려운 회전수”가 곧 부분몫이 유계인 수이고, 섭동을 키울 때 가장 마지막까지 살아남는 불변 원환면이 황금비 회전수를 갖는 것이 표준 사상과 에농-하일레스 계에서 반복 확인되는 결론이다. 반대로 낮은 부분몫에서 잘리는 유리수 회전수(공명)부터 먼저 부서져 섬 사슬이 된다. 카오스로 가는 순서를 연분수가 예언하는 셈.²

같은 논리가 응용에도 내려온다. 잎차례(황금각 $137.5°$ )나 표본점 배치에서 황금비를 쓰는 이유는 “예뻐서”가 아니라 어떤 유한한 주기와도 잘 맞아떨어지지 않아 겹침이 최소이기 때문이고, 준난수 계열이나 저불일치 격자에서 무리수 회전을 쓰는 근거도 같다.

6. 유명한 전개들[편집]

수	정규 연분수	비고
$\sqrt2$	$[1;2,2,2,\dots]$	주기 1, 수렴분수가 펠 방정식의 해
$\sqrt3$	$[1;1,2,1,2,\dots]$	주기 2
황금비 $\varphi$	$[1;1,1,1,\dots]$	가장 느린 수렴
$e$	$[2;1,2,1,1,4,1,1,6,1,\dots]$	규칙적이지만 비주기
$\pi$	$[3;7,15,1,292,1,1,1,2,\dots]$	알려진 규칙 없음

여기서 정리 하나가 딱 떨어진다. 라그랑주 정리 — 정규 연분수가 결국 주기적이 되는 것과 그 수가 이차 무리수(정수계수 2차방정식의 근)인 것은 동치다. $\sqrt2$ 가 $[1;\overline{2}]$ 인 것은 우연이 아니라 $\sqrt2$ 가 이차 무리수라는 사실 그 자체다. 그리고 $\sqrt{d}$ 의 수렴분수를 훑으면 펠 방정식 $p^2 - dq^2 = \pm1$ 의 해가 순서대로 나온다 — 정수론 계산의 고전적 도구.

$e$ 의 $[2;1,2,1,1,4,1,1,6,\dots]$ 패턴은 오일러가 1737년에 증명했고, 이 규칙성 자체가 $e$ 의 무리수성 증명이 된다(주기적이 아니므로 이차 무리수도 아니다). 반면 $\pi$ 는 아직 아무 규칙도 알려져 있지 않다. 부분몫이 유계인지조차 미해결이다.

전형적인 무리수의 통계적 모습도 알려져 있다. 거의 모든 실수에서 부분몫은 가우스-쿠즈민 분포 $P(a_k = m) = \log_2\!\big(1 + \tfrac{1}{m(m+2)}\big)$ 를 따르고, 부분몫의 기하평균은 힌친 상수 $K_0 \approx 2.6854$ 로, 분모는 $q_k^{1/k} \to e^{\pi^2/(12\ln 2)} \approx 3.2758$ (레비 상수)로 수렴한다. 여기에 로흐스 정리를 얹으면 정보량이 환산된다 — 부분몫 하나가 소수 전개 약 1.03자리어치의 정보를 준다. 연분수가 소수 전개보다 “효율적인 표현”이라는 인상이 실은 근소한 차이라는 뜻이지만, 대신 그 정보가 어디에 몰려 있는지를 알려 준다는 것이 진짜 이득이다. $\pi$ 의 실측 통계는 이 예측과 잘 맞고, $e$ 는 규칙적 패턴 때문에 전혀 안 맞는다.

7. 실전 — 달력, 음계, 기어비[편집]

“분모 예산 안에서 최적”이라는 성질은 정수 개수로 실수 비율을 흉내 내야 하는 모든 설계 문제에 그대로 쓰인다. 세 가지 고전 사례가 있다.

달력. 회귀년은 약 365.2422일이다. 소수부 $0.2422 = [0;4,7,1,3,\dots]$ 의 수렴분수를 차례로 보면 설계 선택지가 그대로 나온다.

수렴분수	값	대응 역법
$1/4$	0.25	율리우스력 — 4년마다 윤년
$7/29$	0.24138	실제로 쓰인 예 없음
$8/33$	0.242424	잘랄리력 — 33년에 윤년 8회
$31/128$	0.2421875	제안된 적 있음, 오차 극소

$8/33$ 은 분모 33만으로 오차를 하루당 $2\times10^{-5}$ 까지 줄인다 — 11세기 페르시아 역법이 유럽보다 훨씬 정확했던 이유가 이것이다. 재미있는 것은 우리가 쓰는 그레고리력의 $97/400 = 0.2425$ 가 수렴분수가 아니라는 점이다. 같은 분모 예산에서 더 좋은 근사가 있는데도 100·400 같은 십진 규칙이 이겼다. 최적성이 항상 채택되지는 않는다는 사례.

음계. 순정 완전5도 $3/2$ 를 옥타브 $2$ 의 거듭제곱으로 쌓아 닫으려면 $\log_2(3/2) = 0.58496\dots$ 을 유리수로 근사해야 한다. 전개는 $[0;1,1,2,2,3,1,5,\dots]$ 이고 수렴분수가 $1/2,\,3/5,\,7/12,\,24/41,\,31/53$ 이다. 여기서 $7/12$ 가 튀어나온다 — 옥타브를 12등분하고 완전5도를 7반음으로 잡는 12평균율이 그것이다. 다음 수렴분수 $31/53$ 은 53음 평균율로, 실제로 훨씬 정확하지만 건반을 53개 만들 수 없어서 이론으로만 남았다. 음악사에서 12가 이긴 것은 우연이 아니라 연분수가 시킨 일이다.³

기어비·톱니수. 원하는 감속비가 무리수이거나 큰 소수 비율일 때, 연분수 수렴분수는 “톱니 수를 얼마 이하로 제한할 때 가장 정확한 조합”을 바로 준다. 안티키테라 기계부터 시계 장인의 기어열까지 같은 계산이 반복되어 왔고, 요즘도 난수 생성기의 격자 구조 판정이나 표본점 배치에서 같은 논리가 쓰인다.

8. 함수의 연분수[편집]

부분몫을 정수 대신 다항식으로 두면 함수 근사가 된다. 일반화된 연분수

f(z) = b_0 + \cfrac{a_1}{b_1 + \cfrac{a_2}{b_2 + \cfrac{a_3}{b_3 + \ddots}}}

에서 계수를 잘 고르면 급수보다 훨씬 넓은 영역에서 수렴한다. 고전적 예가 가우스 연분수 — 이웃한 초기하함수의 비 $\,_2F_1(a,b+1;c+1;z)/\,_2F_1(a,b;c;z)$ 를 연분수로 전개한 것으로, 특수함수의 절대다수가 여기서 특수화로 떨어져 나온다. $\tan z$ , $\tanh z$ , 불완전 감마함수, 오차함수, 지수적분이 전부 이 계보다.

\tan z = \cfrac{z}{1 - \cfrac{z^2}{3 - \cfrac{z^2}{5 - \ddots}}}

파데 근사와의 관계가 여기서 결정적이다. 연분수를 $k$ 항에서 자른 수렴분수는 유리함수이고, 이 유리함수들의 수열이 파데 표를 계단 혹은 대각선으로 훑어 내려가는 수열과 일대일로 대응한다. C-분수(정칙 C-fraction)의 수렴분수는 파데 표의 계단 경로, S-분수(스틸체스 분수)는 대각·부대각 경로다. 그래서 “테일러 계수로 파데를 만든다”와 “연분수로 전개한다”는 같은 작업을 두 언어로 말하는 것이며, 실무적으로 연분수 쪽이 차수를 하나 올릴 때 앞의 계산을 버리지 않는다는 장점이 있다(파데는 원칙적으로 선형계를 다시 푼다).

같은 3항 점화식 구조가 직교다항식과 란초스 알고리즘까지 이어진다. 스틸체스 분수의 분모가 곧 직교다항식이고, 양측 란초스가 뽑아내는 삼중대각 행렬 $T_q$ 의 성분이 곧 연분수 계수다. 고체물리의 헤이독 재귀법은 란초스 계수 $\alpha_j,\beta_j$ 를 연분수에 그대로 꽂아 그린 함수의 대각 성분을 얻는데, 이게 연분수·직교다항식·크릴로프 부분공간이 사실상 한 몸이라는 가장 실용적인 증거다. 보간과 근사에서 최량 근사를 따로 구하려면 레머즈 알고리즘으로 가야 하지만, 대각 유리 근사만으로도 지수 수렴이 나오므로 대부분은 여기서 멈춘다.

9. 수치적으로 평가하기[편집]

연분수를 실제로 계산할 때 초심자가 하는 실수는 “충분히 깊이 잘라서 안쪽부터 거꾸로 계산”하는 것이다. 문제는 얼마나 깊이 잘라야 하는지를 미리 모른다는 것. 뒤에서부터 시작하면 항을 하나 더 넣고 싶을 때 전부 다시 계산해야 한다.

정석은 앞에서부터 전진하는 방식이고, 세 가지 표준 처방이 있다.

점화식 직접 사용. $p_k, q_k$ 를 위 3항 점화식으로 굴리고 $p_k/q_k$ 를 본다. 개념이 가장 단순하지만 $p_k, q_k$ 가 각각 지수적으로 커지거나 작아져 비율은 멀쩡한데 분자·분모가 오버플로/언더플로하는 사고가 난다. 주기적으로 둘 다 같은 수로 나눠 주는 스케일링이 필수.
레온츠 알고리즘(1976). 비율을 직접 굴린다. $C_k = p_k/p_{k-1}$ , $D_k = q_{k-1}/q_k$ 를 갱신하며 부분곱 $C_kD_k$ 를 누적하면, 큰 값이 중간에 등장하지 않아 오버플로가 원천 차단된다.
수정 레온츠법(Thompson–Barnett, 1986). 레온츠법의 유일한 약점은 $C_k$ 나 $D_k$ 의 분모가 우연히 0에 가까워질 때인데, 그때 아주 작은 값( $10^{-30}$ 정도)으로 갈아 끼우면 다음 반복에서 저절로 회복된다.⁴ 이 한 줄짜리 보정이 붙은 형태가 오늘날 특수함수 라이브러리의 사실상 표준이며, Numerical Recipes에도 이 형태로 실려 있다.

수렴 판정은 부분곱 $C_kD_k$ 가 1에 충분히 가까워지는지로 한다. 그리고 연분수 표현을 쓰는 이유 자체가 대개 수치적 안정성이다. 불완전 감마함수처럼 급수 전개가 항끼리 부호가 엇갈려 파멸적 상쇄를 일으키는 영역에서, 연분수 표현은 양의 항만으로 구성되어 조건수가 훨씬 좋다. 실무 구현이 “인수가 작으면 급수, 크면 연분수”로 영역을 갈라 쓰는 이유가 이것이고,⁵ 부동소수점 연산에서 테일러 급수를 무조건 신뢰하면 안 되는 대표 사례다.

10. 관련 문서[편집]

실험 물리나 수치실험에서 “이 상수가 혹시 간단한 분수 아닐까” 싶을 때 쓰는 것이 이 기법이다. 배정밀도 값 하나를 연분수로 펴서 부분몫이 갑자기 $10^{15}$ 같은 거대한 수로 튀면, 그 직전 수렴분수가 원래 값일 확률이 높다. 큰 부분몫은 “여기서 사실상 유리수였다”는 자백이다. ↩
그래서 이 바닥에서 “황금비를 쓴다”는 말은 미학이 아니라 최적화다. 가장 근사하기 어려운 수를 고르면 어떤 격자·주기와도 최대한 어긋나므로, 공명은 가장 늦게 오고 표본은 가장 고르게 퍼진다. 해바라기가 이걸 먼저 발견했다는 게 매번 억울한 부분. ↩
순정 5도를 12번 쌓으면 7옥타브에 정확히 안 맞고 약 23.5센트가 남는데, 이게 그 유명한 피타고라스 콤마다. 콤마의 정체는 “ $7/12$ 가 $\log_2(3/2)$ 의 완벽한 값이 아니라 수렴분수일 뿐”이라는 사실 그 자체다. 무리수를 유리수로 근사한 대가를 3천 년째 귀로 듣고 있는 셈. ↩
연분수 평가에서 언더플로 방지용 상수 $10^{-30}$ 이 아무 근거 없어 보이지만, 실제로는 “배정밀도 최소 정규수보다 한참 크면서 어떤 실제 계수보다도 작은” 값이면 무엇이든 된다. 이 알고리즘이 40년째 살아 있는 이유의 절반은 이 뻔뻔한 한 줄 덕분이다. ↩
급수와 연분수의 경계를 어디로 잡느냐는 라이브러리마다 다르고, 대개 논문이 아니라 누군가의 수치실험 결과가 상수로 굳어 있다. 불완전 감마함수의 $x < a+1$ 경계 같은 것이 대표적. 왜 그 값인지 주석에 안 적혀 있으면 파헤치지 말고 그냥 쓰는 편이 정신 건강에 이롭다. ↩

연분수