为什么我们总是在计算圆周率π？因为没有最快，只有更快！
徐晓亚然2019-08-26 22:10
自从人们学会了用越来越多的方法来求圆周率，似乎在怎么求圆周率的研究上已经信心十足。你提出100种要求来得到圆周率的值，那我就能想到101种方法来求解圆周率。的确，人们在这项事业上可以说是蒸蒸日上，从上古时代的割圆术，到莱布尼兹级数，投针实验，以及各种各样的无穷级数等等。每一种方法到最后都可以把圆周率精准无误地的出来，然而这并不意味着，这每一种方法实施起来都是一样的效果。这里就必须考虑一个执行效率的问题。
永无休止的π这里不考虑遥远时代的割圆术了，在两千年前的古人能得出这样的算法就已经很不容易了，你还要求他们，割圆术求π太慢了，能不能找个更快的。这样就太过苛刻了，这样苛刻的要求应该要放在微积分时代的人们身上才显得公平。
莱布尼茨莱布尼茨级数
我们再来回顾一下莱布尼茨大神的得意之作，这个式子很容易记，可操作性也不错。但是若需要在很短时间内去求很多位数的圆周率值，这个级数其实是不实用的。为什么呢？因为这个级数的收敛速度太慢了！人们用计算机模拟过，大约要计算500000项，才能精确到小数点后5位。这样的执行效率实际中会有人采用吗，反正我是不会，因为我将浪费大量的时间和资源在那里兜兜转转才勉强达到的精度值上。
欧拉大神巴塞尔级数
那再来看看欧拉大神的扬名之作，巴塞尔级数，这个级数的和也是一个包含π的数字。这个级数求和过程十分精彩，但是如果你也想通过这个公式来求圆周率那就大错特错了。虽然理论上，巴塞尔级数的收敛速度不会像莱布尼兹级数一样出奇地慢，但是也基本上也要计算到10000项，才能精确到小数点3位。所以，如果我来选择一种算法求解圆周率，这两大鼎鼎有名的公式第一轮就会被pass掉。
于是，我们想在圆周率问题上有所突破，就必须去找一些快，准，狠的算法，不对，应该是快，易，准的方法。
梅钦公式
1706年，英国数学家梅钦提出了一个收敛速度不错的公式，令人惊讶的是这个公式完全没有用到微积分，也没有采用无穷级数，仅仅是三角函数变换就得到了。这个公式是这样子的。
梅钦公式是不是觉得这个公式有点莫名其妙，好像两边驴唇不对马嘴之间也可以建立如此漂亮的等式关系。虽然看起来怪异，但是这个公式还是很好证明出来的。
梅钦公式推导得到这个反正切的公式之后，我们利用梅钦公式计算圆周率就已经完成了一大半了。那接下来呢，我们就要用亲爱的泰勒级数展开式把反正切转换成具体可以计算的形式，其中反正切的泰勒级数展开形式是这样子。
反正切函数泰勒展开式特别的，如果我们对于精度很执着，那么需要计算的式子项数就会格外地多在项数过多的情况下，这样的计算量仍然是可以简化的。这里就不得不提到我国古代一位数学家的成就，这就是秦九韶算法，在高次多项式数值计算时，可以极大地减少计算复杂度，也特别容易通过程序来实现。
数学家 泰勒秦九韶算法和梅钦公式相结合，使得这套计算算法成为历史上第一个快速求圆周率算法。1706年，英国数学家梅钦本人利用这个公式将圆周率计算到了小数点后100位，这在割圆术时代是根本无法想象的，至于为什么是这样子的，请参考鲁道夫穷尽一生用割圆术才计算到小数点35位而已。
我国古代著名数学家 秦九韶后来出现了许多类梅钦公式，都是利用反正切函数的组合。人们用差不多的风格去改造梅钦公式，在这方面做到巅峰的应该是这位，英国的谢克斯。他利用这类公式把圆周率计算到了小数点后707位，这个也是人工计算圆周率取得的最高纪录。不过可惜的是，后人检查他的计算结果，发现第528位是错误的，所以在528位之后的结果就都是错误的了。
秦九韶算法原理 转自维基百科拉马努金公式
虽然说梅钦公式的极大得改进了求π的进程，但是如果我们想计算千万位圆周率数字，梅钦公式就显得力不从心了。然而数学家们的追求是无止境的，琢磨琢磨就总会有新的玩意出来，一句话，求π公式里没有最快只有更快。这里就需要一位超级大神再一次搬出来了，印度的传奇数学家，拉马努金。
拉马努金拉马努金，1887年出生在印度的小镇上，从小家庭贫困，生活艰难，不过好在他很早就发现自己在数学上有着常人无可比拟的天赋。在那个印度教育普遍不行的情况下， 拉马努金靠着一本记载了5000个公式的数学教普书《纯粹数学与应用数学概要》。他完全自学，掌握了最高级的数学技巧，他甚至补全了那本书中很多缺少的内容，比如很多高级公式的证明。这本书也决定了拉马努金日后的研究方向，他受到这本书的启发，日后提出了许许多多骇人听闻的公式，大约有3900个，绝大多数都是对的。任何一个数学爱好者都会把这些公式当成是宝藏一般，细心研究的。
比如，他曾经提出过很多关于求π的公式，这些公式都有以下几个特点：等号右边的构造超乎常人想象，收敛速度极快！比如这个拉马努金在1914年发布的以他自己名字命名著名公式。
拉马努金公式我们普通人根本难以想象等式后边的部分如此繁杂无序，确实深深地与π产生等价关系，事实上，人们也是在研究了很久才得知拉马努金是如何得出这样的公式的。这是来自高深的椭圆积分函数，我们不去深刻研究如何由椭圆积分函数推导出上面这个式子，这已经超过晓然菌的能力了。我们只是来欣赏一下这样的式子究竟有多厉害就行了。
拉马努金笔记右边的组成部分虽然纷繁复杂，但是倘若我们一项一项地来整理还是比较容易用编程的方法来实现的。现在利用一台简单的的计算器来进行，我们发现只要计算一次，精度就会超过计算器能够显示的有效位数。大概这里的k每次累加计算一次，我们就会得到圆周率8位有效数字。也就是说，你只要进行第一步计算，其结果就大大超过了莱布尼茨公式50万步计算的总和，这是一个何其壮哉的进步！当然，当年拉马努金发现这个公式的初衷可不是为了圆周率计算，可能他也完全没有想过这个公式有着如此恐怖的计算速度。
Chudnovsky公式
在进入到了计算机时代，有些算法如果易于编程，便立刻会有极其庞大的计算成果出现。1985年，Gosper利用拉马努金公式，用计算机得到圆周率小数点后1750万位。然而，有人仍然觉得拉马努金公式有深度可挖，这个公式应该也会像梅钦公式一样，可以继续改进，获得更加恐怖的收敛速度。
David Chudnovsky1989年，Chudnovsky两兄弟在一起合作，将拉马努金公式改进不少，这个公式也当之无愧地称为Chudnovsky公式。比起拉马努金公式，这两兄弟得到的公式就更加鬼畜了。就是下面这个。
Chudnovsky公式这个公式可不得了，之前拉马努金公式每计算一项可以获得8位有效数字已经很了不起了，然而他们的这个公式居然可以做到每计算一项得出15位有效数字！1994年，他们利用这个强大的公式，得到了圆周率小数点后40.44亿位。
你以为到了这里就结束了么？当然没有，人们对于算法的改进是永无止境的，很多算法在手工时代看不出效率高低，但是一旦拿到计算机上执行，在计算到百万位，上亿位之后，是一定能分得清效率高低的。
高斯勒让德迭代公式
现在我们的计算机还是只能根据指令来计算的，可能在以后会有别的方式来主导它的计算。它不怕繁杂重复的执行命令，只要你给时间和存储空间，如果算法得当，那么就一定会有一个结果出来。比如，计算机最喜欢做的就是迭代计算，所谓迭代，就是把一个大问题先分解成很多个小过程，小过程的计算很简单，但是后面一步的计算是建立在前一步的基础上的。如果问题足够麻烦，可能会有非常多的小步骤，如果你只盯着其中的一小步，你会觉得这样的计算毫无意义，很难让你有着继续下去的动力。
勒让德比如斐波那契数列的定义，这就是一个最简单的迭代方式：后一项总是前面两项的和。倘若我们不知道这个数列的通项公式，那就只能用这样近乎呆滞的方法一步一步来算。比如让你求斐波那契数列的第30项，这个计算量对于人工来说就已经很庞大了。然而，这样迭代的计算过程对于机器来说，却是最擅长的事情了。
斐波那契数列递推关系有一个著名的圆周率迭代计算方法，这个迭代算法的收敛速度已经到了一种登峰造极的地步。高斯勒让德迭代算法。
高斯勒让德算法 转自维基百科这个算法并不是高斯和勒让德得出的，而是1975年理查德·布伦特和尤金·萨拉明基于上面两位大神的某些成果独立发现的。和别的迭代公式类似，初始值很简单，每一步计算难度也不大。不过这个收敛的速度，怎么形容呢？这套算法只要迭代25次就可以得到4500万位有效数字！1999年，日本的高桥大介和金田康正用这个算法计算到了圆周率的2061亿位数字，创造了当时的世界纪录。
多次打破圆周率世界纪录的金田康正2019年3月14日，一位日裔女程序员艾玛利用谷歌云平台计算引擎得到了圆周率31.4万亿位数字，这也是人类目前的新纪录。这样的成果是在谷歌云平台计算引擎上使用了25台虚拟机，历时4个多月得到的，整个计算过程中一共产生了大约170TB的数据，他们使用的就是Chudnovsky公式。
日裔女程序员艾玛31.4万亿位当然不是人类追求圆周率数值计算的终点，每一次数值里程碑背后都附带着一个当时最先进的算法。到目前为止，人们仍然孜孜不倦地探索着求圆周率的新算法，我们的最终目的不是求到了多少多少位圆周率，而是在计算圆周率的过程中，我们可以检验很多内容深刻的算法。用更少的时间，更小的空间，更少的资源来获得更多精准的数据。
超级计算机 昼夜不停计算圆周率从人工计算到机器计算，关于圆周率的各路求法其实也代表了科学水平的发展水平。尤其是现代计算机算力的加成让算法越来越深刻，成果也越来越丰富。我们也会在这条计算的道路上一直走下去，永不停息！
举报/反馈
0
0
收藏
分享
