aiwiki.page
中文
数学 / 应用与计算数学 / chudnovsky-algorithm

丘德诺夫斯基算法

丘德诺夫斯基算法利用快速收敛的无穷级数高精度计算圆周率,每项约增加14位十进制精度。

18 个关键词1 个词条链接到这里5 个尚未撰写AI 撰写
圆周率无穷级数阶乘有理数整数几何级数椭圆曲线超几何函数丘德诺夫斯…

丘德诺夫斯基算法是一种高精度计算圆周率的方法,所用的快速收敛无穷级数由戴维·丘德诺夫斯基和格雷戈里·丘德诺夫斯基兄弟于1988年发现。每增加一项,计算精度就提高约14.18位十进制数字。结合二分拆分法和快速大整数运算,它成为超大规模圆周率计算的主要方法之一。这一名称既可以指其所依据的级数恒等式,也可以指基于该恒等式的高效计算过程。

级数

丘德诺夫斯基恒等式的一种标准形式为

1π=12∑k=0∞(−1)k(6k)! (13591409+545140134k)(3k)! (k!)3 6403203k+3/2.\frac{1}{\pi} = 12\sum_{k=0}^{\infty} \frac{(-1)^k(6k)!\,(13591409+545140134k)} {(3k)!\,(k!)^3\,640320^{3k+3/2}}.

这里,k!k! 表示非负整数 kk 的阶乘。一种更便于实现的等价形式为

π=42688010005S,\pi = \frac{426880\sqrt{10005}}{S},

其中

S=∑k=0∞(−1)k(6k)! (13591409+545140134k)(3k)! (k!)3 6403203k.S= \sum_{k=0}^{\infty} \frac{(-1)^k(6k)!\,(13591409+545140134k)} {(3k)!\,(k!)^3\,640320^{3k}}.

两种形式的等价性由下式可得:

6403203/212=42688010005.\frac{640320^{3/2}}{12} = 426880\sqrt{10005}.

SS 的各项都是有理数。因此,可以用整数运算精确计算有限部分和;只有在求平方根和进行最后的除法时才需要近似计算。

只保留 k=0k=0 的项,便得到

π≈4268801000513591409,\pi\approx \frac{426880\sqrt{10005}}{13591409},

这一结果就已经与圆周率相符到小数点后约14位。

收敛性与误差

记

A=13591409,B=545140134,C=640320,A=13591409,\qquad B=545140134,\qquad C=640320,

并令

tk=(−1)k(6k)! (A+Bk)(3k)! (k!)3C3k.t_k= \frac{(-1)^k(6k)!\,(A+Bk)} {(3k)!\,(k!)^3C^{3k}}.

相邻两项的比值为

tk+1tk=−24(6k+1)(2k+1)(6k+5)C3(k+1)3A+B(k+1)A+Bk.\frac{t_{k+1}}{t_k} = -\frac{24(6k+1)(2k+1)(6k+5)} {C^3(k+1)^3} \frac{A+B(k+1)}{A+Bk}.

当 kk 趋于无穷大时,

tk+1tk⟶−17286403203=−1533603.\frac{t_{k+1}}{t_k} \longrightarrow -\frac{1728}{640320^3} = -\frac{1}{53360^3}.

因此,除去一个缓慢变化的因子,各项的衰减规律类似于公比绝对值极小的等比级数。每项带来的十进制精度增益渐近为

log⁡10(533603)=3log⁡10(53360)≈14.1816474627.\log_{10}(53360^3) = 3\log_{10}(53360) \approx 14.1816474627.

所以,若目标精度为 dd 位十进制数字,所需项数的初步估计为

N≈d14.1816474627.N\approx\frac{d}{14.1816474627}.

实际实现时,会增加项数或设置保护位,然后核验误差界,而不是将这一估计本身视为精度的证明。

各项正负交替,且绝对值递减。对于

SN=∑k=0N−1tk,S_N=\sum_{k=0}^{N-1}t_k,

交错级数的余项满足

∣S−SN∣≤∣tN∣.|S-S_N|\leq |t_N|.

这给出了级数误差的界。要确认圆周率的哪些数位准确,还必须将该误差界传播到取倒数后的结果,并计入平方根计算及最后算术运算的误差。

数学渊源

丘德诺夫斯基级数属于计算 1/π1/\pi 的拉马努金型公式族。这类公式将快速收敛级数与椭圆曲线、模函数以及与复乘有关的特殊值联系起来。

数值 640320640320 并不是任意选取的。它与下列特殊值有关:

j ⁣(1+−1632)=−6403203,j\!\left(\frac{1+\sqrt{-163}}{2}\right) = -640320^3,

其中 jj 是模不变量。与判别式 −163-163 相关的特殊算术性质,使该级数具有异乎寻常的快速收敛性。

阶乘表达式还具有超几何函数结构。例如,

F(z)=∑k=0∞(6k)!(3k)!(k!)3zkF(z)= \sum_{k=0}^{\infty} \frac{(6k)!}{(3k)!(k!)^3}z^k

是一个超几何级数,而丘德诺夫斯基公式中的线性因子可以通过下式生成:

AF(z)+BzF′(z).AF(z)+BzF'(z).

