Аннотация. Рассматривается ускорение вычисления произвольных шестнадцатеричных цифр числа π с использованием формулы Белларда. Предлагается вычислительная модификация, в которой семь дробей с линейными знаменателями объединяются в одну рациональную функцию с общим знаменателем. Это позволяет заменить несколько модульных возведений в степень на одно для каждого члена ряда. Описаны математическая основа преобразования, алгоритм извлечения цифр, особенности целочисленной арифметики и процедура проверки результатов. Приведены результаты сравнительных измерений двух реализаций на Python 3.12.6. В проведённом эксперименте ускоренная реализация показала преимущество от 1,93 до 2,72 раза на исследованных позициях. Также исследуется применимость метода группировки дробей к формуле Смита, представляющей собой альтернативную формулу извлечения шестнадцатеричных цифр числа π.

1. Введение

Вычисление цифр трансцендентных чисел традиционно связывается с последовательным вычислением их приближений. Однако формулы специального вида позволяют находить отдельные цифры без предварительного вычисления всех предшествующих цифр. Одним из известных результатов в этой области является формула Bailey - Borwein - Plouffe, опубликованная в 1997 году [1].

В том же году Фабрис Беллар предложил формулу для числа π, которая при использовании соответствующего алгоритма извлечения двоичных цифр позволяла получить приблизительно на 43 % большую скорость по сравнению с ранее известной формулой BBP [2]. Формула Белларда содержит семь дробей с линейными знаменателями. При прямой реализации вычисление дробных частей отдельных слагаемых требует многократного применения модульного возведения в степень.

Цель настоящей работы - разработать и экспериментально проверить способ ускорения вычисления цифр по формуле Белларда посредством объединения дробей с общим знаменателем. Основная идея состоит в том, чтобы сохранить математическое выражение ряда, но изменить способ вычисления его отдельных членов.

2. Постановка задачи

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

В работе сравниваются две реализации:

• стандартная реализация формулы Белларда, в которой дробные слагаемые обрабатываются отдельно;
• сгруппированная реализация, в которой дроби объединяются посредством общего знаменателя.

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

3. Формула Белларда

Используемая формула имеет вид [2]:

Для извлечения цифр используется масштабирование ряда на степень числа 16. Поскольку 16ⁿ⁻¹ = 2⁴⁽ⁿ⁻¹⁾, вычисление цифр, начиная с позиции n, сводится к нахождению дробной части соответствующего масштабированного выражения. После получения дробной части её умножают на 16^q, где q - число извлекаемых шестнадцатеричных цифр, и выделяют целую часть результата.

Вклад каждого члена ряда содержит показатель степени

При неотрицательном e вычисление дробной части степени двойки относительно целого знаменателя d использует остаток 2^e mod d. Для отрицательных показателей применяются операции фиксированной точки, поскольку соответствующая степень двойки является дробной.

4. Группировка дробей

Введём общий знаменатель, равный произведению семи линейных множителей:

Тогда выражение в скобках формулы (1) можно записать в виде P(k)/D(k), где

Каждое отношение D(k)/(ak+b) в формуле (4) является целым многочленом, поскольку соответствующий линейный множитель входит в произведение D(k). Следовательно, P(k) также является целочисленным многочленом.

После преобразования формула (1) принимает вид

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

5. Сокращение числа модульных возведений в степень

В стандартной реализации при вычислении каждого k обрабатываются семь знаменателей. Для положительного показателя степени это приводит к нескольким операциям вычисления остатков степеней двойки по разным модулям.

В сгруппированном варианте используется единый знаменатель D(k). Для e(n,k) ≥ 0 вычисляется один остаток

После этого вклад сгруппированного выражения определяется числителем P(k), остатком R(n,k) и знаменателем D(k). Дробная часть вычисляется с учётом знака и чередования знаков ряда. Для этого достаточно одного модульного возведения в степень на рассматриваемый член ряда вместо семи отдельных возведений.

Полиномиальные выражения P(k) и D(k) могут вычисляться по схеме Горнера. Такой способ уменьшает количество промежуточных операций по сравнению с повторным вычислением каждого произведения линейных множителей.

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

6. Реализация и контроль точности

Экспериментальные реализации написаны на Python 3.12.6 с использованием стандартных целочисленных операций языка. Сторонние библиотеки вычислений произвольной точности и внешние программные модули не применялись.

В обоих вариантах использованы следующие параметры:

• точность фиксированной точки - 192 двоичных разряда;
• длина хвоста ряда - 192 двоичных разряда;
• число повторов измерения для каждого теста - 5;
• сравниваемые алгоритмы - стандартная формула Белларда и сгруппированная формула Белларда.

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

Корректность результатов проверялась по известным шестнадцатеричным цифрам числа π. Для первых 18 цифр использовалась последовательность

Дополнительно проверялся результат на позиции 1 000 001. Контрольная последовательность из 24 цифр - 6C65E52CB459350050E4BB1. Обе реализации вернули одинаковые значения, совпадающие с указанными контрольными последовательностями.

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

Исходный код реализаций и скрипт сравнительных измерений доступны в репозитории GitHub.

Скрипт сравнительных измерений: benchmark.py.

Для запуска требуется Python 3. Выполнение команды python benchmark.py в каталоге с файлами запускает сравнительные измерения реализаций.

7. Результаты сравнительных измерений

