Continued Fraction은 다음과 같은 꼴로 실수를 표현하는 것을 의미합니다.
\[a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{...}}}\]유리수에 대해서는 유한하며, 2차 방정식의 해로 나타낼 수 있는 수에 대해서는 $a_n$이 일정 값을 반복되는 형태가 됩니다.
간단한 구조로 수를 표현할 수 있으면 그 수에 대한 continued fraction을 계산할 수 있습니다. 예로 $\sqrt{2}$의 경우도 제곱하면 2라는 특징을 이용해 대소비교를 할 수 있어서 python 언어처럼 자연수의 overflow가 없다는 가정 하에 정확하게 $\sqrt2$의 continued fraction, 더 나아가 루트를 이용해 표현할 수 있는 실수에 대해서 계산이 가능합니다.
그런데, 이런 수 뿐만 아니라 파이나 e(자연로그의 밑)처럼 무리수.. 특히 초월수처럼 값을 확실하게 표현할 수 없는 수들은 이런 Continued Fraction을 어떻게 계산할 지에 대해서 고민해 보기로 했습니다.
어떤 수가 되었건 근사값을 계산한 다음, 정수 부분 추리고, 소수점의 역수를 계산한 뒤, 다시 정수 부분을 계산하는 식으로 값을 계산할 수는 있지만, 역수를 계산하면서 생기는 round off error를 경계하게 되었습니다. 그래서 이걸 어떻게 하면 최대한 정확하게 계산할 수 있을지에 대해서 고민하게 되었습니다.
아이디어는 간단합니다. continued fraction이 한 depth가 추가될 때마다 최종 값을 쉽게 계산할 수 있다는 것에 있습니다. 만약, $a_n$까지만 있는 continued fraction의 경우 $\frac{p_n}{q_n}$라고 했을 때, $a_{n+1}$을 추가했을 때, 다음 continued fraction의 최종 값은 다음과 같습니다.
\[\frac{p_{n+1}}{q_{n+1}} = \frac{p_{n-1} + p_n a_{n+1}}{q_{n-1}+ q_n a_{n+1}}\]그리고 또 하나가 있습니다. 실수 자체를 두 유리수 사이에 있다는 정보만 가지고 있으면 $p_n / q_n$ 값에서 $a_{n+1}$을 선택할 때 구간 사이에 있도록 조정해서 값을 선택할 수 있습니다.
그렇다면, 원주율, 파이의 경우 어떻게 그 구간을 정할 수 있을까요? 여기서는 이 값을 구하기 위해서 Machin-like formula를 이용했습니다. Arctan의 합으로 파이를 표현하는 것을 의미합니다. Machin-like formula에 대해서는 좀 더 이야기 해 볼 기회가 있을 거 같습니다. 여기서는 가장 간단한 형태인 다음 식을 이용하기로 했습니다.
\[\frac{\pi}{4} = \arctan{\frac{1}{2}} + \arctan{\frac{1}{3}}\]Arctan자체가 +와 -가 반복되다 보니 이걸 이용해서 다음 항을 계산해 파이가 어디에 있겠다는 구간을 점점 더 좁힐 수 있습니다. Arctan의 테일러 전개식을 보면서 얘기해 보겠습니다.
\[\arctan(x) = x - \frac{1}{3} x^3 + \frac{1}{5} x^5 - ...\]저 전개식에서 $n$항까지 합친 값을 $A_n(x)$라 하겠습니다. $A_2(x) = x - \frac{1}{3} x^3$이 되는 식이죠. $x$가 0과 1 사이의 값이라 가정하겠습니다. 처음에는 $\arctan(x)$의 값이 0과 $x$사이에 있다는 것을 알 수 있습니다. 좀 더 자세한 값을 알고 싶다면, 그 다음 항을 계산하면 됩니다. 그래서 $\arctan(x)$의 값이 $A_2(x)$와 $x$사이에 있다는 것을 알 수 있습니다. 진행하다 보면 절대값이 계속 작아지면서 덧셈 뺄셈이 계속되는 형태입니다. 더 좁은 구간이 필요하다면 다음항을 계산하면 됩니다. $A_2(x)$와 $x$ 사이에 있으니 다음항을 계산하면 $A_2(X)$와 $A_3(x)$ 사이에 있고 다음은 $A_4(x)$와 $A_3(x)$ 사이에 있는 식으로 점점 필요한 만큼 좁여가면 됩니다.
이 값은 최고의 식이 있습니다.
\[e^x = 1 + x + \frac{1}{2}x^2 + \frac{1}{3!}x^3 + ...\]여기도 $n$항 까지의 합을 $E_n(x)$이라고 했을 때, 구간을 $E_n(x)$에서 $E_{n+1}(x)$로 했을 때 점점 더 좁아질 것입니다.
원주율의 경우 oeis에서 나온 값과 비교했습니다. e의 경우 잘 알려진 규칙이 있습니다. $a_n$이 1, 2, 1, 1, 4, 1, … 처럼 1, $2n$, 1 이 사이클이 반복되기 때문입니다.
실제 구현은 Gist 에서 확인할 수 있습니다.