圆周率的计算及纪录

作者: , 共 1301 字 , 共阅读 0

今天 gezhi 上有一篇关于$ \pi$ 的八卦文章,里面讲到了$ \pi$ 的计算问题。但我对其中的一些数据起了疑心,并不是说数据错了,而是作者所用的数据实在是太老了。

作者提到的$ \pi$ 的最高纪录才八百多万位,但就我以前就见过清华某 FTP 上,提供$ \pi$ 的 120 亿位的下载,总文件大小超过 5G。可惜忘了在哪个服务器上看到的了。

Google 找到一个纪录,圆周率206,158,430,000位,也就是 2060 多亿位吧。用的是Gauss-Legendre 算法(Brent-Salamin),占用内存865G,计算时间消耗37 个小时(不要以为这个时间没有多长,看看占用的内存量便知,计算在大型机或者计算集群上进行的)。

补充:计算在日本东京大学的 Information Technology Center, Computer Centre Division 进行的。所用机器有 128 个 CPU ,运算能力大约1 万亿次浮点运算每秒。

这个纪录很难说是最新的,因为它是 1999 年的,有兴趣的可以去查一查最新的纪录是多少。

补充:查到一个纪录, 2002 年有一个12411 亿位的纪录,似乎又是日本人做的。在这里有 2002 年之前的纪录列表。到这里,$ \pi$ 本身的计算已经不重要了,重要的是比拼谁家的计算机 NB。日本在这一方面的实力确实有目共睹。

$ \pi$ 的计算是一个非常有趣的话题,一般来说,都是利用级数来计算的,所以,级数的收敛速度越快,计算复杂度越低,比如 Gregory-Leibniz series :

$$ \pi=4(1-\frac13+\frac15-\frac17+\cdots)$$

就是一个收敛性能非常糟糕的级数,但下面这个

$$ \pi = 3 \sum_{n=0}^\infty \frac{(2n)!}{n!^2 (2n+1) 16^n} = 3 + \frac{1}{8} + \frac{9}{640} + \frac{15}{7168} + \cdots$$

收敛地快多了。

另外贴一个$ \pi$ 的算法,我一直没看懂过,算法高手出来解释一下?

long a=10000,b,c=2800,d,e,f[2801],g;
void main(){ 
  for(;b-c;)f[b++] =a/5;
  for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),e=d%a) 
  for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b);
}

Q. E. D.

类似文章:
相似度: 0.075
注:此游戏很有名,有同学问我其算法,我在网上找了一下,居然没多少中文资料,这里按照以前看过的一份答案回忆整理贴出。
注: 这个问题来自China Theory Week 2008的 Open Problems Session。
我所学的专业英文名是 Theoretical Computer Science ,理论计算机科学,在这里我就简化成理论计算机了。具体研究些什么呢,下面是Andrew Yao的研究方向
前面已经提到了显示中大多数难解问题问题最后都被证明是 NP-完全问题。这意味着,除非 NP=P ,它们是不可能有多项式时间算法的(而且,在这篇文章提到即使 NP=P ,人们也可能找不到一个 NP 完全问题的「有效」算法)。
一个面试题,号称是微软的
理论计算机(I)课上讲的一个问题,很有意思。