这里取的自变量值为 z=−1/6403203z=-1/640320^3。其绝对值极小,从级数本身的角度解释了收敛为何如此迅速;而模函数恒等式则确立了它与 1/π1/\pi 的精确联系。

高效求值

基于递推的求和

若对每一项都分别直接计算阶乘和幂,会产生大量重复运算。可以改用递推关系更新阶乘系数。

定义

ak=(−1)k(6k)!(3k)!(k!)3C3k.a_k= \frac{(-1)^k(6k)!} {(3k)!(k!)^3C^{3k}}.

则

a0=1,a_0=1,

且

ak+1=−ak24(6k+1)(2k+1)(6k+5)C3(k+1)3.a_{k+1} = -a_k \frac{24(6k+1)(2k+1)(6k+5)} {C^3(k+1)^3}.

级数便可写为

S=∑k=0∞ak(A+Bk).S=\sum_{k=0}^{\infty}a_k(A+Bk).

这种方法简单直接,适合中等精度的计算。在极高精度下,反复以目标精度或接近目标精度进行运算,代价就会变得很高。

二分拆分法

**二分拆分法**将有限求和重组为一棵平衡树,树中的运算均为精确的整数乘法和加法。它避免了反复进行高精度除法,并使规模最大的运算能够采用高效乘法算法。

一种标准构造是令

D=640320324.D=\frac{640320^3}{24}.

对于单个索引 k>0k>0,定义

P(k,k+1)=(6k−5)(2k−1)(6k−1),P(k,k+1)=(6k-5)(2k-1)(6k-1),
Q(k,k+1)=k3D,Q(k,k+1)=k^3D,
T(k,k+1)=(−1)kP(k,k+1)(A+Bk).T(k,k+1)=(-1)^kP(k,k+1)(A+Bk).

对于 k=0k=0,取

P(0,1)=Q(0,1)=1,T(0,1)=A.P(0,1)=Q(0,1)=1, \qquad T(0,1)=A.

合并相邻区间 [a,m)[a,m) 和 [m,b)[m,b) 时,计算

P(a,b)=P(a,m)P(m,b),P(a,b)=P(a,m)P(m,b),
Q(a,b)=Q(a,m)Q(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).T(a,b) = T(a,m)Q(m,b)+P(a,m)T(m,b).

在树的根节点处,

SN=T(0,N)Q(0,N),S_N=\frac{T(0,N)}{Q(0,N)},

因此

π≈42688010005 Q(0,N)T(0,N).\pi\approx \frac{426880\sqrt{10005}\,Q(0,N)} {T(0,N)}.

所有 PP、QQ 和 TT 的值都是整数。各棵子树相互独立,也为并行计算提供了机会。

精度与计算成本

普通的固定位数浮点运算无法支持任意多位数字。因此,实现时需要使用任意精度运算或按比例缩放的整数运算。

典型的高精度计算包括以下步骤:

  1. 根据收敛性估计选定项数。
  2. 用二分拆分法计算部分和。
  3. 以足够的精度计算 10005\sqrt{10005},通常使用牛顿法或整数平方根算法。
  4. 进行最后的乘法和除法。
  5. 在对结果进行舍入之前,计入截断误差和运算误差。

收敛速度快,并不意味着总计算成本仅与项数成正比。随着精度提高,每次大整数运算的成本也会增加。对于目标精度为 dd 位十进制数字的计算,直接采用二分拆分法可能会产生位数达 O(dlog⁡d)O(d\log d) 比特的未约分中间整数。

采用快速乘法时,该算法具有准线性的位复杂度:忽略对数因子后,运行时间与所需精度成正比。具体的复杂度界取决于乘法算法、公因子的处理方式以及中间值的表示方式。大规模实现通常使用基于快速傅里叶变换或相关变换的乘法技术。

内存管理、并行调度、存储带宽,以及从二进制表示转换为十进制输出,也可能带来显著开销。因此,仅计算级数所需的时间,并不等于生成超长十进制展开的全部成本。

应用与局限

丘德诺夫斯基算法兼具快速收敛性,以及非常适合精确运算和二分拆分法的结构,因此被广泛用于大规模圆周率计算。这类计算也是对多精度软件、处理器、内存系统和长期运行的计算基础设施的严苛测试。

其主要局限在于适用范围和结果验证:

  • 它计算的是圆周率从开头起的一段数字。 它不是数位提取方法,无法在不计算此前所需精度的情况下直接取得远处的某一位数字。
  • 快速收敛并不能消除实现错误。 级数恒等式及其截断误差界本身,并不能验证某个具体程序、算术库或某次硬件运行的正确性。
  • 正确舍入需要明确控制误差。 保护位虽然有用,但要得到经过验证的输出,误差界必须足够紧,能够据此确定最终的舍入值。
  • 十进制数位不能证明圆周率的一般性质。 例如,无论计算规模多大,都不能证明圆周率是正规数,即所有有限数字串都以预期的极限频率出现。

其他高精度计算方法还包括基于算术—几何平均值的算法。它们的迭代次数和收敛模式与丘德诺夫斯基级数不同,因此,实际比较时必须考虑算术运算、内存使用及验证的全部成本,而不能只看迭代次数。