也谈圆周率计算

  1. 圆周率计算历史

[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倍

参考文献:

[1] https://en.wikipedia.org/wiki/Approximations_of_%CF%80 π的近似值

[2] https://en.wikipedia.org/wiki/Chronology_of_computation_of_%CF%80 π计算年表

[3] http://numbers.computation.free.fr/Constants/PiProgram/computations.html π and its computation through the ages

[4] https://baike.baidu.com/item/%E5%9C%86%E5%91%A8%E7%8E%87/139930 百度百科圆周率

[5] https://en.wikipedia.org/wiki/Super_PI

[6] https://en.wikipedia.org/wiki/Yasumasa_Kanada金田康正

[7] https://en.wikipedia.org/wiki/Carl_St%C3%B8rmer Carl stomer

[8] http://www.numberworld.org/y-cruncher/algorithms.html

[9] http://www.numberworld.org/y-cruncher/internals/multiplication.html乘法

[10] http://numbers.computation.free.fr/Constants/Pi/piSeries.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注