圆周率的计算及纪录

作者:

今天 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.

一个面试题,号称是微软的
理论计算机(I)课上讲的一个问题,很有意思。