伪·从零开始学算法 - 2.3 求圆周率

2018-03-14  本文已影响50人  阿啊阿吖丁

本文为圆周率日特辑~

简介

圆周率π是一个圆的周长与直径之比。即：π = C / d 。它是一个无限不循环小数，即无理数。

据说远古时期的人们根据经验以3作为圆周率的值（“径一周三”），这个值至今也能够用于一些对精度要求不高的场合（如手工做木桶）。但是，对于天体运行和面积测量等方面，3这个值未免太粗略。人们对于它的计算绝不仅限于此。

古埃及、古巴比伦、古印度、古代中国的遗迹中都能够找到关于圆周率的较精确的值，它们都能够达到3.1这个值。实际上，绝大多数情况下，那时的人还是把它当作有理数来计算的。总之，那时的计算可能仍然属于观测值加以拟合。

割圆术

割圆术是第一个有纪录、严谨计算π数值的算法。

一般来说，它是通过计算圆内接正多边形和/或圆外切正多边形的周长的方式来计算圆周率。随着正多边形的边数增长，其形状越接近圆，因此可以据它的周长或面积计算圆周率。理论上来说，它可以计算任意精度的圆周率的值。

目前所知最早这么做的是约公元前250年的阿基米德。阿基米德的算法是在计算圆的外切正六边形及内接正六边形的边长，以此计算π的上限及下限，之后再将六边形变成十二边形，继续计算边长……，一直计算到正96边形为止。由此，他计算出π的值在223/71和22/7（3.140845...和3.142857...)之间。

此后的托勒密等人也使用割圆术来计算圆周率，但他们是单向迫近，不如阿基米德的双向迫近精确。

三国时期的中国，刘徽也创立了割圆术。与之前不同的是，他的理论是数学史上最严谨完备简洁的割圆术：使用极限论来论证割圆术的正确性；双向迫近。

割之弥细，所失弥少。割之又割，以至于不可割，则与圆周合体而无所失矣。

与阿基米德相似，刘徽也是从正六边形开始计算的。不同的是，刘徽以面积来计算。他自己通过分割圆为192边形，计算出圆周率在3.141024与3.142704之间，取其近似值157/50。

刘徽割圆术原理

在下图中可以发现，如果计原多边形（黄色部分）面积为S1，新的多边形（黄色+绿色部分）面积为S2，圆面积为S，那么新的多边形与原多边形的面积之差（绿色部分）为S2 - S1，矩形ABCD的面积和为2(S2 - S1)。则有：

S2 < S < S2 + (S2 - S1)

或

S2 < S < S2 + 2(S2 - S1)

刘徽圆周率不等式示意图

后来刘徽发明一种快捷算法，通过新的多边形与原多边形的面积之差近似成等比级数来计算，可以只用96边形得到和1536边形同等的精确度，从而得令他自己满意的3.1416。

南北朝的祖冲之，运用刘徽的算法，继续分割到12288边形，求得24576边形的面积，得3.14159261864 < π < 3.141592706934，精确到了小数点后七位，保持了世界最准确圆周率达900年之久。此后他又算出来两个比较简单的近似值：约率（22/7 > π）和密率（355/113 > π）。

至于割圆术的算法，简要解释如下：

割圆术

设上图中圆半径为1，弦心距为hn；正n边形的边长为xn，面积为Sn。由勾股定理，得

hn = sqrt[1 - (xn / 2)2]

x2n = sqrt[(xn)2 + (1 = hn)2]

(n ≥ 6)

纯文字形式有点乱，可以看这个

得x6 = 1。

而且我们可以得到，正2n边形面积等于正n边形面积加n个等腰三角形的面积，即

S2n = Sn + nxn(1 - hn) / 2 (n ≥ 6)

随着n的增大，S2n不断趋近于π。

于是我们可以据此编制割圆术的算法：

割圆术(1)

据此求在正n边形下，圆周率的下限和上限：

割圆术(2)

割圆术在16~17世纪之前一直都是精确计算圆周率的解决方法。奥地利天文学家克里斯托夫·格林伯格在1630年用1040边形计算到第38位小数，至今这仍是利用多边形算法可以达到最准确的结果（当然，是人工的情况下，我在测试算法的时候，仅用53.6 ms就能计算到小数点后100位）。

无穷级数

16世纪及17世纪时，π的计算开始改用无穷级数的计算方式。但是，公式并不是唯一的。1735年，欧拉解决了巴塞尔问题，得到了关于π的一个非常精妙的公式（可能很多人都知道）：

