手机版|
二维码|
算法与圆周率计算
圆周率一般用π来表示，是一个在数学及物理学中普遍存在的数学常数。其定义为圆的周长与直径之比。常用圆周率的十进制近似值为3.141 592 6，另外还有由祖冲之给出的约率：22/7，及密率:355/113。圆周率计算算法 根据马克劳林(Colin Maclaurin)公式有： 在式子两边令x=1，得 这个问题可以使用算法来实现(见下图)。 下面介绍历史上两个有名的公式... 更多
圆周率是圆的周长与直径的比值，一般用希腊字母π表示，是一个在数学及物理学中普遍存在的数学常数。π也等于圆形之面积与半径平方之比。即π=周长C/直径d。圆周率公式——几何算法
凭直观推测或实物度量来计算，实验阶段得到圆周率值的结果是相当粗略的，在众多数学家的努力下，圆周率值的计算进入了科学的阶段——几何算法阶段。
1、圆内接、外切多边形
阿基米德是科学地研究圆周率这一常数的第一个人，开创了几何计算圆周率的阶段，真正使圆周率计算建立在科学的基础上，他提出了一种能够借助数学过程，把圆周率的值精确到任意精度的方法。
由上图知，圆周长大于内接正四边形而小于外切正四边形，因此2√2 圆周率 4，据说阿基米德用到了正96边形才算出这个值域，这个例子虽然可行性不强，但它至少迈出了科学探索圆周率的第一步。
阿基米德求圆周率的更精确近似值的方法，体现在他的一篇论文《圆的测定》之中。在这一书中，阿基米德第一次使用上、下界来确定圆周率的近似值，他用几何方法证明了“圆周长与圆直径之比小于3+1/7而大于3+10/71”，而且提供了误差的估计方法及计算。重要的是，这种方法从理论上而言，能够求得圆周率的更准确的值。
到公元150年左右，希腊天文学家托勒密得出圆周率=3.1416，这是自阿基米德以来取得的巨大进步。
2、割圆术的应用
割圆术(下图)是我国的数学家刘徽提出的，他是我国最早运用科学方法计算圆周率值的人，在公元263年前后，他就用此方法得出π=3.14，后人称之为“徽率”，他指出这是不足近似值。虽然他提出割圆术的时间比阿基米德晚一些，但其方法确有着更美妙之处。
割圆术仅用内接正多边形就确定出了圆周率的上、下界，比阿基米德同时用内接和外切正多边形的方法简捷得多。另外，有人认为在割圆术中刘徽提供了一种绝妙的精加工方法，以致于他将割到192边形的几个粗糙的近似值通过简单的加权平均，竟然获得具有4位有效数字的圆周率π=3927/1250=3.1416。而这一结果，正如刘徽本人指出的，如果通过割圆计算得出这个结果，需要割到3072边形，这种精加工方法的效果是奇妙的，也是割圆术中最为精彩的部分。
令人遗憾的是，由于人们对它缺乏理解而被长期遗忘了。大家更加熟悉的是祖冲之的两大贡献：其一是求得圆周率3.1415926 π 3.1415927，其二是，得到圆周率的两个近似分数，即约率为22/7，密率为355/133。他算出的圆周率的8位可靠数字，不但在当时是最精密的圆周率，而且保持世界记录九百多年，以致于有数学史家提议将这一结果命名为“祖率”。
在这一时期，数学家们对圆周率精确值的探索颇有成就，涌现出了大量的伟人，阿基米德、祖冲之、鲁道夫等，他们都为圆周率的计算做出了卓越的贡献。但是，用几何方法求其值，计算量很大，这样算下去，穷数学家的一生也改进不了多少。
古典方法已引导数学家们走了很远，到鲁道夫可以说已经登峰造极，再向前推进，必须在方法上有所突破。圆周率公式——分析算法
17世纪出现了数学分析这一锐利的工具，使得许多初等数学束手无策的问题迎刃而解，圆周率的计算历史也随之进入一个新的阶段。
1、圆周率公式与解析表达式
1579年法国数学家韦达在(《数学定律，应用于三角形》中)通过计算圆的正6×216=393216边形，得出3.1415926535 π 3.1415926537，同时他利用分析式和级数乘积来刻画圆周率。
这个式子给科学家们指出了一个崭新的计算圆周率的思路，这是分析法计算圆周率时代的第一个解析表达式。这个公式的优美至今令我们赞叹不已，它仅仅借助数2，通过一系列的加、乘、除和开平方就可算出圆周率值，且将圆周率计算到了第九位。
这一时期，是几何算法与分析算法“共同繁荣”的时期，在1621年德国-荷兰物理学家、数学家斯涅耳对原来古典方法作出了一些三角上的改进，利用这一改进，只需算到230边形，就可得到34位圆周率值。1630年，意大利罗马数学家格林贝格(利用斯涅耳的方法得到40位。这也是利用多边形周长算圆周率的最后的重要结果。
2、圆周率公式与反正切函数表达式
1669年，牛顿在在他的《分析学》中提出后，苏格兰数学家詹姆斯·格雷戈里公开了牛顿的arctanx的级数展开式。
只可惜，没有发现只需令式x=1中，就可以得到π/4=1-1/3+1/5-1/7+…，致使他就此裹足不前。这个公式后来由莱布尼兹发现，这个级数被称为莱布尼兹级数。从此，数学家们以反正切函数计算值摆开了强大的阵容。在1706年英国数学家、天文学家梅钦发现了Machin公式
利用此公式将圆周率的值计算到了100位。1734至1735年，在前人的基础上，欧拉经过不懈地努力和探索终于得出著名的欧拉公式
到了1737年，欧拉利用反正切函数arctan1=π/4，根据格雷戈里的展开式将右边展开，得到了著名的欧拉级数，
1841年，英国威廉·卢瑟福利用格雷戈里的级数和公式计算到π的208位，后来发现其中的152位是正确的。1844年，仅花了两个月时间，德国汉堡的数学家斯特拉斯尼茨基和达什使用施瓦兹公式计算到小数点后205位，但只有200位正确。1877年，历史上另一位类似于鲁道夫的英国数学家尚克斯利用梅钦公式并借助台式机械计算机花了30年时间将圆周率计算到707位。
但在1945年，福格森出于笃信圆周率是简单正态数，用手工计算机对尚克斯的的结果进行了核实，发现从528位起是错的。“可怜的尚克斯”，不仅几十年的心血大多打了“水漂”，最主要的是，他至死都不知道，他已经出错了。在尚克斯的结果发表之后不久，中国著名的数学家李善兰在用尖锥术求圆面积的时候得到了式子
这个式子的发现，足以证明我国在继祖冲之之后对圆周率的探索仍然大有作为。1848年1月，福格森和雷恩奇联合发表了经过检验的正确的圆周率的808位。1949年，英国数学家列维·史密斯和雷恩奇算出圆周率的1121位，是人工算圆周率的最高记录。
这一时期，人们对圆周率的计算可以说是有相当大的进展，学会使用解析表达式来计算圆周率的值，而且，有了计算方法的最大突破——圆周率的反正切函数表达式的发现，这个公式层出不穷，为计算圆周率的更精确的值提供了有力的科学依据。
随着人们对圆周率探索的发展，计算工具也在不断的改进，最开始自制的不精确的工具逐渐被淘汰，手盘和算盘成了大多人计算的工具，计算量不断增大，这两种计算工具已经不能满足数学家们的计算要求。此时，台式机械计算机出现了，它为数学家们的计算提供了方便。但人们并没有停止对计算工具的研究和更新，脚步依然在前进。
3、圆周率公式与概率方法
关于圆周率的值，历史上还有一种几何与分析思想之外的方法，那就是18世纪法国科学家蒲丰创造的“投针求的概率论方法”。
问题：将长为l的匀质细针随机地掷于画了等距平行线族的平面上，相邻两平行线距离为a，a l，求针与平行线相交的概率。
具体解法：设x为针中点到平行线的距离，则x∈[0，a/2]，设θ为针与平行线的夹角，则θ∈[0，π]。
由上图知，当且仅当0≤x≤1/2·sinθ，θ∈[0，π]时针与平行线相交，于是所求概率：
p=阴影面积矩形OABC面积-2l/π，于是π=2l/ap。
1901年，意大利数学家拉泽里尼投针3408次，他用压线的频率代替概率p，即取p=m/3408，求得π=3.141592。当投针次数愈多，求得π值将愈精确。在用概率方法计算圆周率值中，值得我们特别关注的是1904年，R·查特发现的“两个随意写出的数互素的概率为6/π2”。英国伯明翰市阿斯顿大学计算机科学与应用数学系的罗伯特·马修斯，利用夜空中亮星的分布来计算圆周率，他从100颗最亮的星星中随意选取一对又一对进行分析，计算它们位置之间的角距且检查了100万对因子，据此求得π的值约为3.12772，这个值与真值相对误差不超过5%。
概率方法的出现，使圆周率的计算又一次靠近了精确值，而数学家们并没有为此沾沾自喜，探索还在继续……圆周率公式与电子计算机
众所周知，电子计算机的产生及应用给人们的生活和工作带来了很大的方便，同时，它不仅为数学家们计算圆周率值带来前所未有的突破，也使圆周率的计算进入了一个新的时代。1949年，人类第一次在美国马里兰州阿伯丁的军队弹道研究实验室里用电子计算机算圆周率，包括冯·诺伊曼在内，用ENIAC和梅钦公式计算圆周率值到2048位，突破了千位数。1959年，美国国际商业机器公司(IBM)制成第二代电子计算机——世界上的一台晶体管电子计算IBM-7090。
1961年，丹尼尔·尚克斯和华盛顿的雷恩奇用IBM-7090分别使用挪威斯托默公式：
和高斯公式：
将圆周率计算到小数点后100256位，终于登上110万位高峰。1985年，乔纳森·波尔文和彼得·波尔文发表波尔文算法：
初值：a0=6-4√2，y0=√2-1，
重复计算：
和
最后得到π=1/an，它四次收敛于圆周率π。
屡创纪录的出生在苏联的美国哥伦比亚大学的戴维德·丘德诺夫斯基和格雷戈里·丘德诺夫斯基兄弟，丘德诺夫斯基兄弟将LM公式改良为式子
这个公式称为丘德诺夫斯基公式，简记“QD”，每计算一项可以得到圆周率的15位十进制精度，他的另一个更方便于计算机编程的形式是，
丘德诺夫斯基兄弟利用此公式，在96年的时候得到80亿位圆周率的值。
计算机的产生，使圆周率的计算达到了惊人的程度，圆周率的值达到难以想象的精度，再继续研究计算圆周率的精度已经变得意义不大。
