账号 自动登录 找回密码 密码 欢迎注册
 搜索

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

### 马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

×

楼主| 发表于 2023-9-8 09:13:07 | 显示全部楼层
 本帖最后由 nyy 于 2023-9-8 09:15 编辑 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} 公式能直接复制过来，真爽！

### 点评

tricky是棘手的; 狡猾的; 难办的; 诡计多端的; 难对付的  发表于 2023-10-12 08:33

楼主| 发表于 2023-9-7 13:32:59 | 显示全部楼层
 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

楼主| 发表于 2023-9-7 13:04:36 | 显示全部楼层
 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.

楼主| 发表于 2023-9-6 09:33:40 | 显示全部楼层

楼主| 发表于 2023-9-7 13:28:18 | 显示全部楼层
 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

### 点评

such as memory sizes and access times，这些也是影响速度的重要因素！  发表于 2023-9-7 13:40

楼主| 发表于 2023-9-7 13:49:11 | 显示全部楼层
 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公式创造的

楼主| 发表于 2023-9-7 14:17:52 | 显示全部楼层
 刨根问题，总是能让人更接近真相！

楼主| 发表于 2023-9-8 08:35:55 | 显示全部楼层
 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

楼主| 发表于 2023-9-8 09:04:05 | 显示全部楼层
 本帖最后由 nyy 于 2023-9-8 09:06 编辑 $\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}}$

 您需要登录后才可以回帖 登录 | 欢迎注册 本版积分规则 回帖并转播 回帖后跳转到最后一页

GMT+8, 2023-12-8 18:12 , Processed in 0.081554 second(s), 23 queries .