Формула Бейли – Борвейна – Плуффа

Формула Бейли-Борвейна-Плуффа ( формула BBP ) представляет собой формулу для π . Он был открыт в 1995 году Саймоном Плуффом и назван в честь авторов статьи, в которой он был опубликован, Дэвида Х. Бэйли , Питера Борвейна и Плуффа. До этого его опубликовал Плуфф на своем сайте. Формула:

$\pi =\sum _{k=0}^{\infty }\left[{\frac {1}{16^{k}}}\left({\frac {4}{8k+1}}-{\frac {2}{8k+4}}-{\frac {1}{8k+5}}-{\frac {1}{8k+6}}\right)\right]$

Формула BBP приводит к появлению кольцевого алгоритма для вычисления n- й шестнадцатеричной (шестнадцатеричной) цифры числа π (и, следовательно, также 4- й двоичной цифры числа π ) без вычисления предыдущих цифр. При этом не вычисляется n- я десятичная цифра числа π (т. е. по основанию 10). Но другая формула, открытая Плуффом в 2022 году, позволяет извлечь n-ю цифру числа π в десятичном формате. Алгоритмы, основанные на BBP и BBP, использовались в таких проектах, как PiHex. для вычисления многих цифр числа π с использованием распределенных вычислений. Существование этой формулы стало неожиданностью. Широко распространено мнение, что вычислить n-ю цифру числа π так же сложно, как вычислить первые n цифр.

С момента своего открытия формулы общего вида:

$\alpha =\sum _{k=0}^{\infty }\left[{\frac {1}{b^{k}}}{\frac {p(k)}{q(k)}}\right]$

были открыты для многих других иррациональных чисел $\alpha$, где $p(k)$ и $q(k)$ являются полиномами с целыми коэффициентами и $b\geq 2$ является целочисленной базой . Формулы такого вида известны как формулы типа BBP . Учитывая число $\alpha$, не существует известного систематического алгоритма поиска подходящего $p(k)$, $q(k)$, и $b$; такие формулы обнаруживаются экспериментально .

Специализации

Специализация общей формулы, которая дала множество результатов:

$P(s,b,m,A)=\sum _{k=0}^{\infty }\left[{\frac {1}{b^{k}}}\sum _{j=1}^{m}{\frac {a_{j}}{(mk+j)^{s}}}\right],$

где s , b и m — целые числа, а $A=(a_{1},a_{2},\dots ,a_{m})$ представляет собой последовательность целых чисел. Функция P приводит к компактному обозначению некоторых решений. Например, исходная формула BBP:

$\pi =\sum _{k=0}^{\infty }\left[{\frac {1}{16^{k}}}\left({\frac {4}{8k+1}}-{\frac {2}{8k+4}}-{\frac {1}{8k+5}}-{\frac {1}{8k+6}}\right)\right]$

можно записать как:

$\pi =P{\bigl (}1,16,8,(4,0,0,-2,-1,-1,0,0){\bigr )}.$

Ранее известные формулы типа BBP

Вот некоторые из простейших формул этого типа, которые были хорошо известны до BBP и для которых функция P приводит к компактным обозначениям:

${\begin{aligned}\ln {\frac {10}{9}}&={\frac {1}{10}}+{\frac {1}{200}}+{\frac {1}{3\ 000}}+{\frac {1}{40\,000}}+{\frac {1}{500\,000}}+\cdots \\&=\sum _{k=1}^{\infty }{\frac {1}{10^{k}\cdot k}}={\frac {1}{10}}\sum _{k=0}^{\infty }\left[{\frac {1}{10^{k}}}\left({\frac {1}{k+1}}\right)\right]\\&={\frac {1}{10}}P{\bigl (}1,10,1,(1){\bigr )},\end{aligned}}$

${\begin{aligned}\ln 2&={\frac {1}{2}}+{\frac {1}{2\cdot 2^{2}}}+{\frac {1}{3\cdot 2^{3}}}+{\frac {1}{4\cdot 2^{4}}}+{\frac {1}{5\cdot 2^{5}}}+\cdots \\&=\sum _{k=1}^{\infty }{\frac {1}{2^{k}\cdot k}}={\frac {1}{2}}\sum _{k=0}^{\infty }\left[{\frac {1}{2^{k}}}\left({\frac {1}{k+1}}\right)\right]\\&={\frac {1}{2}}P{\bigl (}1,2,1,(1){\bigr )}.\end{aligned}}$

