스피곳 알고리즘

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

예제[편집]

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

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

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

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에 비례해서 증가한다.

바깥 고리[편집]