스피곳 알고리즘

스피곳 알고리즘(spigot algorithm)은 π나 e 등의 수학 상수를 계산할 때 쓰이는 알고리즘으로, 상수의 특정 자리 값을 구하기 위해 이전 자리를 구하지 않아도 되는 특성을 가진다. 스피곳 알고리즘의 대표적인 예는 π값을 구하는 Bailey-Borwein-Plouffe 공식이다.

예제

이 예제에서는 자연 로그 2 값을 이진수로 구하는 스피곳 알고리즘을 설명한다. 먼저 자연 로그의 항등식 $\ln {\frac {x}{x-1}}=\sum _{k=1}^{\infty }{\frac {1}{kx^{k}}}$에 의해 다음 식을 얻는다.

$\ln(2)=\sum _{k=1}^{\infty }{\frac {1}{k2^{k}}}\,.$

자연 로그 2의 소수점 아래 8번째부터 이진수 자리를 구하기 위해 양변을 2⁷으로 곱한다.

$2^{7}\ln(2)=2^{7}\sum _{k=1}^{\infty }{\frac {1}{k2^{k}}}\,.$

무한 합을 정수 부분(2의 지수가 0 이상인 부분)과 소수 부분(2의 지수가 음수인 부분)으로 나눈다.

$2^{7}\ln(2)=\sum _{k=1}^{7}{\frac {2^{7-k}}{k}}+\sum _{k=8}^{\infty }{\frac {1}{k2^{k-7}}}\,.$

우리는 소수 부분에만 관심이 있으므로, 정수 부분을 다음과 같이 바꿔 쓸 수 있다.

${\frac {2^{7-k}\mod k}{k}}\,.$

이 항들을 계산하여 총합을 계산하면 다음과 같이 된다.

k	A = 27-k	B = A mod k	C = B / k	C mod 1 의 합
1	64	0	0	0
2	32	0	0	0
3	16	1	1/3	1/3
4	8	0	0	1/3
5	4	4	4/5	2/15
6	2	2	1/3	7/15
7	1	1	1/7	64/105

몇 개의 소수 부분 항을 더해준다.

k	D = 1/k2k-7	D 의 합	최대 오차
8	1/16	1/16	1/16
9	1/36	13/144	1/36
10	1/80	37/360	1/80

정수 부분 항을 먼저 더하고, 소수 부분 항의 처음 몇개를 더하면 다음과 같이 된다.

$2^{7}\ln(2)\mod {1}\approx {\frac {64}{105}}+{\frac {37}{360}}=0.10011100\cdots _{2}+0.00011010\cdots _{2}=0.1011\cdots _{2}\,,$

따라서 ln(2)를 이진수로 표현했을 때 소수점 이하 8번째에서 11번째 자리는 1, 0, 1, 1이 된다. 앞의 7자리를 구하지 않고도 8번째 자리부터 구했다는 것에 주목하라.

같은 방법으로 ln(2)의 n번째 자리의 수를 계산할 수 있다. 계산해야 할 정수 부분 항의 개수는 n에 비례해서 증가하지만, 효율적인 모듈라 지수 연산 방법을 사용한다면 복잡도는 log n에 비례해서 증가한다.

외부 링크

• Weisstein, Eric Wolfgang. “스피곳 알고리즘”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• “Pi를 스피곳 알고리즘을 사용하여 구하기(영어)” (PDF).