圆周率的计算方法.doc

圆周率的计算方法古人计算圆周率，一般是用割圆法。即用圆的内接或外切正多边形来逼近圆的周长。Archimedes用正96边形得到圆周率小数点后3位的精度；刘徽用正3072边形得到5位精度；Ludolph Van Ceulen用正262边形得到了35位精度。这种基于几何的算法计算量大，速度慢，吃力不讨好。随着数学的发展，数学家们在进行数学研究时有意无意地发现了许多计算圆周率的公式。下面挑选一些经典的常用公式加以介绍。除了这些经典公式外，还有很多其他公式和由这些经典公式衍生出来的公式，就不一一列举了。 Machin公式 这个公式由英国天文学教授John Machin于1706年发现。他利用这个公式计算到了100位的圆周率。Machin公式每计算一项可以得到1.4位的十进制精度。因为它的计算过程中被乘数和被除数都不大于长整数，所以可以很容易地在计算机上编程实现。 Machin.c 源程序 还有很多类似于Machin公式的反正切公式。在所有这些公式中，Machin公式似乎是最快的了。虽然如此，如果要计算更多的位数，比如几千万位，Machin公式就力不从心了。下面介绍的算法，在PC机上计算大约一天时间，就可以得到圆周率的过亿位的精度。这些算法用程序实现起来比较复杂。因为计算过程中涉及两个大数的乘除运算，要用FFT(Fast Fourier Transform)算法。FFT可以将两个大数的乘除运算时间由O(n2)缩短为O(nlog(n)。 关于FFT算法的具体实现和源程序，请参考Xavier Gourdon的主页 Ramanujan公式 1914年，印度数学家Srinivasa Ramanujan在他的论文里发表了一系列共14条圆周率的计算公式，这是其中之一。这个公式每计算一项可以得到8位的十进制精度。1985年Gosper用这个公式计算到了圆周率的17,500,000位。 1989年，David & Gregory Chudnovsky兄弟将Ramanujan公式改良成为： 这个公式被称为Chudnovsky公式，每计算一项可以得到15位的十进制精度。1994年Chudnovsky兄弟利用这个公式计算到了4,044,000,000位。Chudnovsky公式的另一个更方便于计算机编程的形式是： AGM(Arithmetic-Geometric Mean)算法 Gauss-Legendre公式： 初值： 重复计算： 最后计算： 这个公式每迭代一次将得到双倍的十进制精度，比如要计算100万位，迭代20次就够了。1999年9月Takahashi和Kanada用这个算法计算到了圆周率的206,158,430,000位，创出新的世界纪录。 Borwein四次迭代式： 初值： 重复计算： 最后计算： 这个公式由Jonathan Borwein和Peter Borwein于1985年发表，它四次收敛于圆周率。 Bailey-Borwein-Plouffe算法 这个公式简称BBP公式，由David Bailey, Peter Borwein和Simon Plouffe于1995年共同发表。它打破了传统的圆周率的算法，可以计算圆周率的任意第n位，而不用计算前面的n-1位。这为圆周率的分布式计算提供了可行性。1997年，Fabrice Bellard找到了一个比BBP快40的公式： 时间纪录创造者小数点后位数前2000古埃及人1前1200中国1前500圣经1前250Archimedes3263刘徽5480祖冲之71429Al-Kashi141593Romanus151596Ludolph Van Ceulen201609Ludolph Van Ceulen351699Sharp711706John Machin1001719De Lagny127(112位正确)1794Vega1401824Rutherford208(152位正确)1844Strassnitzky & Dase2001847Clausen2481853Lehmann2611853Rutherford4401874William Shanks707(527位正确)20世纪后年月纪录创造者所用机器小数点后位数1946Ferguson62019471Ferguson71019479Ferguson & Wrench8081949Smith & Wrench1,1201949Reitwiesner et alENIAC2,0371954Nicholson & JeenelNORC3,0921957FeltonPegasus7,48019581GenuysIBM 70410,00019585FeltonPegasus10,0211959GuilloudIBM 70416,1671961Shanks & WrenchIBM 7090100,2651966Guilloud & FilliatreIBM 7030250,0001967Guilloud & DichamptCDC 6600500,0001973Guilloud & BouyerCDC 76001,001,2501981Miyoshi & KanadaFACOM M-2002,000,0361982Guiloud2,000,0501982TamuraMELCOM 900II2,097,1441982Tamura & KanadaHITACHI M-280H4,194,2881982Tamura & KanadaHITACHI M-280H8,388,5761983Kanada, Yoshino & TamuraHITACHI M-280H16,777,206198310Ushiro & KanadaHITACHI S-810/2010,013,395198510GosperSymbolics 367017,526,20019861BaileyCRAY-229,360,11119869Kanada & TamuraHITACHI S-810/2033,554,414198610Kanada & TamuraHITACHI S-810/2067,108,83919871Kanada, Tamura & Kubo et alNEC SX-2134,217,70019881Kanada & TamuraHITACHI S-820/80201,326,55119895ChudnovskysCRAY-2 & IBM-3090/VF480,000,00019896ChudnovskysIBM 3090525,229,27019897Kanada & TamuraHITACHI S-820/80536,870,89819898ChudnovskysIBM 30901,011,196,691198911Kanada & TamuraHITACHI S-820/801,073,741,79919918Chudnovskys2,260,000,00019945Chudnovskys4,044,000,00019958Takahashi & KanadaHITACHI S-3800/4804,294,967,286199510Takahashi & Kanada6,442,450,93819977Takahashi & Kanada51,539,600,00019994Takahashi & Kanada68,719,470,00019999Takahashi & KanadaHITACHI SR8000206,158,430,000圆周率的最新计算纪录 新世界纪录 圆周率的最新计算纪录由两位日本人Daisuke Takahashi和Yasumasa Kanada所创造。他们在日本东京大学的IT中心，以Gauss-Legendre算法编写程序，利用一台每秒可执行一万亿次浮点运算的超级计算机，从日本时间1999年9月18日19:00:52起，计算了37小时21分04秒，得到了圆周率的206,158,430,208(3*236)位十进制精度，之后和他们于1999年6月27日以Borwein四次迭代式计算了46小时得到的结果相比，发现最后45位小数有差异，因此他们取小数点后206,158,430,000位的p值为本次计算结果。这一结果打破了他们于1999年4月创造的68,719,470,000位的世界纪录。 最后20位 圆周率小数点后206,158,430,000位的最后20位为22144 96687 55157 30964 p小数点后2000亿位中各数字出现的次数 0 : 20000030841 1 : 199999147112 : 20000136978 3 : 200000693934 : 19999921691 5 : 199999170536 : 19999881515 7 : 199999675948 : 20000291044 9 : 19999869180 一些有趣的数字序列在p小数点后出现的位置 数字序列出现的位置0123456789126,852,899,24541,952,536,16199,972,955,571102,081,851,717171,257,652,3690123456789053,217,681,704148,425,641,592432109876543149,589,314,822543210987654197,954,994,28998765432109123,040,860,473133,601,569,485150,339,161,883183,859,550,2370987654321042,321,758,80357,402,068,39483,358,197,9541098765432189,634,825,550137,803,268,208152,752,201,2452718281828445,111,908,393PC机上的计算 PiFast 目前PC机上流行的最快的圆周率计算程序是PiFast。它除了计算圆周率，还可以计算e和sqrt(2)。PiFast可以利用磁盘缓存，突破物理内存的限制进行超高精度的计算，最高计算位数可达240亿位，并提供基于Fabrice Bellard公式的验算功能。 下载PiFast ver4.1(Win平台) 作者Xavier Gourdon主页 PC机上的最高计算记录 最高记录12,884,901,372位时间2000年10月10日记录创造者Shigeru Kondo所用程序PiFast ver3.3机器配置Pentium III 1G, 1792M RAM，WindowsNT4.0，40GBx2(IDE,FastTrak66)计算时间1,884,375秒 (21.8天)验算时间29小时120亿位圆周率下载 圆周率小数点后1000位：1415926535 8979323846 2643383279 5028841971 69399375105820974944 5923078164 0628620899 8628034825 34211706798214808651 3282306647 0938446095 5058223172 53594081284811174502 8410270193 8521105559 6446229489 54930381964428810975 6659334461 2847564823 3786783165 27120190914564856692 3460348610 4543266482 1339360726 02491412737245870066 0631558817 4881520920 9628292540 91715364367892590360 0113305305 4882046652 1384146951 94151160943305727036 5759591953 0921861173 8193261179 31051185480744623799 6274956735 1885752724 8912279381 83011949129833673362 4406566430 8602139494 6395224737 19070217986094370277 0539217176 2931767523 8467481846 76694051320005681271 4526356082 7785771342 7577896091 73637178721468440901 2249534301 4654958537 1050792279 68925892354201995611 2129021960 8640344181 5981362977 47713099605187072113 4999999837 2978049951 0597317328 16096318595024459455 3469083026 4252230825 3344685035 26193118817101000313 7838752886 5875332083 8142061717 76691473035982534904 2875546873 1159562863 8823537875 93751957781857780532 1712268066 1300192787 6611195909 2164201989 圆周率小数点后1亿位： 全部下载大约55M。 pi00010m.zip (5,699,807字节) pi00020m.zip (5,714,446字节) pi00030m.zip (5,713,465字节) pi00040m.zip (5,713,435字节) pi00050m.zip (5,713,391字节) pi00060m.zip (5,713,779字节) pi00070m.zip (5,713,196字节) pi0008