也谈圆周率计算 – Baocheng's home page

圆周率计算历史

[1] [2] [3] [4] 给出详尽的关于圆周率计算的历史。我们这里仅给出几个有代表性的事件。

1.1. 第一个将π计算到小数点后2位数字的是古希腊数学家阿基米德 Archimedes，阿基米德是有史以来最伟大的三个数学家之一，另外两个是牛顿和高斯。

1.2. 第一个将圆周率计算到小数点后7位以上者是中国南北朝时期的数学家祖冲之，他的记录保持了1000多年，直到1424年才被中亚数学家阿尔卡西(AI-Kashi）打破。

1.3. 第一个将圆周率计算到100位以上者，是英国数学家梅钦（John Machin）他在1706将圆周率计算到100位。

1.4. 第一个突破500位，是威廉·香克斯（ William Shanks），他在1874年，将圆周率计算至707位，但只有527位是正确的。

1.5. 圆周率的手工计算最高纪录由是英国的弗格森(DF Ferguson)，1948他和美国的伦奇共同发表了π的808位小数值。

1.6. 第一个突破1000位的是DF Ferguson和John Wrench，他们使用台式计算器将pi计算至1120位，这也是计算机出现之前的最高纪录。

1.7. 第一个突破10000位，Francois Genuys，他在1958年1月用一台IBM 704将圆周率计算到1万位。

1.8. 第一个突破1亿位的，是日本人金田康正(Yasumasa Kanada)，他在1987年1月，他在一台NEC SX-2电脑上，将圆周率计算到134,214,700位。

1.9. 第一个突破1万亿位的，也是日本人金田康正，他使用的就是一种Machine公式。

2. 圆周率的算法

2.1.多边型法

在文艺复兴时代（或者说17世纪）之前，圆周率都是通过计算多边形的周长来近似得到的。这类算法很慢，祖冲之将圆周率至小数点后7位花了15年时间。

2.2 梅钦公式或类梅钦公式

这个公式是英国数学家梅钦（John Machin）提出，1706年梅钦计算π值突破100位小数大关，他利用了如下公式：

这个公式有2项，每项都是一个常数乘以arctan(1/p)形式的数。而arctan(1/p)的展开式是一个级数形式，可以使用普通的方法来计算，也可以使用Binary splitting方法使得计算效率更高。这个公式非常好用，甚至在2002年12月，金田康正首次将圆周率计算到1万亿位以上时，他使用的就是一种Machine公式，这个公式是挪威人Størmer提出来的，见 [3]和[7]

2.3 拉马努金公式和Chudnovsky公式

印度传奇数学家给出多个计算圆周率率的公式，见[10], 这里我们贴出至今仍被广为使用的那个公式。

楚德诺夫斯基（Chudnovsky）公式，楚德诺夫斯基兄弟是美国数学家和工程师，楚德诺夫斯基兄弟发明了一个新的公式，称之为Chudnovsky公式，这个公式是Ramanujan公式改良的基础上改良而成的。1994年Chudnovsky兄弟利用这个公式计算到了4,044,000,000位。

Chudnovsky公式的另一个更方便于计算机编程的形式是：
2.3 AGM算法

在1976年，理查德·布兰特(Richard Peirce Brent)和尤金·萨拉明（Eugene Salamin）独立的发表了新的计算圆周率的算法。称之为布伦特-萨拉明（或萨拉明-布伦特）算法。这个算法是基于是一个迭代算法，每迭代一次，有效数字增加1倍。这个算法用到高斯-勒让德AGM迭代算法。其方法见下

初值：

重复计算：

最后计算：

3. 当代圆周率计算的几个重要人物

3.1. 金田康正（Kanada Yasumasa）

是一位日本数学家，东京大学信息科学系教授，在过去30年中他的21次计算中，创造了11次世界纪录。他的名字出现在[2]中19次。

3.2. Chudnovsky兄弟

是美国数学家和工程师,他们开发了Chudnovsky算法，并多次创造了圆周率的计算纪录。在[2]中，他们的名字出现了5次。

3.3. 法布里斯•贝拉

是一位杰出的软件工程师，FFmpeg 和QEMU 软件的创建者。他用自己开发的软件在一台CPU为Core i7 CPU 2.93GHz台式机上运行了90多天，将圆周率算到小数点后27000亿位，创造当新的世界纪录。

3.4. 近藤茂（Shigeru Kondo）

是一名狂热的圆周率爱好者。他并非数学家，他总是使用别人写的程序来计算圆周率。在近几年，他使用余智恒（Alexander Yee）开发的y-cruncher 程序创创造了3次世界纪录，分别将圆周率计算到5万亿，10万亿，和12万亿位。他也曾用另一个程序PiFast创造了在PC上圆周率计算位数的世界纪录，但计算位数没有超过当时的巨型机，故在[2]中没有提及。在[3]中，他的名字出现了23次，比如在2003年9月，他在一台P4 3.2GHZ的电脑上，将圆周率250亿。

3.5．余智恒（Alexander Yee）

是一位年轻的计算机天才，在2010年，近藤茂用他的程序创造了新的世界记录时，他仅仅22岁。如今，他的程序世界上计算圆周率最快的程序。

4. 几种计算圆周率的软件

4.1. SuperPi

是金田康正基于运行巨型机上的程序改写的，可运行在普通PC的版本。Super PI在超频社区非常流行，既可以作为测试这些系统性能的基准，也可以作为压力测试来检查它们是否仍然正常工作。该程序使用浮点FFT算法来做大数乘法，使用AGM算法来计算圆周率。相对于后来者，这个程序的速度并不是很快。我自己编写的仅仅使用Toom-4乘法和AGM算法的计算Pi的程序居然可和SuperPI打成平手。关于SuperPi,请参见[4]

4.2. PiFast

Xavier Gourdon的PiFast是2003年Microsoft Windows最快的程序。据其作者称，它可以在2.4 GHz Pentium 4上以3.5秒计算一百万位数。PiFast还可以计算其它无理数等e和√2。它也可以在效率较低的情况下以很少的内存工作（低至几十兆以计算十亿位以上的数字）,PiFast可使用拉马努金公式和和Chudnovsky公式来计算圆周率，比SuperPi要快很多，但他依然是一个单线程的程序，运行在32位的操作系统，不能重发发挥CPU的性能。

4.3. QuickPi

Steve Pagliarulo写的QuickPiye 也是同样优秀的计算Pi的程序，当计算精度在4亿位以下时，他的速度快于PiFast。像PiFast一样，QuickPi也可以计算其他的无理数，比如e，√2和√3。

4.4. y-cruncher

他是余智恒写的一个计算PI的程序，可运行在32位或者64位操作系统，可工作于多线程模式或者单线程模式，可充分发挥CPU的计算能力。当然，这个程序也是最复杂的。[8]提到，这个程序的源码竟包含47万行以上的代码。[9]中提到，这个程序使用了多至9种计算大数乘法的算法。

4.5. 其他计算圆周率的程序

除了上述几个程序外，还有其他一些程序同样可计算圆周率，这里就不再重点介绍了。他们有wPrime，IntelBurnTest，Prime95，Montecarlo superPI，OCCT等。

5.y-cruncher 和Pifast的性能比较

由于piFast是32位程序，仅仅运行单线程模式。所以我的测试仅Focus在单线程模式，测试计算2500万位圆周率的运行时间，时间单位为秒。测试结果1

运行环境	Win7 64bit, CPU: i7-4700HQ @ 2.40GHz, 8G RAM
程序	y-cruncher	PiFast
命令行或参数	y-cruncher custom pi -dec:25m -TD:1 -PF:none	0,0,25000000,2048,1
Final Multiply	0.213	1.51
Total time	8.039	45.55
Note:	Total time不包括从2进制转化10进制的时间。以Final Multiply步骤为参照。y-cruncher的速度是PiFast的7倍

测试结果2

运行环境	Win7 32bit, CPU: i7-2600K @ 3.40GHz, 16G RAM
程序	y-cruncher	PiFast
命令行或参数	y-cruncher custom pi -dec:25m -TD:1 -PF:none	0,0,25000000,2048,1
Final Multiply	0.704	1.29
Total time	22.513	40.34
Note:	Total time不包括从2进制转化10进制的时间，Final Multiply步骤为参照y-cruncher的速度是PiFast的1.8倍