为什么使用Chudnovsky公式而不是Brent–Salamin algorithm来计算圆周率？

nyy

为什么使用Chudnovsky公式而不是Brent–Salamin algorithm来计算圆周率？
或者说Chudnovsky公式比Brent–Salamin algorithm好在什么地方？

nyy

https://stackoverflow.com/questi ... n-of-pi-is-accurate  我怀疑呀

nyy

Computation of 2700 billion decimal digits of Pi using a
Desktop Computer
Fabrice Bellard
Feb 11, 2010 (4th revision)

https://bellard.org/pi/pi2700e9/pipcrecord.pdf

这个PDF文件能回答这个疑问：
It was evaluated with the binary splitting algorithm. The asymptotic running
time is O(M(n) log(n)2) for a n limb result. It is worst than the asymptotic
running time of the Arithmetic-Geometric Mean algorithms of O(M(n) log(n))
but it has better locality and many improvements can reduce its constant factor.

nyy

but which of these algorithms is faster in practice for "small enough" n {\displaystyle n} n depends on technological factors such as memory sizes and access times.[68] For breaking world records, the iterative algorithms are used less commonly than the Chudnovsky algorithm since they are memory-intensive.

https://en.wikipedia.org/wiki/Approximations_of_%CF%80

nyy

We consider some of Jonathan and Peter Borweins' contributions to the high-precision computation of π and the elementary functions, with particular reference to their book "Pi and the AGM" (Wiley, 1987). Here "AGM" is the arithmetic-geometric mean of Gauss and Legendre. Because the AGM converges quadratically, it can be combined with fast multiplication algorithms to give fast algorithms for the n-bit computation of π, and more generally the elementary functions. These algorithms run in almost linear time O(M(n)logn), where M(n) is the time for n-bit multiplication. We outline some of the results and algorithms given in Pi and the AGM, and present some related (but new) results. In particular, we improve the published error bounds for some quadratically and quartically convergent algorithms for π, such as the Gauss-Legendre algorithm. We show that an iteration of the Borwein-Borwein quartic algorithm for π is equivalent to two iterations of the Gauss-Legendre quadratic algorithm for π, in the sense that they produce exactly the same sequence of approximations to π if performed using exact arithmetic.

https://arxiv.org/abs/1802.07558

The Borwein brothers, Pi and the AGM

nyy

A DETAILED PROOF OF THE CHUDNOVSKY FORMULA
WITH MEANS OF BASIC COMPLEX ANALYSIS
EIN AUSFUHRLICHER BEWEIS DER CHUDNOVSKY-FORMEL ¨
MIT ELEMENTARER FUNKTIONENTHEORIE
LORENZ MILLA, 03/2021

https://arxiv.org/pdf/1809.00533.pdf



从这张图上可以看出，圆周率的记录都是Chudnovsky公式创造的

nyy

刨根问题，总是能让人更接近真相！

nyy

The algorithm I used (Chudnovsky series evaluated using the binary splitting algorithm) is asymptotically slower than the Arithmetic-Geometric Mean algorithm used by Daisuke Takahashi, but it makes a more efficient use of the various CPU caches, so in practice it can be faster. Moreover, some mathematical tricks were used to speed up the binary splitting.

https://bellard.org/pi/pi2700e9/faq.html

nyy

\[\frac{640320^{3/2}}{12\pi}=\frac{426880\sqrt{10005}}{\pi}=\sum^\infty_{k=0}\frac{(6k)!(545140134k+13591409)}{(3k)!(k!)^3\left(-640320\right)^{3k}}\]

把Chudnovsky公式弄上来！


拉马努金公式

\[\frac{1}{\pi}=\frac{2\sqrt{2}}{99^2}\sum^\infty_{k=0}\frac{(4k)!}{(k!)^4}\frac{(26390k+1103)}{396^{4k}}\]

nyy

One algorithm which has the potential to beat Chudnovsky is the Arithmetic Geometric Mean algorithm which doubles the number of decimal places each iteration. It involves square roots and full precision divisions which makes it tricky to implement well. In theory it should be faster than Chudnovsk but, so far, in practice Chudnovsky is faster.

https://www.craig-wood.com/nick/articles/pi-chudnovsky/


\[\begin{align}
\frac{1}{\pi} &= 12 \sum^\infty_{k=0} \frac{(-1)^k (6k)! (13591409 + 545140134k)}{(3k)!(k!)^3 640320^{3k + 3/2}} \\
&= \frac{12}{640320 \sqrt{640320}} \sum^\infty_{k=0} \frac{(-1)^k (6k)! (13591409 + 545140134k)}{(3k)!(k!)^3 640320^{3k}} \\
&= \frac{1}{426880 \sqrt{10005}} \sum^\infty_{k=0} \frac{(-1)^k (6k)! (13591409 + 545140134k)}{(3k)!(k!)^3 640320^{3k}} \\
\end{align}\]

\[\begin{align}
a     &= \sum^\infty_{k=0} \frac{(-1)^k (6k)!}{(3k)!(k!)^3 640320^{3k}} \\
      &= 1
          - \frac{6\cdot5\cdot4}{(1)^3 640320^3}
          + \frac{12\cdot11\cdot10\cdot9\cdot8\cdot7}{(2\cdot1)^3 640320^6}
          - \frac{18\cdot17\cdots13}{(3\cdot2\cdot1)^3 640320^{9}}
          + \cdots \\
b     &= \sum^\infty_{k=0} \frac{(-1)^k (6k)!k}{(3k)!(k!)^3 640320^{3k}} \\
\frac{1}{\pi} &= \frac{13591409a + 545140134b}{426880 \sqrt{10005}} \\
\pi           &= \frac{426880 \sqrt{10005}}{13591409a + 545140134b}
\end{align}\]

\[\begin{align}
a_k &= \frac{(-1)^k (6k)!}{(3k)!(k!)^3 640320^{3k}} \\
b_k &= k \cdot a_k \\
\frac{a_{k}}{a_{k-1}} &= - \frac{(6k-5)(6k-4)(6k-3)(6k-2)(6k-1)6k}{3k(3k-1)(3k-2)k^3 640320^3} \\
&= - \frac{24(6k-5)(2k-1)(6k-1)}{k^3 640320^3} \\
\end{align}\]

公式能直接复制过来，真爽！