丘德诺夫斯基算法是一种高精度计算圆周率的方法,所用的快速收敛无穷级数由戴维·丘德诺夫斯基和格雷戈里·丘德诺夫斯基兄弟于1988年发现。每增加一项,计算精度就提高约14.18位十进制数字。结合二分拆分法和快速大整数运算,它成为超大规模圆周率计算的主要方法之一。这一名称既可以指其所依据的级数恒等式,也可以指基于该恒等式的高效计算过程。
级数
丘德诺夫斯基恒等式的一种标准形式为
π1=12k=0∑∞(3k)!(k!)36403203k+3/2(−1)k(6k)!(13591409+545140134k).
这里,k! 表示非负整数 k 的阶乘。一种更便于实现的等价形式为
π=S42688010005,
其中
S=k=0∑∞(3k)!(k!)36403203k(−1)k(6k)!(13591409+545140134k).
两种形式的等价性由下式可得:
126403203/2=42688010005.
S 的各项都是有理数。因此,可以用整数运算精确计算有限部分和;只有在求平方根和进行最后的除法时才需要近似计算。
只保留 k=0 的项,便得到
π≈1359140942688010005,
这一结果就已经与圆周率相符到小数点后约14位。
收敛性与误差
记
A=13591409,B=545140134,C=640320,
并令
tk=(3k)!(k!)3C3k(−1)k(6k)!(A+Bk).
相邻两项的比值为
tktk+1=−C3(k+1)324(6k+1)(2k+1)(6k+5)A+BkA+B(k+1).
当 k 趋于无穷大时,
tktk+1⟶−64032031728=−5336031.
因此,除去一个缓慢变化的因子,各项的衰减规律类似于公比绝对值极小的等比级数。每项带来的十进制精度增益渐近为
log10(533603)=3log10(53360)≈14.1816474627.
所以,若目标精度为 d 位十进制数字,所需项数的初步估计为
N≈14.1816474627d.
实际实现时,会增加项数或设置保护位,然后核验误差界,而不是将这一估计本身视为精度的证明。
各项正负交替,且绝对值递减。对于
SN=k=0∑N−1tk,
交错级数的余项满足
∣S−SN∣≤∣tN∣.
这给出了级数误差的界。要确认圆周率的哪些数位准确,还必须将该误差界传播到取倒数后的结果,并计入平方根计算及最后算术运算的误差。
数学渊源
丘德诺夫斯基级数属于计算 1/π 的拉马努金型公式族。这类公式将快速收敛级数与椭圆曲线、模函数以及与复乘有关的特殊值联系起来。
数值 640320 并不是任意选取的。它与下列特殊值有关:
j(21+−163)=−6403203,
其中 j 是模不变量。与判别式 −163 相关的特殊算术性质,使该级数具有异乎寻常的快速收敛性。
阶乘表达式还具有超几何函数结构。例如,
F(z)=k=0∑∞(3k)!(k!)3(6k)!zk
是一个超几何级数,而丘德诺夫斯基公式中的线性因子可以通过下式生成:
AF(z)+BzF′(z).
这里取的自变量值为 z=−1/6403203。其绝对值极小,从级数本身的角度解释了收敛为何如此迅速;而模函数恒等式则确立了它与 1/π 的精确联系。
高效求值
基于递推的求和
若对每一项都分别直接计算阶乘和幂,会产生大量重复运算。可以改用递推关系更新阶乘系数。
定义
ak=(3k)!(k!)3C3k(−1)k(6k)!.
则
且
ak+1=−akC3(k+1)324(6k+1)(2k+1)(6k+5).
级数便可写为
S=k=0∑∞ak(A+Bk).
这种方法简单直接,适合中等精度的计算。在极高精度下,反复以目标精度或接近目标精度进行运算,代价就会变得很高。
二分拆分法
**二分拆分法**将有限求和重组为一棵平衡树,树中的运算均为精确的整数乘法和加法。它避免了反复进行高精度除法,并使规模最大的运算能够采用高效乘法算法。
一种标准构造是令
D=246403203.
对于单个索引 k>0,定义
P(k,k+1)=(6k−5)(2k−1)(6k−1),
Q(k,k+1)=k3D,
T(k,k+1)=(−1)kP(k,k+1)(A+Bk).
对于 k=0,取
P(0,1)=Q(0,1)=1,T(0,1)=A.
合并相邻区间 [a,m) 和 [m,b) 时,计算
P(a,b)=P(a,m)P(m,b),
Q(a,b)=Q(a,m)Q(m,b),
T(a,b)=T(a,m)Q(m,b)+P(a,m)T(m,b).
在树的根节点处,
SN=Q(0,N)T(0,N),
因此
π≈T(0,N)42688010005Q(0,N).
所有 P、Q 和 T 的值都是整数。各棵子树相互独立,也为并行计算提供了机会。
精度与计算成本
普通的固定位数浮点运算无法支持任意多位数字。因此,实现时需要使用任意精度运算或按比例缩放的整数运算。
典型的高精度计算包括以下步骤:
- 根据收敛性估计选定项数。
- 用二分拆分法计算部分和。
- 以足够的精度计算 10005,通常使用牛顿法或整数平方根算法。
- 进行最后的乘法和除法。
- 在对结果进行舍入之前,计入截断误差和运算误差。
收敛速度快,并不意味着总计算成本仅与项数成正比。随着精度提高,每次大整数运算的成本也会增加。对于目标精度为 d 位十进制数字的计算,直接采用二分拆分法可能会产生位数达 O(dlogd) 比特的未约分中间整数。
采用快速乘法时,该算法具有准线性的位复杂度:忽略对数因子后,运行时间与所需精度成正比。具体的复杂度界取决于乘法算法、公因子的处理方式以及中间值的表示方式。大规模实现通常使用基于快速傅里叶变换或相关变换的乘法技术。
内存管理、并行调度、存储带宽,以及从二进制表示转换为十进制输出,也可能带来显著开销。因此,仅计算级数所需的时间,并不等于生成超长十进制展开的全部成本。
应用与局限
丘德诺夫斯基算法兼具快速收敛性,以及非常适合精确运算和二分拆分法的结构,因此被广泛用于大规模圆周率计算。这类计算也是对多精度软件、处理器、内存系统和长期运行的计算基础设施的严苛测试。
其主要局限在于适用范围和结果验证:
- 它计算的是圆周率从开头起的一段数字。 它不是数位提取方法,无法在不计算此前所需精度的情况下直接取得远处的某一位数字。
- 快速收敛并不能消除实现错误。 级数恒等式及其截断误差界本身,并不能验证某个具体程序、算术库或某次硬件运行的正确性。
- 正确舍入需要明确控制误差。 保护位虽然有用,但要得到经过验证的输出,误差界必须足够紧,能够据此确定最终的舍入值。
- 十进制数位不能证明圆周率的一般性质。 例如,无论计算规模多大,都不能证明圆周率是正规数,即所有有限数字串都以预期的极限频率出现。
其他高精度计算方法还包括基于算术—几何平均值的算法。它们的迭代次数和收敛模式与丘德诺夫斯基级数不同,因此,实际比较时必须考虑算术运算、内存使用及验证的全部成本,而不能只看迭代次数。