(Фактически это тождество справедливо и для a > 1:

$\ln {\frac {a}{a-1}}=\sum _{k=1}^{\infty }{\frac {1}{a^{k}\cdot k}}$.)

Плуфф также был вдохновлен степенным рядом арктанга в форме ( обозначение P также можно обобщить на случай, когда b не является целым числом):

${\begin{aligned}\arctan {\frac {1}{b}}&={\frac {1}{b}}-{\frac {1}{b^{3}3}}+{\frac {1}{b^{5}5}}-{\frac {1}{b^{7}7}}+{\frac {1}{b^{9}9}}+\cdots \\&=\sum _{k=1}^{\infty }\left[{\frac {1}{b^{k}}}{\frac {\sin {\frac {k\pi }{2}}}{k}}\right]={\frac {1}{b}}\sum _{k=0}^{\infty }\left[{\frac {1}{b^{4k}}}\left({\frac {1}{4k+1}}+{\frac {-b^{-2}}{4k+3}}\right)\right]\\&={\frac {1}{b}}P\left(1,b^{4},4,\left(1,0,-b^{-2},0\right)\right).\end{aligned}}$

Поиск новых равенств

Используя упомянутую выше функцию P , самая простая известная формула для π — это для s = 1, но m > 1. Многие открытые сейчас формулы известны для b как показателя степени 2 или 3 и m как показателя степени 2 или некоторых других. другое значение, богатое факторами, но в котором некоторые члены последовательности A равны нулю. Открытие этих формул предполагает компьютерный поиск таких линейных комбинаций после вычисления отдельных сумм. Процедура поиска состоит из выбора диапазона значений параметров для s , b и m , оценки сумм до многих цифр, а затем использования алгоритма поиска целочисленных отношений (обычно Хеламана Фергюсона ) алгоритм PSLQ для поиска последовательности A это складывает эти промежуточные суммы до известной константы или, возможно, до нуля.

Формула BBP для π

Оригинальная формула суммирования BBP π была найдена в 1995 году Плуффом с использованием PSLQ . Это также можно представить с помощью функции P :

${\begin{aligned}\pi &=\sum _{k=0}^{\infty }\left[{\frac {1}{16^{k}}}\left({\frac {4}{8k+1}}-{\frac {2}{8k+4}}-{\frac {1}{8k+5}}-{\frac {1}{8k+6}}\right)\right]\\&=P{\bigl (}1,16,8,(4,0,0,-2,-1,-1,0,0){\bigr )},\end{aligned}}$

что также сводится к этому эквивалентному отношению двух многочленов:

$\pi =\sum _{k=0}^{\infty }\left[{\frac {1}{16^{k}}}\left({\frac {120k^{2}+151k+47}{512k^{4}+1024k^{3}+712k^{2}+194k+15}}\right)\right].$

С помощью довольно простого доказательства было показано, что эта формула равна π .

Алгоритм извлечения цифр BBP для π

Мы хотели бы определить формулу, которая возвращает ( $n+1$)-й (с $n\geq 0$) шестнадцатеричная цифра числа π . с использованием этой формулы требуется несколько манипуляций Для реализации алгоритма патрубка .

Сначала нам нужно переписать формулу так:

$\pi =4\sum _{k=0}^{\infty }{\frac {1}{\left(16^{k}\right)(8k+1)}}-2\sum _{k=0}^{\infty }{\frac {1}{\left(16^{k}\right)(8k+4)}}-\sum _{k=0}^{\infty }{\frac {1}{\left(16^{k}\right)(8k+5)}}-\sum _{k=0}^{\infty }{\frac {1}{\left(16^{k}\right)(8k+6)}}.$

Теперь, для определенного значения n и взяв первую сумму, мы делим сумму на бесконечность по n -му члену:

$\sum _{k=0}^{\infty }{\frac {1}{\left(16^{k}\right)(8k+1)}}=\sum _{k=0}^{n}{\frac {1}{\left(16^{k}\right)(8k+1)}}+\sum _{k=n+1}^{\infty }{\frac {1}{\left(16^{k}\right)(8k+1)}}.$

Теперь умножаем на 16 ^н , так что шестнадцатеричная точка (разделитель между дробной и целой частями числа) смещается (или остается, если n = 0 ) слева от (n+1) -й дробной цифры:

