스피곳 알고리즘

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

 예제 

이 예제에서는 자연 로그 2 값을 이진수로 구하는 스피곳 알고리즘을 설명한다.
먼저 자연 로그의 항등식 에 의해 다음 식을 얻는다.

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

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

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

이 항들을 계산하여 총합을 계산하면 다음과 같이 된다.
{| class="wikitable"
|-
! 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
|}

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

{| class="wikitable"
|-
! 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
|}

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

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

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

 외부 링크 



분류:컴퓨터 산술 알고리즘