Формула Бейли – Борвейна – Плуфа - Bailey–Borwein–Plouffe formula

В Формула Бейли – Борвейна – Плуфа (Формула BBP) является формулой для π. Он был открыт в 1995 г. Саймон Плафф и назван в честь авторов статьи, в которой он был опубликован, Дэвид Х. Бейли, Питер Борвейн, и Plouffe.^[1] До этого ее публиковал Плафф на своем собственном сайте.^[2] Формула

${\displaystyle \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 приводит к алгоритм патрубка для вычисления пth база-16 (шестнадцатеричная) цифра π (а значит, и пth двоичный символ из π) без вычисления предыдущих цифр. Это делает нет вычислить пth десятичная дробь π (т.е. по основанию 10). Такой результат для базы 10 неизвестен.^[3]

Существование этой формулы стало неожиданностью. Было широко распространено мнение, что вычисление п-я цифра π так же сложно, как вычислить первый п цифры.^[1]

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

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

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

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

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

${\displaystyle 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, б, и м целые числа, и ${\displaystyle A=(a_{1},a_{2},\dots ,a_{m})}$ это последовательность целых чисел. п функция приводит к компактным обозначениям для некоторых решений. Например, исходная формула BBP

${\displaystyle \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]}$

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

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

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

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

${\displaystyle {\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{\big (}1,10,1,(1){\big )},\end{aligned}}}$

${\displaystyle {\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{\big (}1,2,1,(1){\big )}.\end{aligned}}}$

(На самом деле это тождество верно при a> 1: ${\displaystyle \ln {\frac {a}{a-1}}=\sum _{k=1}^{\infty }{\frac {1}{a^{k}\cdot k}}}$)

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

${\displaystyle {\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{\big (}1,b^{4},4,(1,0,-b^{-2},0){\big )}.\end{aligned}}}$

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

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

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

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

${\displaystyle {\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{\big (}1,16,8,(4,0,0,-2,-1,-1,0,0){\big )},\end{aligned}}}$

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

${\displaystyle \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].}$

Эта формула, как было показано довольно простым доказательством, равна π.^[5]

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

Мы хотели бы определить формулу, которая возвращает пth шестнадцатеричный цифра π. Требуется несколько манипуляций для реализации алгоритм патрубка используя эту формулу.

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

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

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

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

Теперь умножаем на 16^п, так что шестнадцатеричная точка (разделение между дробной и целой частями числа) находится в пместо:

${\displaystyle \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 > п. Следовательно, нам нужен трюк, чтобы убрать целые числа из первой суммы. Этот трюк - мод 8k + 1. Тогда наша сумма для первой дробной части станет

${\displaystyle \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^п−k мод (8k + 1) быстро и качественно, модульное возведение в степень используется алгоритм. Когда текущее произведение становится больше единицы, берется модуль, как и для промежуточной суммы в каждой сумме.

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

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

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

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

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

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

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

Обобщения

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

Смотрите также

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

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

1. Бейли, Дэвид Х .; Borwein, Питер Б .; Plouffe, Саймон (1997). «О быстром вычислении различных полилогарифмических констант». Математика вычислений. 66 (218): 903–913. Дои:10.1090 / S0025-5718-97-00856-9. МИСТЕР  1415794.
2. Сайт Plouffe.
3. Гурдон, Ксавье (12 февраля 2003 г.). «Вычисление N-й цифры» (PDF). Получено 4 ноября 2020.
4. Вайсштейн, Эрик В. «Формула BBP». MathWorld.
5. Бейли, Дэвид Х .; Borwein, Jonathan M .; Borwein, Питер Б .; Plouffe, Саймон (1997). «В поисках пи». Математический интеллигент. 19 (1): 50–57. Дои:10.1007 / BF03024340. МИСТЕР  1439159.
6. Бейли, Дэвид Х. (8 сентября 2006 г.). «Алгоритм BBP для Пи» (PDF). Получено 17 января 2013. Время выполнения алгоритма BBP ... увеличивается примерно линейно с положением d.
7. Д. Дж. Бродхерст, «Полилогарифмические лестницы, гипергеометрические ряды и десятимиллионные цифры ζ (3) и ζ (5)», (1998) arXiv math.CA/9803067

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

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

внешняя ссылка

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