算法如下：

欧拉的公式推导的算法

i越大，结果越精确。

此外，还有莱布尼茨公式、尼拉卡莎级数等一系列级数。但是许多级数的收敛速度很慢，莱布尼茨公式要到500000项之后，才会精确到π的第五位小数。


莱布尼茨公式 尼拉卡莎级数

印度数学家斯里尼瓦瑟·拉马努金在1914年发表了许多与π相关的公式，这些公式十分新颖，极为优雅而又颇具数学深度，收敛速度也非常快。
以下为一例：

第一位使用拉马努金公式计算π并取得进展的是比尔·高斯珀，他在1985年算得了小数点后一千七百万位。

拉马努金公式开创了现代数值近似算法的先河。，此后波尔文兄弟和楚德诺夫斯基兄弟进一步发展了这类算法。后者于1987年提出了楚德诺夫斯基公式，如下所示：

此公式每计算一项就能得到π的约14位数值，因而被用于突破圆周率的数位的计算。利用该公式，有人已经计算到小数点后第一万亿位。

但是很显然，这些公式已经变得非常复杂，难以记忆（虽然没有多少人需要记这个的）。

迭代算法

二十世纪中期计算机技术的发展、革新再次引发了计算π位数的热潮，除了之前的无穷级数，利用迭代算法计算圆周率的方法也被提出。

迭代算法因为收敛速度比无穷级数快很多，在1980年代以后广为使用。无穷级数随着项次的增加，一般来说正确的位数也会增加几位，但迭代算法每多一次计算，正确的位数会呈几何级数增长。

有一个比较有名的算法是高斯-勒让德算法，于1975年被理查德·布伦特和尤金·萨拉明独立发现。日本筑波大学于2009年8月17日宣布利用此算法计算出π小数点后2576980370000（2.58万亿）位数字。知名的电脑性能测试程序Super PI也使用此算法。

该算法的步骤如下：

第一步：设置初始值：

第二步：反复执行以下步骤直到an与bn之间的误差到达所需精度：

则π的近似值为：

流程图如下：

高斯-勒让德算法

它以迅速收敛著称，算法每执行一步正确位数就会加倍，只需25次迭代即可产生π的4500万位正确数字。不过，它的缺点是内存密集。

蒙特卡罗方法

前面介绍的是靠计算得出的方法，但这个却与概率与统计有关。

蒙特卡罗方法（Monte Carlo method）是以概率统计理论为指导的一类非常重要的数值计算方法，通过进行大量重复试验计算事件发生的频率，按照大数定律，可以求得π的近似值。

布丰投针问题就是其中一个应用的例子。当一枚长度为l的针随机地往一个画满间距为t(l ≤ t)的平行线的平面上抛掷n次， 如果针与平行直线相交了m次，那么当n充分大时就可根据以下公式算出π的近似值：π≈(2nl)/(mt)。

布丰投针问题

另一个例子是随机地往内切四分之一圆的正方形内抛掷大量的点，落在四分之一圆内的点的数量与抛掷点的总量的比值会近似等于π/4。

蒙特卡罗方法

我们以第二个例子为例，如果要编制算法，我们可以使用解析几何的方法，把“随机地往正方形内抛掷大量的点”转化为“定义一个点，该点的横坐标和纵坐标取[0,1]范围的随机数（两坐标不一定相同），重复若干次”，把“落在四分之一圆内”这个条件转化为“点是否在x2+y2=1内”。于是得下面的流程图：

蒙特卡罗方法流程图

它的缺点也很明显：随机、不精确。

结语

还有很多算法，在此我就不一一列举了。

最后我放上一张图，以展示π的计算的发展。

当数学家发现新的算法、电脑变得普及时，π的已知小数位急剧增加。注意垂直坐标使用了对数坐标

一般而言，π值并不需要过于精确便能够满足大部分的数学运算的需求。按照约尔格·阿恩特（Jörg Arndt）及克里斯托夫·黑内尔（Christoph Haenel）的计算，39个数位已足够运算绝大多数的宇宙学的计算需求，因为这个精确度已能够将可观测宇宙圆周的精确度准确至一个原子大小。但是大家仍然对π的计算乐此不疲，这有很多原因，但计算π的本身让我想起了一个故事：

有人问英国登山家乔治·马洛里为何想要攀登珠穆朗玛峰。他回答说：“因为山就在那儿。”

参考资料

上一篇下一篇

猜你喜欢

热点阅读