Ниже — краткая формулировка и анализ основных подходов к приближению числа $\pi$: скорость сходимости, вычислительная стоимость и практичность.
1) Ряды на основе арктангенса (Machin‑типа)
- Формула: например $\frac{\pi }{4}=4\arctan \frac{1}{5}-\arctan \frac{1}{239}$.
- Базовый ряд: $\arctan x=\sum _{n=0}^{\infty }\frac{(-1{)}^n{x}^{2n+1}}{2n+1}$ при $|x|\le 1$.
- Сходимость: геометрическая с фактором примерно $x^2$ для каждого слагаемого; для малых $x$ — быстро, но всё же линейная (один дополнительный знак на постоянном числе членов).
- Плюсы: простота, устойчивость, хорошо для десятков–сотен знаков; низкая сложность реализации.
- Минусы: для больших n неэкономичен по сравнению с экспоненциально сходящимися рядами.
2) Ramanujan‑типы и Chudnovsky
- Примеры:
- Ramanujan: $\frac{1}{\pi }=\frac{2\sqrt{2}}{9801}\sum _{k=0}^{\infty }\frac{(4k)!(1103+26390k)}{(k!{)}^{4}396^{4k}}$.
- Chudnovsky: $\frac{1}{\pi }=12\sum _{k=0}^{\infty }\frac{(-1{)}^k(6k)!(13591409+545140134k)}{(3k)!(k!{)}^{3}640320^{3k+3/2}}$.
- Сходимость: экспоненциально быстрая — каждое слагаемое даёт десятки (вплоть до десятков) дополнительных десятичных знаков.
- Плюсы: чрезвычайно экономичны по числу членов; в комбинации с бинарным разбиением (binary splitting) и быстрым умножением дают наилучшее практическое соотношение затрат/точности для очень большой точности.
- Минусы: требуют больших факториалов и многоточечной арифметики; реализация сложнее, требуется аккуратность в многоточечных умножениях и делениях.
3) Алгоритмы на основе AGM / Gauss–Legendre (Brent–Salamin)
- Итерации (схематично): среднее арифм. и геом. строят последовательности, после k итераций погрешность примерно квадратно уменьшается.
- Свойство: квадратичная сходимость (число верных цифр примерно удваивается при каждом шаге).
- Вычислительная стоимость: несколько итераций, но каждая требует операций с очень длинными числами (умножения/деления); с быстрым умножением асимптотика очень хорошая.
- Плюсы: очень эффективен для гигантской точности; асимптотически лучший при использовании FFT‑умножения.
- Минусы: каждое итерационное обновление зависит от предыдущего — ограничения по параллельности; реализация требует высокой точности на промежуточных шагах.
4) BBP‑формула (digit‑extraction)
- Пример: получили формулы, позволяющие вычислять отдельные шестнадцатеричных цифр $\pi$ без вычисления всех предыдущих.
- Применение: полезно для извлечения отдельных цифр; не экономична, если нужна большая непрерывная последовательность первых $n$ цифр.
- Плюсы: уникальная возможность прямой выборки цифр.
- Минусы: не самый эффективный метод для вычисления полного набора первых $n$ цифр.
5) Геометрические методы: Архимедов метод многоугольников и Монте‑Карло
- Архимед: аппроксимация через вписанные/описанные $2^k$-угольники — сходимость линейная по числу удвоений сторон (очень медленно).
- Монте‑Карло: вероятность, погрешность $O(1/\sqrt{N})$ — крайне неэкономичен для точных цифр.
- Вывод: геометрические и статистические методы годятся для иллюстраций и образовательных целей, но не для эффективного вычисления многих цифр.
6) Критерии «экономичности» и практические замечания
- Мера: число дополнительных корректных десятичных цифр на одну «весомую» операцию (многозначное умножение/деление) или асимптотическая сложность для n знаков.
- Резюме:
- Для очень большой точности (миллионы+ цифр): Chudnovsky (с binary splitting) и AGM/Brent–Salamin с быстрым умножением — лучшие; при использовании FFT‑умножения асимптотика близка к $O(M(n)\log n)$, где $M(n)$ — стоимость умножения длины $n$.
- Для умеренной точности (несколько десятков–сотен знаков): Machin‑типа формулы просты и эффективны.
- Для извлечения отдельных цифр: BBP‑типа формулы.
- Избегать: Архимеда и Монте‑Карло, если нужна высокая точность.
Короткий практический совет: если нужна высокая точность — реализуйте Chudnovsky с бинарным разбиением и быстрым умножением или AGM с FFT‑умножением; для простоты и небольших точностей — Machin‑типа ряд.