Алгоритм патрубка

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

Интерес к алгоритмам с патрубками был вызван на заре вычислительной математики крайними ограничениями на память, и такой алгоритм для вычисления цифр е появился в статье Сейла в 1968 году. В 1970 году Абдали представил более общий алгоритм вычисления сумм рядов, в котором отношения последовательных членов могут быть выражены как частные целочисленных функций позиций терминов. Этот алгоритм применим ко многим знакомым рядам для тригонометрических функций, логарифмов и трансцендентных чисел, поскольку эти ряды удовлетворяют указанному выше условию. Название «алгоритм втулки», по-видимому, было придумано Стэнли Рабиновичем и Стэном Вагоном , чей алгоритм вычисления цифр числа π иногда называют « алгоритмом втулки для числа π ».

Алгоритм патрубка Рабиновица и Вагона ограничен в том смысле, что количество членов бесконечного ряда, которые будут обрабатываться, должно быть указано заранее. Термин «потоковый алгоритм» указывает на подход без этого ограничения. Это позволяет выполнять расчет бесконечно, изменяя объем промежуточной памяти по мере выполнения расчета.

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

Пример

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

$\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 больше или равны нулю, и «хвост», в котором показатели степени 2 отрицательны:

$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}}{k}}{\bmod {1}}={\frac {2^{7-k}{\bmod {k}}}{k}}\,.$

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

к	А = 2 7− к	B = A mod 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

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

к	Д = 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

Сложив «голову» и первые несколько членов «хвоста», мы получаем:

$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, эффективный метод модульного возведения в степень если используется . Точность арифметика с вычислений и промежуточных результатов, а также количество членов, взятых из «хвостовой» суммы, не зависят от n и зависят только от количества вычисляемых двоичных цифр - одинарной точностью может использоваться для вычисления около 12 двоичных цифр. цифры, независимо от начальной позиции.

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

• Арндт, Йорг; Хэнель, Кристоф, π unleashed , Springer Verlag, 2000.
• Вайсштейн, Эрик В. «Алгоритм патрубка» . Математический мир .