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

nyy

目前求 π 的算法中哪种收敛最快？ - 得特呢勒的回答 - 知乎
https://www.zhihu.com/question/312520105/answer/795705835

高斯-勒让德算法是一种用于计算π的算法。它的收敛速度是显著的，只需25次迭代即可产生π的4500万位正确数字。不过，内存密集是它的缺点，因此有时它不如梅钦类公式使用广泛。

内存密集是什么意思？

nyy

nyy 发表于 2023-9-11 10:21
目前求 π 的算法中哪种收敛最快？ - 得特呢勒的回答 - 知乎
https://www.zhihu.com/question/312520105/an ...

内存密集是什么意思？

这个有谁知道的？

nyy

nyy 发表于 2023-10-11 09:15
内存密集是什么意思？

这个有谁知道的？

存储密集型（I/O密集型）是指一种需要大量读写存储设备的操作，比如说文件拷贝、数据库查询、网络传输等。这种操作通常需要反复读写存储设备，因为这些操作涉及到大量的数据传输。在进行这些任务时，需要高效地利用存储设备和网络带宽，以便更快地完成任务。此外，在处理大量数据时还需要考虑数据压缩和优化传输协议的选择，以便最大程度地减少数据传输的时间。

也许是这个意思

Ickiverar

内存密集的意思是，考虑在内存大小为 N 的数据上进行 k=log_2(N) 次遍历计算的算法，复杂度显然是 Nk，或者 N lnN。
算法1：从头遍历到尾，遍历 k 次；
算法2：将数据分为两半，首先处理前一半 k-1 次，再处理后一半 k-1 次，再整体处理 1 次。处理过程同样使用该算法递归。
两个算法都将数据处理了 k 次，复杂度是一样的，都是 Nk，但算法2有更好的内存局部性（cache locality），而算法1是内存密集的，所以算法2会更快。

nyy

现在证明了 Chudnovsky 公式中的级数可以用 binary splitting 算法求得。我们整理一下公式

https://article.itxueyuan.com/2daK95

也许这个是答案，虽然我没理解

nyy

我用最直白、不绕弯的话跟你说：

内存密集 = 特别吃内存、特别占空间。

 

「内存密集」到底啥意思？

你可以把内存当成临时工作台：

- CPU = 干活的手
- 内存 = 你面前的桌子
- 硬盘 = 仓库

内存密集型算法 / 程序：
算的时候，要把大量数据同时放在桌子上，不能只算一点丢一点。

 

放到「高斯-勒让德算圆周率」里：

它是迭代算法，特点是：

- 每次迭代，精度翻倍（速度极快）
- 但每一步都要保存上一步的全部高精度数字

你算到 1亿位 π：

- 这些数字要全部存在内存里
- 不能边算边丢
→ 这就叫 内存密集。

 

对比一下就懂

- 丘德诺夫斯基：逐项累加，不用存整个大数 → 不怎么吃内存
- 高斯-勒让德：每次迭代都要完整高精度数 → 超级吃内存

 

人话总结

内存密集 = 计算快，但特别占内存，内存小就跑不动。

要不要我给你画个超简单对比图，一眼看懂两种算π算法的差别？

对，你这句话说到点子上了，而且非常关键。

我用最直白、最本质的话讲清楚：

1. 内存密集 ≠ 只是“占空间大”

更重要的是：
要频繁、大量地读写内存里的数据。

CPU 很快，但内存比 CPU 慢得多得多。
你越频繁去读/写内存，整体速度就越被拖慢。

2. 为什么算 π 时这很要命？

高斯-勒让德这种算法：

- 每一步都要完整的超大精度数字
- 每一步都要来回拷贝、读写这些大数

这些操作大部分时间不是在计算，
而是在：
从内存读 → 算一点点 → 写回内存

内存访问慢，就变成瓶颈。

3. 一句话总结

内存密集 = 数据太大、访问太频繁，
CPU 空等内存，速度上不去。

 

如果你愿意，我可以用超简单比喻帮你把：
CPU 快 / 内存慢 / 硬盘更慢
这三者的差距讲得特别直观。

nyy

高斯勒让德算法，不是比丘特罗夫斯基算法快吗？

你的直觉非常准，如果单看**收敛速度**（也就是“迭代一次能提高多少精度”），**高斯-勒让德算法确实比丘德诺夫斯基算法快**。它是二次收敛，而丘德诺夫斯基是对数级收敛。

但现实情况有点反直觉：在**实际的计算机**上计算圆周率，**丘德诺夫斯基算法比高斯-勒让德算法快得多**。目前的世界纪录（2024年算到105万亿位）都是用丘德诺夫斯基算法打破的。

之所以会这样，关键在于**收敛速度不等于计算速度**，主要有三个原因：

### 1. 计算复杂度：乘法比开方快得多
-   **高斯-勒让德**：每次迭代都需要做**开平方根**运算。在计算机里，高精度的开平方根是非常“重”的操作，需要执行多次乘法，而且必须一步一步来，很难并行计算。
-   **丘德诺夫斯基**：它是一个无穷级数，虽然项数多，但只用到了**乘法、加法、阶乘**。最关键的是，它可以用一种叫**“二元分裂法”**的技巧，把计算过程彻底并行化。虽然总的计算次数多，但单次计算快，还能让电脑的多个核心同时开工。

### 2. 存储空间的限制
-   **高斯-勒让德**：因为每次迭代都要依赖上一步的结果，必须把整个数字全程保存在内存里，对内存的占用很大。
-   **丘德诺夫斯基**：级数算法的每一项可以独立计算，算完就能“扔掉”一部分，对内存友好得多。算到万亿位时，内存就是最宝贵的资源。

### 3. 工程优化上的优势
丘德诺夫斯基算法在代码层面有成熟的模组化方案，比如 **y-cruncher**（就是那个破纪录的软件）对它做了极限优化。而高斯-勒让德因为流程固定，优化空间小。

**总结**：
-   **只看数学迭代次数**：高斯-勒让德快。
-   **实际电脑运行时间**：丘德诺夫斯基快得多，因为它的**操作更简单、更能并行、更省内存**。

如果你想了解“二元分裂法”具体是怎么加速级数求和的，我可以继续为你讲解。