一般方法

级数展开

一般方法

很类似除法, 以求200的开平方为例

1 4. 1 4 2…… {以小数点为界, 每隔2位写一位得数, 注意加小数点}

√2`00. {以小数点为界, 每隔2位做一个标记（其实做不做没所谓）}

1 1 {算出不大于最右一组数的开平方的最大整数,写在标记左上方,

即 Int( sqrt(最右一组数) ), 并把这个整数的平方写下1}

100 {计算它们的差, 在右边添两个零}

24 96 {将刚才求得的一位数乘以20（即1*20）然后, 算出不大于差的x(20+x),

的x的最大整数 4 }

400 {计算它们的差, 在右边添两个零}

281 281 {将求得的数乘以20（即14*20）然后, 算出不大于差的x(280+x),

的x的最大整数 1 }

11900 {计算它们的差, 在右边添两个零}

2824 11296 {同上, 算出不大于差的x(141*20+x),的x的最大整数 4}

60400

28282 56564

3826

……

级数展开

1. 由代数式的变换

Sqrt(x)=a/b * 1/Sqrt[1-(xb2-a2)/(xb2)]

而1/sqrt(1-y) = 1+(1/2)y+(1*3)/(2*4)y2+(1*3*5)/(2*4*6)y3+…

a/b是Sqrt(x)的近似值.

例如Sqrt(2)≈239/169 , a=239,b=169 ,得

Sqrt(2) = (239/169)*1/Sqrt(1-1/57122)

2. 开N (正整数 次方)(x是被开方数)

(x)1/n=a/b * 1/[1-(xbn-an)/(xbn)]1/n

而1/(1-y)1/n = 1 + (1/n)y + (1*(n+1))/(n*2n)y2 + (1*(1+n)*(1+2n))/(n*2n*3n)y3+...

它的时间复杂度是 O(n2).

牛顿叠代法 (它是目前最快的算法, ∴这是同时是最重要的方法)

先求出1/sqrt(A)的近似值并赋给X, 反复运算下式

hn=1-Axn2

xn+1=xn+xn*hn/2

直到得到想要的精度(每算一次上式, 可比前次多差不多一倍的精度)

{也可以用X←X+X[4(1-AX2)+3(1-AX2)2]/8, 算一次, 可比前次多差不多2倍的精度}

最后X←AX 就得到Sqrt(A)

反复算的过程有许多地方可以优化:

While X<>0 do begin

Mul(X,X,Tmp);

Mul(Tmp,A,Tmp); {每次只取比X多一倍位数的A}

Tmp ← 1-Tmp; {for i=1 to size do tmp<-999…- tmp}

Mul(Tmp,X,Tmp);

Mul(Tmp,0.5,Tmp); {乘以0.5 比除以2快}

Add(X,Tmp,X); {X的前(size-1)部分几乎不用考虑}

End;

2.开N (正整数 次方)(A是被开方数)

X≈Exp(-Ln(A)/n); {X约等于A开N次方的倒数}

While X精度不够do

X ← X+X(1-AXn)/n; {算一次, 可比前次多差不多一倍的精度}

X←A*Xn-1 {得到A开N次方}