【算法】高精度计算π(pi)值

😀大家好，我是白晨，一个不是很能熬夜😫，但是也想日更的人✈。如果喜欢这篇文章，点个赞👍，关注一下👀白晨吧！你的支持就是我最大的动力！💪💪💪

π π π 一直是一个备受数学界青睐的数字。从古至今，无数的学者都在努力探求着 π π π 精确值。🤼‍♂️从祖冲之到欧拉，📖从圣经到《数理精蕴》，从东至西，历经几千年的发展，特别是在计算机发明之后，对于 π π π 的求解可以说是一日千里，现在计算到几十亿位以后已经不值得惊讶。

🧐这篇文章，白晨想带大家去了解利用计算机求解 π π π 的一种方法，其中涉及到 C++，链表，大数四则运算等知识点。我会尽可能详细的讲解每一个难点的实现。

题目参考：

这次我们的最低目标是在3000ms的限制内，实现计算 π π π 到小数点后500位。

首先，如果不清楚如何计算 π π π 的同学可以先参考下面的文章，有助于理解下面的公式选择。

π 是怎么算出来的？

相信大家看完后已经对 π π π 的求法有一定的认识了，所以这里给出几个关于 π π π 的几个公式：

我们这里选择第三个公式，为什么呢？

当然是因为第三个公式是题目给出的反正切函数的幂次展开式啦（bushi）

其实是因为第三个公式是线性收敛，平均每计算一次就会得到0.3个有效数字，相比于第四个 a r c t a n x arctanx arctanx泰勒展开公式（莱布尼茨公式）来说，效率上会高出很多，而且最重要的一点是它比较容易实现，递推公式如下：

将其展开就是第三个公式，大家可以对比着看。

关于 a r c t a n x arctanx arctanx泰勒展开计算 π π π 可以参考此篇文章：π的计算

反正切函数的幂次展开式的推导具体过程：

这里我们选择 C++ 模板中的 list 类来实现（也可以使用string类等，只要可以进行大数四则运算就可以，这里为了符合题意使用链表），由于 π π π 的整数部分为3，所以我们只需要一位来存储整数部分，也即front存储整数部分，其余小数点以后的位顺次向后连接。

我们的核心目标是要实现：

我们将上面的任务拆开，分解成一个个独立的任务

这里我们选择模拟竖式乘法：

这里我们选择模拟竖式除法：

此处不再演示，大家可以类比乘法动手模拟一下，其实非常相似，代码也很相似。

这就是递推公式的最后一步，将上面计算得到的 R ( n + 1 ) R(n+1) R(n+1) 加到 S u m ( n ) Sum(n) Sum(n) 上，这其实就是一个大数加法的问题，我们选择模拟竖式加法：

此过程与乘法非常相近，在后面的代码实现中我们可以看出。

链表结点数代表着小数点后的位数，所以当然是结点越多越精确，但是结点数太多会影响性能。如果我们要实现500位的精确值，我的建议是创建550~600个结点即可。

这里有两种根据所求精度估算大致的迭代的次数的方法：

估算精度

参考文章：数据结构实验1.2—高精度计算PI值（西工大）

估算有效数字

参考文章：目前求 π 的算法中哪种收敛最快？

以上两种方法都可以使用，根据我在release发布版本的测试下，两种方法没有数量级的差别，所以使用哪一种都可以。

注：如果要提升精度，必须也增大结点个数，不能只增加迭代次数

测试结果：

方法一：

方法二：