$\sum _{k=0}^{\infty }{\frac {16^{n-k}}{8k+1}}=\sum _{k=0}^{n}{\frac {16^{n-k}}{8k+1}}+\sum _{k=n+1}^{\infty }{\frac {16^{n-k}}{8k+1}}.$

Поскольку нас интересует только дробная часть суммы, мы смотрим на наши два слагаемых и понимаем, что только первая сумма содержит члены с целой частью; и наоборот, вторая сумма не содержит членов с целой частью, поскольку числитель никогда не может быть больше знаменателя при k > n . Поэтому нам нужен трюк по удалению ненужных нам целых частей из членов первой суммы, чтобы ускорить и повысить точность вычислений. Этот трюк заключается в уменьшении по модулю 8 k + 1. Наша первая сумма (из четырех) для вычисления дробной части тогда будет выглядеть так:

$\sum _{k=0}^{n}{\frac {16^{n-k}{\bmod {(}}8k+1)}{8k+1}}+\sum _{k=n+1}^{\infty }{\frac {16^{n-k}}{8k+1}}.$

Обратите внимание, что оператор модуля всегда гарантирует, что будут сохранены только дробные части членов первой суммы. Чтобы вычислить 16 ^{п - к} mod (8k + 1) быстро и эффективно, алгоритм модульного возведения в степень выполняется на том же уровне цикла, а не вложенном . Когда его промежуточное произведение 16 x становится больше единицы, берется модуль, как и для промежуточной суммы в каждой сумме.

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

$4\Sigma _{1}-2\Sigma _{2}-\Sigma _{3}-\Sigma _{4}.$

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

Этот процесс аналогичен выполнению длинного умножения , но требует только суммирования некоторых средних столбцов. Хотя некоторые переносы не учитываются, компьютеры обычно выполняют арифметические операции для многих бит (32 или 64) и округляют, и нас интересуют только наиболее значащие цифры. Существует вероятность того, что конкретное вычисление будет похоже на неспособность прибавить небольшое число (например, 1) к числу 9999999999999999, и что ошибка распространится на самую старшую цифру.

BBP по сравнению с другими методами вычисления π

Этот алгоритм вычисляет π, не требуя специальных типов данных, состоящих из тысяч или даже миллионов цифр. Метод вычисляет n-ю цифру без вычисления первых n - 1 цифр и может использовать небольшие и эффективные типы данных. Фабрис Беллар нашел вариант BBP, формулу Беллара , который работает быстрее.

Хотя формула BBP может напрямую вычислить значение любой заданной цифры числа π с меньшими вычислительными затратами, чем формулы, которые должны вычислять все промежуточные цифры, BBP остается линейным ( $O(n\log n)$), при этом последовательное увеличение значений n требует все больше времени для расчета; то есть, чем «дальше» находится цифра, тем больше времени требуется BBP для ее вычисления, как и в стандартных алгоритмах π -вычислений.

Обобщения

DJ Broadhurst предлагает обобщение алгоритма BBP, которое можно использовать для вычисления ряда других констант почти в линейном времени и логарифмическом пространстве. Явные результаты даны для константы Каталана , $\pi ^{3}$, $\pi ^{4}$, постоянная Апери $\zeta (3)$, $\zeta (5)$, (где $\zeta (x)$ – дзета-функция Римана ), $\log ^{3}2$, $\log ^{4}2$, $\log ^{5}2$и различные продукты полномочий $\pi$ и $\log 2$. Эти результаты получены в первую очередь за счет использования полилогарифмических лестниц .

См. также

• Приближения π
• Экспериментальная математика
• Формула Белларда

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

• DJ Broadhurst, «Полилогарифмические лестницы, гипергеометрические ряды и десятимиллионные цифры ζ(3) и ζ(5)» , (1998) arXiv math.CA/9803067

Внешние ссылки

• Ричард Дж. Липтон , « Создание алгоритма — алгоритм — BBP », запись в блоге, 14 июля 2010 г.
• Ричард Дж. Липтон , « Класс Кука содержит число Пи », сообщение в блоге, 15 марта 2009 г.
• Бейли, Дэвид Х. «Сборник формул типа BBP для математических констант, обновлено 15 августа 2017 г.» (PDF) . Проверено 31 марта 2019 г.
• Дэвид Х. Бэйли , « Справочник кодов BBP », веб-страница со ссылками на код Бейли, реализующий алгоритм BBP, 8 сентября 2006 г.