실수의 소수점 아래 $n$번째 자리 구하기

이 글은 Fabrice Bellard의 글 Computation of the n’th digit of pi in any base in O(n^2)을 정리한 것입니다. 멋대로 정리한 거라 기호가 좀 다릅니다.

유리수의 소수점 아래 $n$번째 자리 구하기

어떤 양의 유리수 $s$를 기약분수로 나타내면 $\frac{A}{M}$이라고 합시다. 이때 $M$을 다음과 같이 분해할 수 있습니다.

\[ M=m_1m_2\cdots m_k, \quad \mathrm{gcd}(m_i, m_j)=1 \ \ \text{for} \ \ i\neq j \]

예를 들면,

\[ M=6552=2^3\times3^2\times7\times13 \quad \Rightarrow \quad m_1=2^3,\ m_2=3^2,\ m_3=7,\ m_4=13 \]

한편 $A$를 $m_i$로 나눈 나머지를 $a_i$라 하면

\[ \begin{align}
A &\equiv a_1 \pmod{m_1} \\
A &\equiv a_2 \pmod{m_2} \\
& \qquad\quad\ \vdots \\
A &\equiv a_k \pmod{m_k}
\end{align} \]

이므로 중국인의 나머지 정리에 의하여

\[ A \equiv \sum_{i=1}^k M_i(M_i^{-1} \ \mathrm{mod} \ {m_i})a_i \pmod M, \quad M_i = \frac{M}{m_i} \]

따라서

\[ s \equiv \frac{A}{M} \equiv \sum_{i=1}^k \frac{M_i(M_i^{-1} \ \mathrm{mod} \ {m_i})a_i}{M}
\equiv \sum_{i=1}^k \frac{(M_i^{-1} \ \mathrm{mod} \ {m_i})a_i}{m_i} \pmod 1 \]

여기서 법 1에 대한 합동은 소수부분이 같음을 의미합니다. $x$와 $y$를 $m$으로 나눈 나머지가 같다면 자명하게 $x/m$과 $y/m$의 소수부분은 같겠죠.

이제 $D_n$을 다음과 같이 정의하면

\[ D_n = sB^n \ \mathrm{mod} \ 1\]

$D_n$의 각 자리는 $B$진법에서 $s$의 소수점 아래 $n+1$, $n+2$, …번째 자리와 동일합니다. 위 식에 의해

\[ D_n \equiv sB^n \equiv \sum_{i=1}^k \frac{B^n(M_i^{-1} \ \mathrm{mod} \ {m_i})a_i}{m_i} \pmod 1 \]

또는 $x/m$의 소수부분과 $(x \ \mathrm{mod} \ m)/m$의 소수부분이 같으므로

\[ D_n \equiv
\sum_{i=1}^k \frac{(B^n \ \mathrm{mod}\ m_i)(M_i^{-1} \ \mathrm{mod} \ {m_i})a_i}{m_i} \pmod 1 \]

최종적으로 $s$의 소수점 아래 $n$번째 자리는 $BD_{n-1}$의 정수 부분이 됩니다.

예시

$s=\frac{55}{84}$의 소수점 아래 $n$자리를 구해봅시다. 먼저 $M=84$는 아래와 같이 분해됩니다.

\[ M=84=2^2\times3\times7 \quad \Rightarrow \quad m_1=2^2,\ m_2=3,\ m_3=7 \]

그리고 각 $a_i$, $M_i$와 $M_i^{-1} \ \mathrm{mod} \ m_i$는

\[ \begin{align}
a_1 &= 3 & M_1 &= 21 & M_1^{-1}\ \mathrm{mod}\ m_1 &= 1 \\
a_2 &= 1 & M_2 &= 28 & M_2^{-1}\ \mathrm{mod}\ m_2 &= 1 \\
a_3 &= 6 & M_3 &= 12 & M_3^{-1}\ \mathrm{mod}\ m_3 &= 3
\end{align} \]

이므로 $D_n$ 식에 대입하면

\[ D_n = \left[\frac{3 (B^n\ \mathrm{mod}\ 4)}{4}
+\frac{B^n\ \mathrm{mod}\ 3}{3}
+\frac{18(B^n\ \mathrm{mod}\ 7)}{7}\right] \ \mathrm{mod}\ 1 \]

$B=10$, $n=20$이면

\[ \begin{align}
D_{20} &= \left[\frac{3(10^{20}\ \mathrm{mod}\ 4)}{4}
+\frac{10^{20}\ \mathrm{mod}\ 3}{3} + \frac{18(10^{20}\ \mathrm{mod}\ 7)}{7}\right]\ \mathrm{mod}\ 1 \\
&= \left[\frac{0}{4} + \frac{1}{3} + \frac{72}{7}\right]\ \mathrm{mod}\ 1 \\
&= \left[0 + 0.333333333\cdots + 10.285714285\cdots\right]\ \mathrm{mod}\ 1 \\
&= 0.619047619\cdots
\end{align} \]

따라서 $s$의 소수점 아래 21번째 자리는 6입니다. $s=0.65\overline{476190}$이므로 비교해보면 맞죠. ■

마지막에 실수 연산이 들어가긴 하는데 실제로 짜보면 의외로 실수 오차에 안 걸립니다.