返回主页<-

----翻译自 Mathematical Constants and computation  的

Computation of inverse and square root in high precision

此页的.DOC版本

　用我们已学过的除法, 算N位数的倒数可以在 O(n²)的时间里完成. 实际上, 用快速乘法可以在 O(nlog(n)) 的时间里完成, 这就要用到 Newton 叠代法.它有一次叠代式、二次叠代式、三次…….它们都可以用作高精度快速计算.

1.2 多次叠代式

1.1  Newton's 叠代法

一个低精度的 x₀≈1/A 用 Newton's 叠代法变换函数 f(x) = 1/x-A, 得到近似序列.

xn+1 = xn- f(xn) f¢(xn) = 2xn-Axn2.     (*)

每算一次上式, 可比前次多几乎一倍的精度. 因此, 算 n 位 1/A 只要反复约 log_mn 次.

它的好处是只需进行乘法.

例如要计算 p 的倒数, 开始取近似值 x₀ = 0.31831 (5 位).前三次叠代:

x₁=2x₀-px₀² = 0.3183098861 (10 位)

x₂=2x₁-px₁² = 0.31830988618379067151 (20 位)

x₃=2x₂-px₂² = 0.3183098861837906715377675267450287240665 (40 位)

x₃ 前 38 位是正确的 1/p.

注意: 更好的二次叠代式如下:

h_n=1-Ax_n

x_n+1=x_n+x_nh_n

除法 B/A 可以转为算 1/A 乘以 B.

{程序(包含对大整数的操作)}

1.2 多次叠代式

 三次：

    由Newton 叠代法得

于是:　

h_n=1-Ax_n,   
x_n+1=x_n+x_n(h_n+h_n²)

例： 算π的倒数

x₀ = 0.31831 (5 位).

x₁=0.3183098861837906715(523...), (19 位正确)

x₂=0.3183098861837906715377675267450287240689...,(58 位正确)

x₃ 有 174 位正确.

四次叠代式:

h_n=1-Ax_n ,         

x_n+1=x_n+x_n(h_n+h_n²+h_n³).

五次叠代式:

h_n=1-Ax_n

x_n+1=x_n+x_n( h_n+h_n²+h_n³+h_n⁴) = x_n+x_n( 1+h_n²) ( h_n+h_n²)

r 次叠代式:

h_n=1-Ax_n

x_n+1=x_n+x_nP^r-1(h_n)

例:

P³(u)=u+u²+u³,

P⁴(u)=u+u²+u³+u⁴ = (1+u²)(u+u²),

P⁵(u)=u+u²+u³+u⁴+u⁵ = u+(1+u)(u²+u⁴),

P⁶(u)=u+u²+u³+u⁴+u⁵+u⁶ = (1+u²+u⁴)(u+u²),

P⁷(u)=u+u²+u³+u⁴+u⁵+u³+u⁶ = u+(1+u³)(u²+u³+u⁴),

...