圆周率的计算公式是什么???
图为信息科技（深圳）有限公司
2021-01-25 广告
边缘计算可以咨询图为信息科技(深圳)有限公司了解一下，图为信息科技（深圳）有限公司（简称：图为信息科技）是基于视觉处理的边缘计算方案解决商。作为一家创新企业，多年来始终专注于人工智能领域的发展，致力于为客户提供满意的解决方案。...
点击进入详情页
本回答由图为信息科技（深圳）有限公司提供
展开全部
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
展开全部
一、中国圆周率公式的分类
外国圆周率公式为高精度圆周率的计算立下了汗马功劳，并为许多数学人所熟习，但并不适合普通人使用，下面向数学爱好者和中学生们介绍一组中国人自己研究的普及型圆周率公式：
一基本公式：
⑴π＝180°sinθ∕θ 、
⑵π＝180°∕(θ cscθ)、
⑶π＝180°tgθ∕θ 、
⑷π＝180°∕(θ ctgθ) 、
（θ→0°θ＞0°）
此类公式以圆内接或外切直角三角形或正多边形的边所对应的圆心角为计算依据，外形简单，计算方便，对圆周率的概括比较全面系统；同时，既是1弧度公式，又是1角度公式。
二派生公式：
⑸π＝(n/2)*sin(360°∕n) 、
⑹π＝1∕((2/n)*csc(360°∕n)) 、
⑺π＝(n/2)*tg(360°∕n) 、
⑻π＝1∕((2/n)*ctg(360°∕n)) 、
（n→∞, n≥5）
此类派生公式可以由基本公式导出或单独推导，并以圆内接或外切直角三角形数量为计算依据，是专用性、针对性较强的圆周率公式。
三派生公式：
⑼π＝nsin(180°∕n) 、
⑽π＝n/csc(180°∕n) 、
⑾π＝ntg(180°∕n) 、
⑿π＝n/ctg(180°∕n) 、
（n→∞,n≥3）
此类派生公式可以由基本公式导出或单独推导，并以圆内接或外切正多边形的边数为计算依据，是中国割圆术公式的典型代表。
四专业公式：
⑴π＝2＾n√（2-√（2+…√2+）…）
⑵π＝3×2＾n√（2-√（2+…√（2+√3）…）
⑶π＝2×2＾n√（2-√（2+…√2+）…）/√（2+√（2+…√2+）…）
⑷π＝6×2＾n√（2-√（2+…√3）…）/√（2+√（2+…√3）…）
（n→∞，根式中有n个2）
专业公式可由基本公式或倍边公式推导，它们是割圆术公式的最高形式，是以圆内接或外切正四边形或正六边形为基础，不断分割至无穷，从而得到适合专家们使用的表达式。
根据以上公式和三角函数间的关系，还可导出更为复杂一些的圆周率公式。
二、中国圆周率的计算
在圆周率的日常应用中，我们根本不需要对其进行计算，因为数学家已经计算好了，直接拿来运用即可；但对于数学爱好者和中学生来说，亲自动手计算圆周率，将会进一步加深对圆周率的理解。
在计算机发明以前，圆周率的计算主要是靠手工计算和其他简易工具的计算，今天我们可以直接运用计算机或计算器进行计算，计算器的精度一般在10位左右，计算机上的计算器精度一般在30或60位左右，如果需要数以万计、亿计的精度，则需要将三角函数原始公式代入，转换成专业公式并编制专用程序进行计算即可，这里只是简单介绍常规计算。
圆周率公式非常多，我们只取其中几个最简单的中国圆周率公式进行讲解：
⑴ π＝180°sinθ∕θ 、
⑵ π＝180°tgθ∕θ 、
（θ→0°θ＞0°）
一模拟计算正24576边形的圆周率（祖率）
∵ θ＝180°∕24576＝0.007324219°
∴ ⑴ π＝180°sinθ∕θ
＝180°×sin0.007324219°∕0.007324219°
＝180°×0.0001278317363∕0.007324219°
＝3.1415926
∴ ⑵ π＝180°tgθ∕θ
＝180°×tg0.007324219°∕0.007324219°
＝180°×0.0001278317374∕0.007324219°
＝3.1415927
如果采用传统的割圆术公式（倍边公式）进行祖率计算，运算过程将达上百步，不管是采用手工还是计算器，其运算过程都是十分繁琐的。
二计算30位精度的圆周率（win系统计算器）
一般地，θ小数每增加一位，则π有效值增加两位。
为了简化运算，θ取值为1.8°×10＾（-15）即可。
∴ ⑴ π＝180°sinθ∕θ
＝sin（1.8°×10＾（-15））×180°∕1.8°×10＾（-15）
＝3.14159 26535 89793 23846 26433 83279 5×10＾（-17）
×180°∕1.8°×10＾（-15）
＝3.14159 26535 89793 23846 26433 83279 5
∴ ⑵ π＝180°tgθ∕θ
＝tg（1.8°×10＾（-15））×180°∕1.8°×10＾（-15）
＝3.14159 26535 89793 23846 26433 83279 5×10＾（-17）
×180°∕1.8°×10＾（-15）
＝3.14159 26535 89793 23846 26433 83279 5
三十位或六十位的精度已能满足大多数科研及专业应用，成千上万、上亿位的精度主要是专家们为了检验圆周率公式及程序的优劣和计算机性能的高低等特殊需要而存在的。
三计算100位精度的圆周率（专业软件）
取π＝2＾n√（2-√（2+…√2）…）
（n→∞）
该公式的精度一般为0.56n,即n=100/0.56≈180
π＝2＾180√（2-√（2+…√2）…）
＝3.14159 26535 89793 23846 26433 83279 50288 41971 69399 37510
58209 74944 59230 78164 06286 20899 86280 34825 34211 70679 8
利用计算器、计算机计算圆周率效率极高，相信一定能够给数学爱好者和中学生们带来意想不到的效果。
三、中国圆周率的主要作用
在圆周率的历史长河中，由于计算工具和计算方法的落后，圆周率公式的推导主要是为手工计算而设计的，其主要作用就是为计算而计算，因而得出的圆周率公式非常复杂，除了专家们能够掌握使用外，普通人是知其然而不知所以然。所以旧的圆周率公式很不利于大众普及。
由于计算工具的快速发展，手工计算圆周率已成为历史。然而，圆周率公式依旧复杂，普通人即使利用计算器或计算机计算圆周率依然很不方便。
值得庆幸的是：中国的许多数学家和众多的业余数学爱好者们前赴后继，利用中国古代的割圆术思想与现代数学知识相结合，诞生了今天的中国圆周率公式，该公式正好弥补了圆周率的千古缺陷。
所以，中国圆周率公式现今的主要作用是：
1、简捷、全面、准确的描述圆周率及相关性质。
2、快速、方便、有趣的计算圆周率。
外国圆周率公式为高精度圆周率的计算立下了汗马功劳，并为许多数学人所熟习，但并不适合普通人使用，下面向数学爱好者和中学生们介绍一组中国人自己研究的普及型圆周率公式：
一基本公式：
⑴π＝180°sinθ∕θ 、
⑵π＝180°∕(θ cscθ)、
⑶π＝180°tgθ∕θ 、
⑷π＝180°∕(θ ctgθ) 、
（θ→0°θ＞0°）
此类公式以圆内接或外切直角三角形或正多边形的边所对应的圆心角为计算依据，外形简单，计算方便，对圆周率的概括比较全面系统；同时，既是1弧度公式，又是1角度公式。
二派生公式：
⑸π＝(n/2)*sin(360°∕n) 、
⑹π＝1∕((2/n)*csc(360°∕n)) 、
⑺π＝(n/2)*tg(360°∕n) 、
⑻π＝1∕((2/n)*ctg(360°∕n)) 、
（n→∞, n≥5）
此类派生公式可以由基本公式导出或单独推导，并以圆内接或外切直角三角形数量为计算依据，是专用性、针对性较强的圆周率公式。
三派生公式：
⑼π＝nsin(180°∕n) 、
⑽π＝n/csc(180°∕n) 、
⑾π＝ntg(180°∕n) 、
⑿π＝n/ctg(180°∕n) 、
（n→∞,n≥3）
此类派生公式可以由基本公式导出或单独推导，并以圆内接或外切正多边形的边数为计算依据，是中国割圆术公式的典型代表。
四专业公式：
⑴π＝2＾n√（2-√（2+…√2+）…）
⑵π＝3×2＾n√（2-√（2+…√（2+√3）…）
⑶π＝2×2＾n√（2-√（2+…√2+）…）/√（2+√（2+…√2+）…）
⑷π＝6×2＾n√（2-√（2+…√3）…）/√（2+√（2+…√3）…）
（n→∞，根式中有n个2）
专业公式可由基本公式或倍边公式推导，它们是割圆术公式的最高形式，是以圆内接或外切正四边形或正六边形为基础，不断分割至无穷，从而得到适合专家们使用的表达式。
根据以上公式和三角函数间的关系，还可导出更为复杂一些的圆周率公式。
二、中国圆周率的计算
在圆周率的日常应用中，我们根本不需要对其进行计算，因为数学家已经计算好了，直接拿来运用即可；但对于数学爱好者和中学生来说，亲自动手计算圆周率，将会进一步加深对圆周率的理解。
在计算机发明以前，圆周率的计算主要是靠手工计算和其他简易工具的计算，今天我们可以直接运用计算机或计算器进行计算，计算器的精度一般在10位左右，计算机上的计算器精度一般在30或60位左右，如果需要数以万计、亿计的精度，则需要将三角函数原始公式代入，转换成专业公式并编制专用程序进行计算即可，这里只是简单介绍常规计算。
圆周率公式非常多，我们只取其中几个最简单的中国圆周率公式进行讲解：
⑴ π＝180°sinθ∕θ 、
⑵ π＝180°tgθ∕θ 、
（θ→0°θ＞0°）
一模拟计算正24576边形的圆周率（祖率）
∵ θ＝180°∕24576＝0.007324219°
∴ ⑴ π＝180°sinθ∕θ
＝180°×sin0.007324219°∕0.007324219°
＝180°×0.0001278317363∕0.007324219°
＝3.1415926
∴ ⑵ π＝180°tgθ∕θ
＝180°×tg0.007324219°∕0.007324219°
＝180°×0.0001278317374∕0.007324219°
＝3.1415927
如果采用传统的割圆术公式（倍边公式）进行祖率计算，运算过程将达上百步，不管是采用手工还是计算器，其运算过程都是十分繁琐的。
二计算30位精度的圆周率（win系统计算器）
一般地，θ小数每增加一位，则π有效值增加两位。
为了简化运算，θ取值为1.8°×10＾（-15）即可。
∴ ⑴ π＝180°sinθ∕θ
＝sin（1.8°×10＾（-15））×180°∕1.8°×10＾（-15）
＝3.14159 26535 89793 23846 26433 83279 5×10＾（-17）
×180°∕1.8°×10＾（-15）
＝3.14159 26535 89793 23846 26433 83279 5
∴ ⑵ π＝180°tgθ∕θ
＝tg（1.8°×10＾（-15））×180°∕1.8°×10＾（-15）
＝3.14159 26535 89793 23846 26433 83279 5×10＾（-17）
×180°∕1.8°×10＾（-15）
＝3.14159 26535 89793 23846 26433 83279 5
三十位或六十位的精度已能满足大多数科研及专业应用，成千上万、上亿位的精度主要是专家们为了检验圆周率公式及程序的优劣和计算机性能的高低等特殊需要而存在的。
三计算100位精度的圆周率（专业软件）
取π＝2＾n√（2-√（2+…√2）…）
（n→∞）
该公式的精度一般为0.56n,即n=100/0.56≈180
π＝2＾180√（2-√（2+…√2）…）
＝3.14159 26535 89793 23846 26433 83279 50288 41971 69399 37510
58209 74944 59230 78164 06286 20899 86280 34825 34211 70679 8
利用计算器、计算机计算圆周率效率极高，相信一定能够给数学爱好者和中学生们带来意想不到的效果。
三、中国圆周率的主要作用
在圆周率的历史长河中，由于计算工具和计算方法的落后，圆周率公式的推导主要是为手工计算而设计的，其主要作用就是为计算而计算，因而得出的圆周率公式非常复杂，除了专家们能够掌握使用外，普通人是知其然而不知所以然。所以旧的圆周率公式很不利于大众普及。
由于计算工具的快速发展，手工计算圆周率已成为历史。然而，圆周率公式依旧复杂，普通人即使利用计算器或计算机计算圆周率依然很不方便。
值得庆幸的是：中国的许多数学家和众多的业余数学爱好者们前赴后继，利用中国古代的割圆术思想与现代数学知识相结合，诞生了今天的中国圆周率公式，该公式正好弥补了圆周率的千古缺陷。
所以，中国圆周率公式现今的主要作用是：
1、简捷、全面、准确的描述圆周率及相关性质。
2、快速、方便、有趣的计算圆周率。
本回答被网友采纳
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
展开全部
第一类算法：arctan 的级数展开
PI/4 = 4 arctan(1/5) - arctan(1/239) (1)
arctan(x) = x - x3/3 + x5/5 - x7/7 + .... (2)
很容易想到，要得到超高精度的 PI 值，实数在计算机中必须以数组的形式进行存取，数组的大小跟所需的有效位数成正比。在这个算法中，PI 的有效位数 n 随 (2) 的求和项数线性增加。而为计算 (2) 中的每一项，需要进行超高精度实数除以小整数(52, 2392, 2k+1)的循环，循环所需次数也跟 n 成正比。所以，这个算法总的时间复杂度为 O(n2)。
这个算法的优点是简单，而且只需要进行整数运算。下面给出我写的算 PI 程序。在程序中，我采用了一些提高速度的措施：超高精度实数以数组的形式进行存取，数组元素的类型为 64 位整数(long long)，每个元素储存 12 个十进制位；对 xk (x = 1/5, 1/239) 的头部和尾部的 0 的数量进行估计，只对非 0 的部分进行计算。
pi.cpp C++ 源程序，在 Linux 下以 g++ pi.cpp -o pi -O2 编译
pi.s 在 g++ 生成的汇编程序的基础上进行修改，速度更快，在 Linux 下以 g++ pi.s -o pi 编译
另外，还有许多跟 (1) 类似的式子，但不常用。例如：
PI/4 = arctan(1/2) + arctan(1/3)
PI/4 = 8 arctan(1/10) - arctan(1/239) - 4 arctan(1/515)
第二类算法：与 1/PI 有关的级数
1/PI = (sqrt(8) / 9801) sumk=0~inf { [(4k)! (1103 + 26390k)] / [(k!)4 3964k] } (Ramanujan)
1/PI = (sqrt(10005) / 4270934400) sumk=0~inf { [(6k)! (13591409 + 545140134k)] / [(k!)3 (3k)! (-640320)3k] } (Chudnovsky)
以上两个级数(还有其它类似形式的级数，但不常用)比起 arctan 的泰勒级数要复杂得多。虽然仍然是线性收敛，总的时间复杂度也仍然是 O(n2)，但它们的收敛速度相当快， (Ramanujan) 每项可以增加 8 位有效数字， (Chudnovsky) 每项可以增加 14 位。
在这个算法中，除了要进行超高精度实数(数组形式)和小整数的运算外，还有一次超高精度实数的开方和倒数的运算，这需要用到 FFT(快速傅立叶变换)，在下文叙述。
第三类算法：算术几何平均值和迭代法
算术几何平均值(Arithmetic-Geometric Mean, AGM) M(a, b) 定义如下：
a0 = a, b0 = b
ak = (ak-1 + bk-1) / 2, bk = sqrt(ak-1 bk-1)
M(a, b) = limk->inf ak = limk->inf bk
然后，由椭圆积分的一系列理论(抱歉，过程我不懂)可以推导出如下公式：
a0 = 1, b0 = 1 / sqrt(2)
1/PI = { 1 - sumk=0~inf [2k (ak2 - bk2)] } / 2M(a0, b0)2 (AGM)
根据这条公式可以制定适当的迭代算法。在迭代过程中，有效位数随迭代次数按 2 的指数增加，即每迭代一次有效位数乘 2。算法中的超高精度实数的乘、除、开方等运算需要使用 FFT，在下文叙述。综合考虑 FFT 的时间复杂度，整个算法的时间复杂度约为 O(n log(n)2)。
除了 (AGM) 以外，还有其它的迭代序列，它们具有同样的时间复杂度。例如下面的这个序列将按 4 的指数收敛到 1/PI：
y0 = sqrt(2) - 1, a0 = 6 - 4 sqrt(2)
yk = [1 - sqrt(sqrt(1 - yk-14))] / [1 + sqrt(sqrt(1 - yk-14))], ak = (1 + yk)4 ak-1 - 22k+1 yk (1 + yk + yk2)
1/PI = limk->inf ak (Borwein)
FFT
如上所述，第二和第三类算法不可避免地要涉及超高精度实数(数组形式存取的多位数)的乘、除、开方等运算。多位数乘法如果按照常规方法来计算，逐位相乘然后相加，其时间复杂度将达到 O(n2)。使用 FFT 可大大减少计算量。
设有复数数组 a[k] 和 b[k] (k=0~n-1)，正向和反向的离散傅立叶变换(DFT)定义如下： (i = sqrt(-1))
b = FFTforward(a) : b[k] = sumj=0~n-1 ( a[j] e-i*j*2PI*k/n ) (3)
b = FFTbackward(a) : b[k] = (1/n) sumj=0~n-1 ( a[j] ei*j*2PI*k/n ) (4)
(3) 和 (4) 中的 (1/n) 可以放在任何一个式子中，也可以拆成 (1/sqrt(n)) 同时放在两个式子中，目的是保证正向和反向傅立叶变换以后不会相差一个因子。
当 n 的所有素因子均为小整数，尤其是当 n 为 2 的整数次幂的时候，使用适当的算法经过仔细的协调，可以避免多余的计算，使离散傅立叶变换 (3) 和 (4) 减少至 O(n log(n)) 的时间复杂度，即所谓的快速傅立叶变换(FFT)。具体的细节请查阅相关书籍。下面给出我写的一段 FFT 程序，仅供参考。另外也有已经开发的 FFT 函数库，例如 FFTW ，可以直接使用。
fft.cpp FFT 的 C++ 源程序
利用 FFT，要计算 n1 位和 n2 位的两个多位数乘法，可以这样进行：开辟两个长度为 n(n>=n1+n2，取 2m 最佳) 的复数数组，将两个多位数从低位到高位分别填入，高位补 0。对两个数组分别进行正向傅立叶变换。将得到的两个变换后的数组的对应项相乘，然后进行反向傅立叶变换，最后得到一个结果数组。由于傅立叶变换是在复数域中进行的，因此还要对结果数组进行取整和进位，才能得到最终的乘积。
值得留意的是傅立叶变换的精度问题。我们知道，在计算机中实数用单精度数或双精度数表示，它们会存在一定的误差。在计算多位数乘法时，n 往往是一个很大的数字，傅立叶变换过程中需要对数组的每一项进行求和，如何保证精度带来的误差不会因为求和而超出允许的范围？我的观点是必须使用双精度实数，而且由于统计特性，精度带来的误差在求和过程中不会很大，一般不会影响计算的正确性。如果需要保证计算的正确性，我想到两种检查方法。第一种是取模验算。例如，如果乘数和被乘数对 17 的模分别是 8 和 6，那么积对 17 的模就应该是 14。第二种是检查运算结果中浮点数偏离整数的最大值。如果偏差只有比如 10-3 量级，我们可以认为这个尺度的乘法运算很安全；如果偏差达到 0.5，说明运算已经出错了；如果偏差达到 0.1 量级，那也比较危险，也许换个别的乘数和被乘数就溢出了。
多位数的倒数和开方可以通过牛顿迭代求根法转化为乘法运算。例如，要计算 x = 1/a ，根据牛顿迭代法令 f(x) = 1/x - a ，可以得到以下迭代序列：
x0 ~= 1/a
xk = xk-1 - f(xk-1)/f'(xk-1) = 2xk-1 - axk-12 (5)
要计算 x = sqrt(a) ，可以先计算 x = 1 / sqrt(a) ，令 f(x) = 1/x2 - a ，可以得到以下迭代序列：
x0 ~= 1 / sqrt(a)
xk = xk-1 - f(xk-1)/f'(xk-1) = (3/2)xk-1 - (1/2)axk-13 (6)
(5) 和 (6) 均以 2 的指数收敛到所求结果。还存在其它更复杂一些的迭代序列，它们以更高的指数收敛，在此不提。不过需要提醒的是，跟 (AGM) 不同，这里 (5) 和 (6) 中的 x0 只是 1/a 和 1 / sqrt(a) 的约值，在前几次的迭代中不必进行满 n 位数的乘法运算，因而可以减少计算量。
示例程序
作为 AGM 和 FFT 算 PI 的完整过程演示，这里是我新写的算 PI 程序。很遗憾，我的程序比网上可以找到的其它算 PI 程序慢大约 100 倍，而且消耗更多的内存。:-( 目前还不清楚它的瓶颈所在。不管怎么说，它总算是我的第一个 AGM 和 FFT 算 PI 程序，祝贺！:-)
faint-pi-1.0.3.tar.gz C 源程序，在 Linux 下以 gcc -std=c99 *.c -o pi -lm -O3 编译
综述
以上介绍了三类算 PI 的算法。第一类算法的速度最慢，基本上已经过时。后两类算法的速度目前相差不大，最为常用。迭代法虽然在时间复杂度上有理论上的优势，但实现起来较为复杂，实际上也并不见得比 1/PI 级数法快。
PI/4 = 4 arctan(1/5) - arctan(1/239) (1)
arctan(x) = x - x3/3 + x5/5 - x7/7 + .... (2)
很容易想到，要得到超高精度的 PI 值，实数在计算机中必须以数组的形式进行存取，数组的大小跟所需的有效位数成正比。在这个算法中，PI 的有效位数 n 随 (2) 的求和项数线性增加。而为计算 (2) 中的每一项，需要进行超高精度实数除以小整数(52, 2392, 2k+1)的循环，循环所需次数也跟 n 成正比。所以，这个算法总的时间复杂度为 O(n2)。
这个算法的优点是简单，而且只需要进行整数运算。下面给出我写的算 PI 程序。在程序中，我采用了一些提高速度的措施：超高精度实数以数组的形式进行存取，数组元素的类型为 64 位整数(long long)，每个元素储存 12 个十进制位；对 xk (x = 1/5, 1/239) 的头部和尾部的 0 的数量进行估计，只对非 0 的部分进行计算。
pi.cpp C++ 源程序，在 Linux 下以 g++ pi.cpp -o pi -O2 编译
pi.s 在 g++ 生成的汇编程序的基础上进行修改，速度更快，在 Linux 下以 g++ pi.s -o pi 编译
另外，还有许多跟 (1) 类似的式子，但不常用。例如：
PI/4 = arctan(1/2) + arctan(1/3)
PI/4 = 8 arctan(1/10) - arctan(1/239) - 4 arctan(1/515)
第二类算法：与 1/PI 有关的级数
1/PI = (sqrt(8) / 9801) sumk=0~inf { [(4k)! (1103 + 26390k)] / [(k!)4 3964k] } (Ramanujan)
1/PI = (sqrt(10005) / 4270934400) sumk=0~inf { [(6k)! (13591409 + 545140134k)] / [(k!)3 (3k)! (-640320)3k] } (Chudnovsky)
以上两个级数(还有其它类似形式的级数，但不常用)比起 arctan 的泰勒级数要复杂得多。虽然仍然是线性收敛，总的时间复杂度也仍然是 O(n2)，但它们的收敛速度相当快， (Ramanujan) 每项可以增加 8 位有效数字， (Chudnovsky) 每项可以增加 14 位。
在这个算法中，除了要进行超高精度实数(数组形式)和小整数的运算外，还有一次超高精度实数的开方和倒数的运算，这需要用到 FFT(快速傅立叶变换)，在下文叙述。
第三类算法：算术几何平均值和迭代法
算术几何平均值(Arithmetic-Geometric Mean, AGM) M(a, b) 定义如下：
a0 = a, b0 = b
ak = (ak-1 + bk-1) / 2, bk = sqrt(ak-1 bk-1)
M(a, b) = limk->inf ak = limk->inf bk
然后，由椭圆积分的一系列理论(抱歉，过程我不懂)可以推导出如下公式：
a0 = 1, b0 = 1 / sqrt(2)
1/PI = { 1 - sumk=0~inf [2k (ak2 - bk2)] } / 2M(a0, b0)2 (AGM)
根据这条公式可以制定适当的迭代算法。在迭代过程中，有效位数随迭代次数按 2 的指数增加，即每迭代一次有效位数乘 2。算法中的超高精度实数的乘、除、开方等运算需要使用 FFT，在下文叙述。综合考虑 FFT 的时间复杂度，整个算法的时间复杂度约为 O(n log(n)2)。
除了 (AGM) 以外，还有其它的迭代序列，它们具有同样的时间复杂度。例如下面的这个序列将按 4 的指数收敛到 1/PI：
y0 = sqrt(2) - 1, a0 = 6 - 4 sqrt(2)
yk = [1 - sqrt(sqrt(1 - yk-14))] / [1 + sqrt(sqrt(1 - yk-14))], ak = (1 + yk)4 ak-1 - 22k+1 yk (1 + yk + yk2)
1/PI = limk->inf ak (Borwein)
FFT
如上所述，第二和第三类算法不可避免地要涉及超高精度实数(数组形式存取的多位数)的乘、除、开方等运算。多位数乘法如果按照常规方法来计算，逐位相乘然后相加，其时间复杂度将达到 O(n2)。使用 FFT 可大大减少计算量。
设有复数数组 a[k] 和 b[k] (k=0~n-1)，正向和反向的离散傅立叶变换(DFT)定义如下： (i = sqrt(-1))
b = FFTforward(a) : b[k] = sumj=0~n-1 ( a[j] e-i*j*2PI*k/n ) (3)
b = FFTbackward(a) : b[k] = (1/n) sumj=0~n-1 ( a[j] ei*j*2PI*k/n ) (4)
(3) 和 (4) 中的 (1/n) 可以放在任何一个式子中，也可以拆成 (1/sqrt(n)) 同时放在两个式子中，目的是保证正向和反向傅立叶变换以后不会相差一个因子。
当 n 的所有素因子均为小整数，尤其是当 n 为 2 的整数次幂的时候，使用适当的算法经过仔细的协调，可以避免多余的计算，使离散傅立叶变换 (3) 和 (4) 减少至 O(n log(n)) 的时间复杂度，即所谓的快速傅立叶变换(FFT)。具体的细节请查阅相关书籍。下面给出我写的一段 FFT 程序，仅供参考。另外也有已经开发的 FFT 函数库，例如 FFTW ，可以直接使用。
fft.cpp FFT 的 C++ 源程序
利用 FFT，要计算 n1 位和 n2 位的两个多位数乘法，可以这样进行：开辟两个长度为 n(n>=n1+n2，取 2m 最佳) 的复数数组，将两个多位数从低位到高位分别填入，高位补 0。对两个数组分别进行正向傅立叶变换。将得到的两个变换后的数组的对应项相乘，然后进行反向傅立叶变换，最后得到一个结果数组。由于傅立叶变换是在复数域中进行的，因此还要对结果数组进行取整和进位，才能得到最终的乘积。
值得留意的是傅立叶变换的精度问题。我们知道，在计算机中实数用单精度数或双精度数表示，它们会存在一定的误差。在计算多位数乘法时，n 往往是一个很大的数字，傅立叶变换过程中需要对数组的每一项进行求和，如何保证精度带来的误差不会因为求和而超出允许的范围？我的观点是必须使用双精度实数，而且由于统计特性，精度带来的误差在求和过程中不会很大，一般不会影响计算的正确性。如果需要保证计算的正确性，我想到两种检查方法。第一种是取模验算。例如，如果乘数和被乘数对 17 的模分别是 8 和 6，那么积对 17 的模就应该是 14。第二种是检查运算结果中浮点数偏离整数的最大值。如果偏差只有比如 10-3 量级，我们可以认为这个尺度的乘法运算很安全；如果偏差达到 0.5，说明运算已经出错了；如果偏差达到 0.1 量级，那也比较危险，也许换个别的乘数和被乘数就溢出了。
多位数的倒数和开方可以通过牛顿迭代求根法转化为乘法运算。例如，要计算 x = 1/a ，根据牛顿迭代法令 f(x) = 1/x - a ，可以得到以下迭代序列：
x0 ~= 1/a
xk = xk-1 - f(xk-1)/f'(xk-1) = 2xk-1 - axk-12 (5)
要计算 x = sqrt(a) ，可以先计算 x = 1 / sqrt(a) ，令 f(x) = 1/x2 - a ，可以得到以下迭代序列：
x0 ~= 1 / sqrt(a)
xk = xk-1 - f(xk-1)/f'(xk-1) = (3/2)xk-1 - (1/2)axk-13 (6)
(5) 和 (6) 均以 2 的指数收敛到所求结果。还存在其它更复杂一些的迭代序列，它们以更高的指数收敛，在此不提。不过需要提醒的是，跟 (AGM) 不同，这里 (5) 和 (6) 中的 x0 只是 1/a 和 1 / sqrt(a) 的约值，在前几次的迭代中不必进行满 n 位数的乘法运算，因而可以减少计算量。
示例程序
作为 AGM 和 FFT 算 PI 的完整过程演示，这里是我新写的算 PI 程序。很遗憾，我的程序比网上可以找到的其它算 PI 程序慢大约 100 倍，而且消耗更多的内存。:-( 目前还不清楚它的瓶颈所在。不管怎么说，它总算是我的第一个 AGM 和 FFT 算 PI 程序，祝贺！:-)
faint-pi-1.0.3.tar.gz C 源程序，在 Linux 下以 gcc -std=c99 *.c -o pi -lm -O3 编译
综述
以上介绍了三类算 PI 的算法。第一类算法的速度最慢，基本上已经过时。后两类算法的速度目前相差不大，最为常用。迭代法虽然在时间复杂度上有理论上的优势，但实现起来较为复杂，实际上也并不见得比 1/PI 级数法快。
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
