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

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

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

Формула BBP дает начало алгоритму втулки для вычисления n-й base-16 (шестнадцатеричной) цифры числа π (и, следовательно, также n-й двоичной цифры числа π) без вычисления предыдущих цифр.

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

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

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

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

Содержание

• 1 Специализации
  • 1.1 Ранее известные формулы типа BBP
  • 1.2 Поиск новых равенств
  • 1.3 Формула BBP для π
    • 1.3. 1 Алгоритм выделения цифры BBP для π
• 2 BBP по сравнению с другими методами вычисления π
• 3 Обобщения
• 4 См. Также
• 5 Ссылки
• 6 Дополнительная литература
• 7 Внешние ссылки

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

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

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

где s, b и m - целые числа, и $A\; =\; (a\; 1,\; a\; 2,\dots ,\; am)\; \{\backslash \; displaystyle\; A\; =\; (a\_\; \{1\},\; a\_\; \{2\},\; \backslash \; dots,\; a\_\; \{m\})\}$- это последовательность целых чисел. Функция P приводит к компактным обозначениям для некоторых решений. Например, исходная формула BBP

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

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

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

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

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

$ln\; \; 10\; 9\; =\; 1\; 10\; +\; 1\; 200\; +\; 1\; 3\; 000\; +\; 1\; 40\; 000\; +\; 1\; 500\; 000\; +\; \cdots \; =\; \sum \; k\; =\; 1\; \infty \; 1\; 10\; k\; \cdot \; k\; =\; 1\; 10\; \sum \; k\; =\; 0\; \infty \; [1\; 10\; k\; (1\; k\; +\; 1)]\; =\; 1\; 10\; P\; (\; 1,\; 10,\; 1,\; (1)),\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; \backslash \; ln\; \{\backslash \; frac\; \{10\}\; \{9\}\}\; =\; \{\backslash \; frac\; \{1\}\; \{10\}\}\; +\; \{\backslash \; frac\; \{1\; \}\; \{200\}\}\; +\; \{\backslash \; frac\; \{1\}\; \{3\; \backslash \; 000\}\}\; +\; \{\backslash \; frac\; \{1\}\; \{40\; \backslash ,\; 000\}\}\; +\; \{\backslash \; frac\; \{1\}\; \{500\; \backslash ,\; 000\}\}\; +\; \backslash \; cdots\; \backslash \; \backslash \; =\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{\backslash \; infty\}\; \{\backslash \; frac\; \{1\}\; \{10\; ^\; \{k\}\; \backslash \; cdot\; k\}\}\; =\; \{\backslash \; frac\; \{1\}\; \{10\}\}\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{\backslash \; infty\}\; \backslash \; left\; [\{\backslash \; frac\; \{1\}\; \{10\; ^\; \{k\}\}\}\; \backslash \; left\; (\{\backslash \; frac\; \{1\}\; \{k\; +\; 1\}\}\; \backslash \; right)\; \backslash \; right]\; \backslash \backslash \; =\; \{\; \backslash \; frac\; \{1\}\; \{10\}\}\; P\; \{\backslash \; big\; (\}\; 1,10,1,\; (1)\; \{\backslash \; big)\},\; \backslash \; end\; \{align\}\}\}$

$ln\; \; 2\; =\; 1\; 2\; +\; 1\; 2\; \cdot \; 2\; 2\; +\; 1\; 3\; \cdot \; 2\; 3\; +\; 1\; 4\; \cdot \; 2\; 4\; +\; 1\; 5\; \cdot \; 2\; 5\; +\; \cdots \; =\; \sum \; k\; =\; 1\; \infty \; 1\; 2\; k\; \cdot \; k\; =\; 1\; 2\; \sum \; k\; =\; 0\; \infty \; [1\; 2\; k\; (1\; k\; +\; 1)]\; =\; 1\; 2\; P\; (1,\; 2,\; 1,\; (1)).\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; \backslash \; ln\; 2\; =\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; +\; \{\backslash \; frac\; \{1\}\; \{2\; \backslash \; cdot\; 2\; ^\; \{2\}\}\}\; +\; \{\backslash \; frac\; \{1\}\; \{3\; \backslash \; cdot\; 2\; ^\; \{3\}\}\}\; +\; \{\backslash \; frac\; \{1\}\; \{4\; \backslash \; cdot\; 2\; ^\; \{4\}\}\}\; +\; \{\backslash \; frac\; \{1\}\; \{5\; \backslash \; cdot\; 2\; ^\; \{5\}\}\}\; +\; \backslash \; cdots\; \backslash \backslash \; =\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{\backslash \; infty\}\; \{\backslash \; frac\; \{1\}\; \{2\; ^\; \{k\}\; \backslash \; cdot\; k\}\}\; =\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; \backslash \; sum\; \_\; \{k\; =\; 0\; \}\; ^\; \{\backslash \; infty\}\; \backslash \; left\; [\{\backslash \; frac\; \{1\}\; \{2\; ^\; \{k\}\}\}\; \backslash \; left\; (\{\backslash \; frac\; \{1\}\; \{k\; +\; 1\}\}\; \backslash \; right)\; \backslash \; right]\; \backslash \backslash \; =\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; P\; \{\backslash \; big\; (\}\; 1,2,1,\; (1)\; \{\backslash \; big)\}.\; \backslash \; end\; \{align\}\}\}$

