스피곳 알고리즘 문서 원본 보기

{{위키데이터 속성 추적}}
'''스피곳 알고리즘'''(spigot algorithm)은 [[원주율|π]]나 [[자연로그의 밑|e]] 등의 [[수학 상수]]를 계산할 때 쓰이는 [[알고리즘]]으로, 상수의 특정 자리 값을 구하기 위해 이전 자리를 구하지 않아도 되는 특성을 가진다.
스피곳 알고리즘의 대표적인 예는 π값을 구하는 [[Bailey-Borwein-Plouffe 공식]]이다.

== 예제 ==

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

:<math>\ln(2)=\sum_{k=1}^{\infty}\frac{1}{k2^k}\, .</math>

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

:<math>2^7\ln(2) =2^7\sum_{k=1}^{\infty}\frac{1}{k2^k}\, .</math>

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

:<math>2^7\ln(2) =\sum_{k=1}^{7}\frac{2^{7-k}}{k}+\sum_{k=8}^{\infty}\frac{1}{k2^{k-7}}\, .</math>

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

:<math>\frac{2^{7-k} \mod k}{k}\, .</math>

이 항들을 계산하여 총합을 계산하면 다음과 같이 된다.
:{| class="wikitable"
|-
! ''k''
! ''A'' = 2<sup>7-''k''</sup>
! ''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/''k''2<sup>''k''-7</sup>
! ''D'' 의 합
! 최대 오차
|-
| 8
| 1/16
| 1/16
| 1/16

|-
| 9
| 1/36
| 13/144
| 1/36
|-
| 10
| 1/80
| 37/360
| 1/80
|}

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

:<math>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}\, ,</math>

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

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

== 외부 링크 ==
* {{매스월드|id=SpigotAlgorithm|title=스피곳 알고리즘}}
* {{웹 인용|url=http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/spigot.pdf|title=Pi를 스피곳 알고리즘을 사용하여 구하기(영어)}}

{{전거 통제}}

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