스피것 알고리즘

스피것 알고리즘은 알고리즘이 진행됨에 따라 증가하는 정밀도를 제공하는 왼쪽에서 오른쪽으로 순차적으로 숫자의 숫자를 생성하는 초월수 값( ( 또는 e 등)을 계산하는 알고리즘이다.스피것 알고리즘은 또한 필요한 중간 저장소의 양을 최소화하는 것을 목표로 한다.그 이름은 액체의 흐름을 조절하는 수돗물이나 밸브에 대한 "spigot"이라는 단어에서 유래되었다.스피것 알고리즘은 완전한 숫자를 저장하고 처리하여 원하는 초월에 대한 보다 정확한 근사를 연속적으로 산출하는 알고리즘과 대조될 수 있다.

스피것 알고리즘에 대한 관심은 기억력에 대한 극단적인 제약에 의해 연산수학 초기부터 자극되었고, 1968년 Sale의 논문에 e의 숫자를 계산하는 알고리즘이 등장했다.^[1]1970년에 압달리는 연속된 항들의 비율이 항 위치의 정수 함수의 인수로 표현될 수 있는 시리즈의 합계를 계산하기 위해 보다 일반적인 알고리즘을 제시했다.이 알고리즘은 삼각함수, 로그, 초월수 등에 대해 익숙한 많은 시리즈에 적용할 수 있다. 이들 시리즈가 위의 조건을 만족하기 때문이다.^[2]스피것 알고리즘이란 이름은 스탠리 라비노위츠와 스탠 왜건이 만든 것으로 보이는데, 그의 숫자 계산 알고리즘은 π의 스피것 알고리즘이라고 부르기도 한다.^[3]

라비노위츠와 왜건의 스피것 알고리즘은 처리될 무한 계열의 용어 수를 미리 명시해야 한다는 의미에서 경계한다."스트리밍 알고리즘"^[4]이라는 용어는 이러한 제한이 없는 접근방식을 나타낸다.이를 통해 계산이 진행됨에 따라 중간 저장량을 무한정 변경할 수 있다.

스피것 접근법의 변형은 앞의 숫자를 계산하지 않고 초월체의 임의의 단일 자릿수를 계산하는데 사용할 수 있는 알고리즘을 사용한다. 예를 들면 베이스 16자리를 생성하는 π의 숫자 추출 알고리즘인 Bailey-Borwein-Pluffe 공식이다.알고리즘의 기본 무한 계열의 불가피한 절단은 결과의 정확도가 계산된 항 수에 의해 제한될 수 있다는 것을 의미한다.

예

이 예는 ID를 사용하여 2의 자연 로그(OEIS에서 순서 A068426)의 이진수를 계산하여 스피것 알고리즘의 작동을 예시한다.

${\displaystyle \ln(2)=\sum _{k=1}^{\inflt }{{1}{k2^{k}}\,}$

예를 들어, 2진수 계산을 시작하려면 8위부터 이 ID를 2로⁷ 곱하십시오(7 = 8 - 1 이후).

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

그런 다음 무한 합계를 2의 지수가 0보다 크거나 같은 "머리"와 2의 지수가 음의 "꼬리"로 나눈다.

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

우리는 이 가치의 극히 일부분에만 관심이 있기 때문에, "헤드"에 있는 각 요약을 다음과 같이 대체할 수 있다.

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

이러한 각 항을 계산하여 실행 중인 총계에 추가하면 다시 부분만 유지되며, 다음과 같은 결과를 얻을 수 있다.

k	A = 27−k	B = A mod k	C = B / k	C모드 합계 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

"머리"와 "꼬리"의 처음 몇 용어를 함께 추가하면 다음과 같은 이점을 얻을 수 있다.

${\displaystyle 2^{7}\ln(2){\bmod{1}}}{{64}}}}+{\frac {37}{360}}=0.10011100\ldots _{2}+0.00011010\ldots _{2}=0.1011\ldots _{2}$

따라서 ln(2)의 이진 확장에서 8번째에서 11번째 이진수는 1, 0, 1, 1이다. 참고로 우리는 처음 7개의 이진수의 값을 계산하지 않았다. 실제로, 그것들에 대한 모든 정보는 "head" 합계의 모듈식 산수를 사용하여 의도적으로 폐기되었다.

임의 n 위치에서^th 시작하는 ln(2)의 이진 확장 자릿수를 계산하는 데도 동일한 접근법을 사용할 수 있다."head" 합계의 항 수는 n과 함께 선형적으로 증가하지만, 각 항의 복잡성은 모듈형 지수의 효율적인 방법을 사용하는 경우에만 n의 로그에 따라 증가한다.계산의 정밀도와 중간 결과 및 "꼬리" 합에서 얻은 항 수는 모두 n과 무관하며 계산되는 이진수 숫자에만 의존한다 – 단일 정밀 산술은 시작 위치와 관계없이 12개의 이진수 정도 계산에 사용할 수 있다.

참조

추가 읽기

• 아른트, 호르그; 해넬, 크리스토프, 2000년 스프링거 베를라그.
• Weisstein, Eric W. "Spigot algorithm". MathWorld.