이 글에서는 로그의 근삿값을 구하는 여러 알고리즘에 대해 소개한다.
네이피어는 로그의 발견과 동시에 로그표를 작성했다. 그가 처음 만들었던 로그는 지금보다는 형태가 복잡했기에, 지금은 당시 로그보다 많이 정돈된 형태의 로그를 사용하고 있고, 계산기가 발전하기 전까지는 그에 따른 로그표를 이용해서 복잡한 로그의 계산을 수행했다. 지금은 그 계산과정이 프로그램되어 계산기에 들어가 있다. 그동안 많은 계산법이 고안되었기 때문에 로그값을 계산하는 방법은 계산기에 따라 조금씩 다른 알고리즘이 사용된다. 계산법은 크게 세 가지 정도로 분류할 수 있다. 미적분을 이용하는 법, 미리 계산된 값을 이용하는 법, 번분수를 이용하는 법 등이 있다.[1]
[1] G. R. Rising, Inside Your Calculator: From Simple Programs to Significant Insights, Wiley-Interscience, 2007.
1. 미적분을 이용하는 방법
가장 간편하면서도 많이 알려진 방법은 미적분의 결과를 이용하는 방법으로, 테일러 급수라는 다음 식을 활용한다. $$\ln(1+x) = x - \frac 1 2 x^2 + \frac 1 3 x^3 - \cdots$$ 위 식 좌변은 오일러수 혹은 네이피어수라고도 하는 무리수 $e$를 밑으로 가지는 로그를 말한다. 아래 그림을 보면 $x$가 0에 가깝고 많은 항을 사용할수록 로그값이 잘 근사됨을 확인할 수 있다.
2. 미리 계산된 값을 이용하는 방법
미리 계산된 값을 이용하는 방법은 휴대용 계산기나 속도가 느린 컴퓨터에서 사용되는 방법이다. 네이피어가 처음 로그표를 만들 때도 이 방법과 비슷한 아이디어를 사용했으며, 파인만도 2차 세계대전 당시 맨해튼 프로젝트에 참가했을 때 상용로그 값을 구하는 방법으로 아이디어를 냈던 방법이다.[2] 이 방법은 문서마다 약간 다른 모델로 설명들을 하는데, 근본적으로 $\log x$의 값을 구하기 위해 다음을 만족하는 수열 $a_k$($k= 0$, $\pm 1$, $\pm 2$, $\cdots$)을 먼저 얻어낸다. $$ x \times \prod_k \left( 1+ a_k 2^{-k} \right) \fallingdotseq 1 \quad \quad (a_k \text{는 }0, 1, -1 \text{중 어느 하나})$$ 이 식이 사용되는 알고리즘에 주어지는 조건에 따라 $a_k$는 달라진다. 이 수열의 모든 항을 구하는 것은 아니고, 근삿값을 구하려는 정밀도에 맞게 수열을 구한다. 그러면 위 식은 $$ \log x \fallingdotseq - \sum_k \log \left( 1+ a_k 2^{-k} \right)$$ 와 같이 정리할 수 있으므로 미리 구해둔 $\log (1 \pm 2^k)$ 값들을 적당히 더하고 빼주면 $\log x$의 근삿값을 구할 수 있다.
[2] Hillis, Danny, Richard Feynman and the Connection Machine, Physics Today 42 (1989).
3. 번분수 사용법
앞에서 설명한 방법 외에 번분수를 이용한 방법이 있다. 대표적인 문서는 샹크스가 소개했던 방법이다.[3] 손으로 계산하기에는 아마 이 방법이 가장 쉬울 것이다. 내용은 다음과 같다. 여기서는 로그값이 유리수가 되지 않는 경우만 다루므로 부등식에서 등호는 편의상 빼서 설명하겠다.
[3] 다니엘 샹크스는 미국의 수학자로 역사상 처음으로 원주율 $\pi$의 값을 소수점 아래 10만 자리까지 구했다.
$a_0 > a_1 >1$인 두 실수에 대해 $\log_{a_0} a_1$을 구하는 것을 목표로 한다. 이것만 구해도 다른 모든 경우의 근삿값을 구할 수 있다. 우선, \begin{equation} \label{step1} a_1^{n_1} < a_0 < a_1^{n_1 + 1} \end{equation} 인 관계를 만족하는 자연수 $n_1$을 구한다. 그러고 \begin{equation} \label{step2} a_2 = \frac {a_0} {a_1^{n_1}} \end{equation} 이라 한다. 이제, 다시 \begin{equation} \label{step3} a_2^{n_2} < a_1 < a_2^{n_2 + 1} \end{equation} 을 만족하는 자연수 $n_2$를 구하고 다시 \begin{equation*} a_3 = \frac {a_1} {a_2^{n_2}} \end{equation*} 이라 한다. 이렇게 $n_k$, $a_k$를 구해가면서 최종 계산을 준비하는데, 도대체 무슨 일이 벌어지고 있는지 정리를 해보자.
우선 식 (\ref{step1})에 의해 \begin{equation*} a_0 = a_1^{n_1 + \frac 1 {x_1}} \quad (x_1 > 1) \end{equation*} 인 실수 $x_1$을 생각할 수 있다. 이 단계에서 \begin{equation} \label{temp1} \log_{a_0} a_1 = \frac 1 {n_1 + \dfrac 1 {x_1}} \end{equation} 이 된다. 한편 식 (\ref{step2})에 의해 \begin{equation*} a_2 = a_1^{\frac 1 {x_1}}, \quad \quad \text{즉,} \quad \quad a_1 = a_2^{x_1} \end{equation*} 이므로 식 (\ref{step3})에 따르면 다음과 같은 관계식을 얻어낼 수 있다. \begin{equation*} a_1 = a_2^{n_2 + \frac 1 {x_2}}, \quad \quad x_1 = n_2 + \frac 1 {x_2}, \quad \quad x_2 > 1 \end{equation*} 여기까지의 결과를 식 (\ref{temp1})에 반영하면 다음과 같은 식을 얻는다. \begin{equation*} \log_{a_0} a_1 = \frac 1 {n_1 + \dfrac 1 {x_1}} = \frac 1 {n_1 + \dfrac 1 {n_2 + \dfrac 1 {x_2} }} \end{equation*} 이렇게 계속 반복하면 다음과 같은 식이 얻어진다. \begin{equation} \label{contFrtn} \log_{a_0} a_1 = \frac 1 {n_1 + \dfrac 1 {n_2 + \dfrac 1 { n_3 + \dfrac 1 \ddots } }} \end{equation}
예제
이제, $\log 2$의 값을 구해보자. $a_0 = 10$, $a_1 =2$인 상태다. $$2^3 < 10 < 2^4$$ 이므로 $n_1 =3$이고 $a_2 = \dfrac {10} {2^3} = \dfrac 5 4$다. 여기서 $$ \left( \frac 5 4 \right)^3 < 2 < \left( \frac 5 4 \right)^4$$ 이므로 $n_2 =3$이고 $a_3 = 2 \div \left( \dfrac 5 4 \right)^3 = \dfrac {128}{125}$이다. 이 과정을 계속하면 $n_3 = 9$, $n_4 = 2$, $n_5 = 2$, $\cdots$가 얻어진다. 실제 얼마나 빨리 수렴하는지 확인하기 위해 $$c_k = \frac 1 {n_1 + \dfrac 1 {n_2 + \dfrac 1 {n_3 + \dfrac 1 {\ddots + \dfrac 1 {n_k}}}}}$$ 를 계산해보면 \begin{align*} c_1 &= \frac 1 3 \fallingdotseq 0.3333 \\ c_2 &= \frac 3 {10} \fallingdotseq 0.3000 \\ c_3 &= \frac {28}{93} \fallingdotseq 0.3011 \\ c_4 &= \frac {59}{196} \fallingdotseq 0.3010 \\ & \vdots \end{align*} 과 같이 빠른 속도로 참값에 가까워짐을 알 수 있다.
이 알고리즘을 이용한 코딩 가이드는 다음 논문에서 확인할 수 있다.
D. Shanks, A logarithm algorithm, Math. Tables and Other Aids to Computation 8 (1954).
Terence Jackson and Keith Matthews, On Shanks’ Algorithm for Computing the Continued Fraction of $\log_b a$ http://www.numbertheory.org/pdfs/log.pdf