Spigot алгоритм

Spigot Алгоритм (упоминается также как "алгоритм крана", или, что более точно, "алгоритм затвора", так как его работа похожа на движение затвора автомата, выбрасывающего очередной патрон) — алгоритм вычисления значения математических констант, например $\pi$ или e, который позволяет определить цифры в некоторой заранее выбранной системе счисления (обычно двоичной или с основанием в виде степени двойки) слева направо. Название происходит от английского слова "spigot", означающего кран или вентиль для управления потоком жидкости.

Интерес к Spigot алгоритму усилился в период раннего развития вычислительной математики из-за жестких ограничений на объемы памяти. Первый подобный алгоритм вычисления знаков числа e встречается в работе Артура Сейла (Arthur Harry John Sale) 1986 года[1]. Название "Spigot алгоритм" скорее всего придумали Стенли Рабинович и Стен Вагон[2].

Алгоритм предложенный Рабиновичем и Вагоном ограниченный в том смысле, что количество вычисляемых знаков должно быть определено заранее. Джереми Гиббонс (Jeremy Gibbons) в 2004г вводит обобщение под названием "потоковый алгоритм"[3], в котором вычисления можно проводить бесконечно долго, тем самым убрав ограниченность исходного алгоритма. Ещё одним улучшением Spigot алгоритма стал алгоритм, позволяющий вычислить конкретный знак без необходимости определения предыдущих знаков числа. Например, Формула Бэйли-Боруэйна-Плаффа для вычисления произвольных знаков в 16-ричной записи числа $\pi$ .

Пример

Продемонстрируем работу Spigot алгоритма на примере вычисления двоичных знаков натурального логарифма 2 на основе формулы:

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

Чтобы найти двоичные знаки начиная с 8-го, умножим число на 2⁷ (так как 7=8-1):

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

Затем разделим бесконечный ряд на "голову", в которой степень двойки больше или равна нулю, и "хвост" с отрицательными степенями:

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}({\bmod {k}})}{k}}\,.

Вычислим каждое слагаемое отдельно, отбрасывая целую часть:

k	A = 2^7−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

Вычислим несколько первых элементов из "хвоста". Выбираем такую часть этой суммы, чтобы ошибка вычисления была меньше искомого 7-го знака числа.

k	D = 1/k2^k−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)({\bmod {1}})\approx {\frac {64}{105}}+{\frac {37}{360}}=0.10011100\ldots _{2}+0.00011010\ldots _{2}=0.1011\ldots _{2}\,,

таким образом цифры с 8-й по 11-ю в двоичной записи числа $\ln(2)$ являются 1, 0, 1, 1. Заметьте, что мы не вычисляли значения предыдущих семи цифр. Информация об этих цифрах была умышленно отброшена при использовании модульной арифметики при вычислении "головы".

Данный подход можно использовать для вычисления произвольного n-го знака в двоичной записи числа ln(2). Количество слагаемых в "голове" линейно растёт с увеличением n, но сложность вычисления элементов растёт логарифмически при использовании методов возведения в степень по модулю. Точность вычисления, промежуточные вычисления и количество нужных слагаемых из "хвоста" не зависят от n, а зависят только от количества двоичных знаков, которые нужно вычислить. Используя дробные числа одинарной точности можно найти около 12 двоичных знаков, независимо от начальной позиции.

Примечания

Sale, AHJ. The calculation of e to many significant digits (англ.) // The Computer Journal : journal. — 1968. — Vol. 11, no. 2. — P. 229—230. — doi:10.1093/comjnl/11.2.229.
Rabinowitz, Stanley; Wagon, Stan. A Spigot Algorithm for the Digits of Pi (англ.) // American Mathematical Monthly : journal. — 1995. — Vol. 102, no. 3. — P. 195—203. — doi:10.2307/2975006.
Gibbons, Jeremy Unbounded Spigot Algorithms for the Digits of Pi (неопр.) (24 мая 2004).

Ссылки

Spigot Algorithm — from Wolfram MathWorld — страница алгоритма в каталоге MathWorld.
«Краник», или алгоритм для поиска цифр числа Пи — пример использования алгоритма для вычисления знаков $\pi$ .

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Sale, AHJ. The calculation of e to many significant digits (англ.) // The Computer Journal : journal. — 1968. — Vol. 11, no. 2. — P. 229—230. — doi:10.1093/comjnl/11.2.229.

[2] Rabinowitz, Stanley; Wagon, Stan. A Spigot Algorithm for the Digits of Pi (англ.) // American Mathematical Monthly : journal. — 1995. — Vol. 102, no. 3. — P. 195—203. — doi:10.2307/2975006.

[3] Gibbons, Jeremy Unbounded Spigot Algorithms for the Digits of Pi (неопр.) (24 мая 2004).