Измерения проводились на одной системе с использованием Python 3.12.6. Для каждой позиции цифры выполнялось пять измерений; в таблице приведены медианные значения времени. Сравнивались стандартная и сгруппированная реализации формулы Белларда, а также сгруппированные реализации формул Белларда и Смита. Время указано в секундах.

Ускорение Белларда вычислялось как отношение времени стандартной реализации к времени сгруппированной реализации. Например, для позиции 1 000 оно составляет приблизительно 0,001673 / 0,000655 = 2,55 раза. В последнем столбце приведено отношение времени сгруппированной реализации формулы Белларда ко времени сгруппированной реализации формулы Смита.

На всех четырёх проверенных позициях сгруппированная реализация формулы Белларда работала быстрее стандартной. Ускорение составило около 2,72 раза на позиции 100, 2,55 раза на позиции 1 000, 2,06 раза на позиции 10 000 и 1,93 раза на позиции 100 000. Таким образом, группировка дробных слагаемых позволила сократить время вычисления во всех проведённых измерениях.

Применение группировки к формуле Смита. Дополнительно исследовалась возможность применения аналогичного метода к формуле Смита, представляющей собой альтернативную формулу извлечения шестнадцатеричных цифр числа π. В сгруппированной реализации дробные слагаемые объединяются с использованием общего знаменателя, что позволяет сократить количество модульных возведений в степень. Описание формулы приведено в источнике [3].

Сравнение двух сгруппированных реализаций показало, что в проведённых измерениях реализация формулы Смита работала быстрее сгруппированной реализации формулы Белларда на всех проверенных позициях. Ускорение составило около 1,06 раза на позиции 100, 1,09 раза на позиции 1 000, 1,08 раза на позиции 10 000 и 1,10 раза на позиции 100 000.

Корректность реализаций проверялась по первым 18 шестнадцатеричным цифрам π: стандартная формула Белларда, обе сгруппированные реализации и прямая реализация BBP выдали последовательность 243F6A8885A308D313. Дополнительно стандартная и сгруппированные реализации формул Белларда и Смита прошли проверку контрольной последовательности на позиции 1 000 001: 6C65E52CB459350050E4BB1.

Измерения проводились в Python 3.12.6 при точности 192 бита и отсечении хвоста на уровне 192 бит. Для каждой реализации использовалась медиана пяти измерений. Полученные значения характеризуют конкретные программные реализации и условия тестирования. На абсолютное время влияют процессор, версия интерпретатора, фоновая нагрузка и стоимость арифметических операций над целыми числами. Результаты показывают, что группировка дробных слагаемых ускоряет вычисления как для формулы Белларда, так и для формулы Смита; в данном эксперименте сгруппированная формула Смита показала наименьшее время выполнения на всех четырёх позициях.

8. Вычислительная сложность

Количество итераций по индексу k определяется позицией извлекаемой цифры и выбранной длиной хвоста. При извлечении цифр на позиции n число членов, для которых показатель e(n,k) неотрицателен, имеет порядок O(n). После достижения отрицательных показателей дополнительно учитывается ограниченный хвост ряда, задаваемый точностью реализации. То есть предложенная группировка не изменяет асимптотический порядок числа итераций по сравнению со стандартным алгоритмом Белларда. Её преимущество состоит в сокращении количества модульных возведений в степень внутри каждой итерации. Вместо нескольких операций с линейными знаменателями применяется одна операция с произведением этих знаменателей.

При оценке полной вычислительной сложности следует учитывать размер целых чисел, участвующих в модульном возведении в степень. Общий знаменатель D(k) растёт как многочлен седьмой степени по k, что увеличивает размер модуля. Поэтому преимущество метода следует рассматривать как результат оптимизации конкретной вычислительной схемы, а не как изменение асимптотической сложности задачи.

9. Заключение

В работе рассмотрен способ ускорения извлечения шестнадцатеричных цифр числа π по формуле Белларда посредством объединения семи дробей с линейными знаменателями в одну рациональную функцию.

Основной результат состоит в том, что алгебраическое объединение дробей позволяет сократить количество модульных возведений в степень с семи до одного на соответствующий член ряда. Для реализации на Python 3.12.6 экспериментально получено ускорение от 1,75 до 2,03 раза на позициях 100, 1 000 и 10 000 при выбранных параметрах точности.

Обе реализации совпали с контрольными шестнадцатеричными последовательностями на первых 18 цифрах и на позиции 1 000 001. Эти результаты подтверждают корректность вычислений в проверенных случаях. Дальнейшее развитие метода может включать исследование оптимального представления общего знаменателя, сокращение затрат на вычисление полиномов и формальное получение границы ошибки при конечной точности.

Список использованных источников

1. Bailey D. H., Borwein P. B., Plouffe S. On the Rapid Computation of Various Polylogarithmic Constants // Mathematics of Computation. - 1997. - Vol. 66, no. 218. - P. 903-913. - DOI: 10.1090/S0025-5718-97-00856-9.

2. Bellard F. A New Formula to Compute the n'th Binary Digit of π [Электронный ресурс]. - 20 January 1997. - URL: https://www.bellard.org/pi/pi_bin/pi_bin.html (дата обращения: 13.10.2026).

3. Smith R. Beating Bellard's Formula [Электронный ресурс]. - 4 March 2026. - URL: https://www.stylewarning.com/posts/beating-bellard/ (дата обращения: 13.10.2026).