找回密码
 欢迎注册
楼主: nyy

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

[复制链接]
 楼主| 发表于 2023-9-11 10:21:36 | 显示全部楼层
目前求 π 的算法中哪种收敛最快? - 得特呢勒的回答 - 知乎
https://www.zhihu.com/question/312520105/answer/795705835

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

内存密集是什么意思?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-10-11 09:15:26 | 显示全部楼层
nyy 发表于 2023-9-11 10:21
目前求 π 的算法中哪种收敛最快? - 得特呢勒的回答 - 知乎
https://www.zhihu.com/question/312520105/an ...

内存密集是什么意思?

这个有谁知道的?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-10-12 08:32:30 | 显示全部楼层
nyy 发表于 2023-10-11 09:15
内存密集是什么意思?

这个有谁知道的?

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

也许是这个意思
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-10-13 01:57:47 | 显示全部楼层
内存密集的意思是,考虑在内存大小为 N 的数据上进行 k=log_2(N) 次遍历计算的算法,复杂度显然是 Nk,或者 N lnN。
算法1:从头遍历到尾,遍历 k 次;
算法2:将数据分为两半,首先处理前一半 k-1 次,再处理后一半 k-1 次,再整体处理 1 次。处理过程同样使用该算法递归。
两个算法都将数据处理了 k 次,复杂度是一样的,都是 Nk,但算法2有更好的内存局部性(cache locality),而算法1是内存密集的,所以算法2会更快。

点评

nyy
终于等来了一个回答,虽然我没有看懂。  发表于 2023-10-13 06:18
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-12-21 10:56:33 | 显示全部楼层
现在证明了 Chudnovsky 公式中的级数可以用 binary splitting 算法求得。我们整理一下公式

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

也许这个是答案,虽然我没理解
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-7-23 06:38 , Processed in 0.044059 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表