(На самом деле, это тождество верно для>1: $пер\; \; аа\; -\; 1\; знак\; равно\; \sum \; К\; знак\; равно\; 1\; \infty \; 1\; ак\; \cdot \; К\; \{\backslash \; Displaystyle\; \backslash \; ln\; \{\backslash \; frac\; \{a\}\; \{a-1\}\}\; =\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{\backslash \; infty\; \}\; \{\backslash \; frac\; \{1\}\; \{a\; ^\; \{k\}\; \backslash \; cdot\; k\}\}\}$)

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

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

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

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

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

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

$\pi \; =\; \sum \; k\; =\; 0\; \infty \; [1\; 16\; k\; (4\; 8\; k\; +\; 1\; -\; 2\; 8\; k\; +\; 4\; -\; 1\; 8\; k\; +\; 5\; -\; 1\; 8\; k\; +\; 6)]\; Знак\; равно\; п\; (1,\; 16,\; 8,\; (4,\; 0,\; 0,\; -\; 2,\; -\; 1,\; -\; 1,\; 0,\; 0)),\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; \backslash \; pi\; =\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{\backslash \; infty\}\; \backslash \; left\; [\{\backslash \; frac\; \{1\}\; \{16\; ^\; \{k\}\}\}\; \backslash \; left\; (\{\backslash \; frac\; \{4\}\; \{8k\; +\; 1\}\}\; -\; \{\backslash \; frac\; \{2\}\; \{8k\; +\; 4\; \}\}\; -\; \{\backslash \; frac\; \{1\}\; \{8k\; +\; 5\}\}\; -\; \{\backslash \; frac\; \{1\}\; \{8k\; +\; 6\}\}\; \backslash \; right)\; \backslash \; right]\; \backslash \backslash \; =\; P\; \{\backslash \; big\; (\}\; 1,16,8,\; (4,0,0,\; -2,\; -1,\; -1,0,0)\; \{\backslash \; big)\},\; \backslash \; end\; \{align\}\}\}$

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

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

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

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

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

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

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

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

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

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

$\sum \; k\; =\; 0\; \infty \; 16\; N\; -\; К\; 8\; К\; +\; 1\; знак\; равно\; \sum \; К\; знак\; равно\; 0\; N\; 16\; N\; -\; К\; 8\; К\; +\; 1\; +\; \sum \; К\; знак\; равно\; N\; +\; 1\; \infty \; 16\; N\; -\; К\; 8\; К\; +\; 1.\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{\backslash \; infty\}\; \{\backslash \; frac\; \{16\; ^\; \{nk\}\}\; \{8k\; +\; 1\}\}\; =\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{n\}\; \{\backslash \; frac\; \{16\; ^\; \{nk\}\}\; \{8k\; +\; 1\}\}\; +\; \backslash \; sum\; \_\; \{k\; =\; n\; +\; 1\}\; ^\; \{\backslash \; infty\}\; \{\backslash \; frac\; \{16\; ^\; \{nk\}\}\; \{8k\; +\; 1\}\}.\}$

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

$\sum \; k\; =\; 0\; n\; 16\; n\; -\; k\; mod\; (8\; k\; +\; 1)\; 8\; k\; +\; 1\; +\; \sum \; k\; =\; n\; +\; 1\; \infty \; 16\; n.\; -\; к\; 8\; к\; +\; 1.\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{n\}\; \{\backslash \; frac\; \{16\; ^\; \{nk\}\; \{\backslash \; bmod\; \{(\}\}\; 8k\; +\; 1)\}\; \{8k\; +\; 1\}\}\; +\; \backslash \; sum\; \_\; \{k\; =\; n\; +1\}\; ^\; \{\backslash \; infty\}\; \{\backslash \; frac\; \{16\; ^\; \{nk\}\}\; \{8k\; +\; 1\}\}.\}$

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

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

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

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

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

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

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

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

Обобщения

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

См. Также

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

Ссылки

Дополнительная литература

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

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

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