Алгоритм втулки - Spigot algorithm

А алгоритм патрубка является алгоритм для вычисления значения трансцендентного числа (например, π или же е ), который генерирует цифры числа последовательно слева направо, обеспечивая возрастающую точность по мере выполнения алгоритма. Алгоритмы Spigot также стремятся минимизировать объем требуемой промежуточной памяти. Название происходит от значения слова «кран» для кран или клапан контроль потока жидкости. Алгоритмы втулки можно противопоставить алгоритмам, которые хранят и обрабатывают полные числа, чтобы последовательно производить более точные приближения к желаемому трансцендентному.

Интерес к алгоритмам втулки был подстегнут на заре вычислительной математики крайними ограничениями на память, и такой алгоритм для вычисления цифр е появилась в газете Sale в 1968 году.^[1] Название «алгоритм патрубка», похоже, было придумано Стэнли Рабиновиц и Стэн Вагон, чей алгоритм вычисления цифр π иногда упоминается как "то втулочный алгоритм для π".^[2]

Алгоритм втулки Рабиновица и Вагона: ограниченный, в том смысле, что количество слагаемых бесконечного ряда, которые будут обрабатываться, необходимо указать заранее. Термин «потоковый алгоритм» (Джереми Гиббонс (2004)^[3]) обозначает подход без этого ограничения. Это позволяет выполнять расчет неограниченно, изменяя объем промежуточной памяти по мере выполнения расчета.

Вариант подхода с патрубком использует алгоритм, который можно использовать для вычисления одной произвольной цифры трансцендентного без вычисления предшествующих цифр: примером является Формула Бейли – Борвейна – Плуфа, алгоритм извлечения цифр для π который дает основание 16 цифр. Неизбежное усечение лежащей в основе бесконечной серии алгоритма означает, что точность результата может быть ограничена количеством вычисляемых членов.

Пример

Этот пример иллюстрирует работу алгоритма втулки путем вычисления двоичных цифр натуральный логарифм из 2 (последовательность A068426 в OEIS ) используя тождество

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

Чтобы начать вычисление двоичных цифр, например, с 8-го места, мы умножаем это тождество на 2⁷ (поскольку 7 = 8-1):

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

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

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

Нас интересует только дробная часть этого значения, поэтому мы можем заменить каждое из слагаемых в «голове» на

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

Рассчитывая каждый из этих членов и добавляя их к промежуточной сумме, где мы снова сохраняем только дробную часть, мы имеем:

k	А = 27−k	B = А мод 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}} приблизительно { 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. Обратите внимание, что мы не вычислили значения первых семи двоичных цифр - действительно, вся информация о них была намеренно отброшена используя модульная арифметика в «головной» сумме.

Тот же подход можно использовать для вычисления цифр двоичного разложения ln (2), начиная с произвольного п^th позиция. Количество слагаемых в «головной» сумме линейно увеличивается с увеличением п, но сложность каждого члена увеличивается только с логарифмом п если эффективный метод модульное возведение в степень используется. В точность расчетов и промежуточных результатов, а также количество членов, взятых из «хвостовой» суммы, не зависят от п, и зависят только от количества вычисляемых двоичных цифр - одинарная точность арифметика может использоваться для вычисления около 12 двоичных цифр, независимо от начальной позиции.

Рекомендации

дальнейшее чтение

• Арндт, Йорг; Хенель, Кристоф, π развязанный, Springer Verlag, 2000.
• Вайсштейн, Эрик В. «Алгоритм втулки». MathWorld.