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

π =

∞ ∑ k=0

1 16k

(

4 8k+1 − 2 8k+4 − 1 8k+5 − 1 8k+6

)

Особенность этой формулы состоит в том, что степень 16^-k позволяет вычислять шестнадцатеричные цифры π независимо от уже вычисленных. Поэтому вместо обычного последовательного вычисления всего числа можно сразу обратиться к нужной позиции.

Идея поиска других BBP-подобных формул заключается в том, чтобы рассматривать не одну известную формулу, а целое семейство рядов и искать среди них такие комбинации, которые в точности дают π и сохраняют возможность извлечения отдельных цифр.

В рассматриваемом поиске используется x = ±2^-m. Параметр a определяет шаг в знаменателях, j выбирает конкретный ряд, а m определяет степень двойки в основании.

Задача состоит в поиске рациональной линейной зависимости между π и несколькими такими суммами:

Если коэффициент при π отличен от нуля, получаем формулу непосредственно для π:

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

Почему именно такие ряды подходят для этой задачи? Рассмотрим один из них:

Если умножить его на 2ⁿ, получится

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

Именно это свойство является основой BBP-подобного извлечения цифр. Положение требуемой цифры меняет множитель 2ⁿ, но не заставляет вычислять число π от начала до этой позиции.

Одной только точной формулы недостаточно. Среди множества возможных представлений интерес представляют прежде всего те, в которых используется небольшое количество рядов S_j.

Для сравнения вводится величина

где N - количество использованных рядов S_j, а m - показатель степени двойки. В качестве ориентиров используются значения R = 1,0 для BBP и R = 0,7 для формулы Белларда.

Поэтому формула с R меньше 0,7 была бы кандидатом на улучшение по этому конкретному критерию. Значение R = 0,7 означает тот же уровень эффективности, что и выбранный ориентир Белларда.

В результате поиска получено, в частности, следующее представление с параметрами a = 40, m = 10 и отрицательным знаком:

π =

∞ ∑ k=0

( −

1 210

)k

[

16 40k+4 − 5 40k+10 − 4 40k+12 − 1 4(40k+20) − 1 4(40k+28) − 5 32(40k+30) + 1 16(40k+36)

].

В этой формуле используется семь рядов S_j. Следовательно,

То есть по выбранному нами критерию эта формула достигает уровня Белларда, но не превосходит его.

Для проверки метода рассматриваются также несколько известных или контрольных случаев. При a = 8, m = 4 и положительном знаке получается структура классической BBP-формулы. Для нее количество используемых рядов и значение m дают

Другой контрольный случай имеет параметры a = 20, m = 10 и отрицательный знак. Для него используется семь слагаемых, поэтому

Наконец, при a = 4, m = 2 и отрицательном знаке получается вариант с

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

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

где y выбирается так, чтобы выполнялось y^a = ±2^-m, а ζ является корнем единицы.

После такого преобразования вопрос о существовании формулы превращается в вопрос о рациональной линейной зависимости между π и соответствующими углами. Если π не принадлежит нужному рациональному линейному пространству, данный набор параметров не может привести к искомой формуле.

Для поиска таких зависимостей удобно использовать алгоритм PSLQ. Он позволяет по численным значениям величин находить возможные целочисленные линейные отношения между ними. Найденная зависимость после этого проверяется с повышенной точностью, чтобы отличить настоящее тождество от случайного численного совпадения.

Полученное соотношение сначала проверяется непосредственно как математическое тождество. Если

то абсолютное значение левой части должно оставаться пренебрежимо малым при увеличении рабочей точности.

После этого формула проверяется уже своим основным свойством - извлечением двоичных цифр π. Проверяются позиции 0, 1, 7, 100, 1000, 2718 и 12345. Таким образом, кандидат должен не просто численно воспроизводить π, но и работать как формула BBP-подобного типа.

Вся задача может быть сведена к следующей схеме. Сначала выбирается семейство

Затем для различных a, m и знака ищется рациональная линейная зависимость с π. Неподходящие пространства отбрасываются, найденная зависимость проверяется с высокой точностью, после чего проверяется возможность извлечения цифр.

Главный интерес представляют случаи, в которых число используемых слагаемых N мало по сравнению с m. Поэтому поиск формулы с R < 0,7 был бы уже не просто еще одним представлением π, а кандидатом на улучшение по принятому критерию эффективности.