Алгоритм втулки

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

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

Алгоритм втулки Рабиновица и Вагона ограничен в том смысле, что количество элементов бесконечного ряда, которые будут обрабатываться, должно быть указано заранее. Термин «алгоритм потоковой передачи» ^[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	А = 2 7− к	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	15.07
7	1	1	1/7	64/105

Мы добавляем несколько членов в «хвост», отмечая, что ошибка, вызванная усечением суммы, меньше последнего члена:

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

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Арндт, Йорг; Хенель, Кристоф, π unleashed , Springer Verlag, 2000.
• Вайсштейн, Эрик В. "Алгоритм Spigot" . MathWorld .