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

Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Формула Бейли – Борвейна – Плуфа»  – Новости  · газеты  · книги  · ученый  · JSTOR (Март 2014 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

В Формула Бейли – Борвейна – Плуфа (Формула 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 альфа = сумма _ {к = 0} ^ { infty} left [{ гидроразрыва {1} {b ^ {k}}} { гидроразрыва {p (k)} {q (k) }}верно]}$

были открыты для многих других иррациональных чисел ${ displaystyle alpha}$, куда ${ displaystyle p (k)}$ и ${ Displaystyle д (к)}$ находятся многочлены с целыми коэффициентами и ${ 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 А = (а_ {1}, а_ {2}, точки, а_ {м})}$ это последовательность целых чисел. п функция приводит к компактным обозначениям для некоторых решений. Например, исходная формула 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 {align} 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 {align}}}$

${ displaystyle { begin {align} 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 {выравнивается}}}$

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

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

${ displaystyle { begin {align} 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 {выравнивается}}}$

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

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

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

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

${ displaystyle { begin {align} 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 {выравнивается} }}$

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

${ 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 ^ {nk}} {8k + 1}} = sum _ {k = 0} ^ {n} { frac {16 ^ {nk}} {8k + 1}} + sum _ {k = n + 1} ^ { infty} { frac {16 ^ {nk}} {8k + 1}}.}.}$

Поскольку нас интересует только дробная часть суммы, мы смотрим на наши два члена и понимаем, что только первая сумма может дать целые числа; и наоборот, вторая сумма не может давать целые числа, так как числитель никогда не может быть больше знаменателя для k > п. Следовательно, нам нужен трюк, чтобы убрать целые числа из первой суммы. Этот трюк - мод 8k + 1. Тогда наша сумма для первой дробной части станет

${ displaystyle sum _ {k = 0} ^ {n} { frac {16 ^ {nk} { bmod {(}} 8k + 1)} {8k + 1}} + sum _ {k = n +1} ^ { infty} { frac {16 ^ {nk}} {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 О (п журнал п)}$), при этом последовательно увеличивающиеся значения п требуется все больше времени для расчета; то есть, чем «дальше» находится цифра, тем больше времени требуется BBP для ее вычисления, как и в стандартном π-вычислительные алгоритмы.^[6]

Обобщения

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

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

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

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

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

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

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

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