Jump to content

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

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

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

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

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

Пример [ править ]

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

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

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

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

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

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

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

поэтому двоичные цифры с 8 по 11 в двоичном представлении ln(2) равны 1, 0, 1, 1. Обратите внимание, что мы не вычисляли значения первых семи двоичных цифр – более того, вся информация о них была намеренно отброшена. используя модульную арифметику в «головной» сумме.

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

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

  1. ^ Продажа, AHJ (1968). «Вычисление е до многих значащих цифр» . Компьютерный журнал . 11 (2): 229–230. дои : 10.1093/comjnl/11.2.229 .
  2. ^ Абдали, С. Камаль (1970). «Суммирование специальных рядов с произвольной точностью» (PDF) . Коммуникации АКМ . 13 (9): 570. дои : 10.1145/362736.362756 .
  3. ^ Рабиновиц, Стэнли; Вагон, Стэн (1995). «Алгоритм втулки для цифр числа Пи» (PDF) . Американский математический ежемесячник . 102 (3): 195–203. дои : 10.2307/2975006 . JSTOR   2975006 . Проверено 8 мая 2013 г.
  4. ^ Гиббонс, Джереми (24 мая 2004 г.). «Алгоритмы неограниченного соединения для цифр числа Пи» (PDF) .

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

Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: f859e051797a347f0437384eba065e63__1690587840
URL1:https://arc.ask3.ru/arc/aa/f8/63/f859e051797a347f0437384eba065e63.html
Заголовок, (Title) документа по адресу, URL1:
Spigot algorithm - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)