Spigot-алгоритм

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

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

Алгоритм, предложенный Рабиновичем и Вагоном, — ограниченный в том смысле, что количество вычисляемых знаков должно быть определено заранее. Джереми Гиббонс (Jeremy Gibbons) в 2004 г. вводит обобщение под названием «потоковый алгоритм», в котором вычисления можно проводить бесконечно долго, тем самым убрав ограниченность исходного алгоритма. Ещё одним улучшением 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 = 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

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

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)({\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 двоичных знаков независимо от начальной позиции.

Ссылки

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