很类似除法,以求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}6040028282 565643826.......很类似除法,以求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}6040028282 565643826⒈由代数式的变换Sqrt(x)=ab * 1Sqrt[1-(xb2-a2)(xb2)]而1sqrt(1-y) = 1+(12)y+(1*3)(2*4)y2+(1*3*5)(2*4*6)y3+...ab是Sqrt(x)的近似值.例如Sqrt⑵≈239169,a=239,b=169,得Sqrt⑵= (239169)*1Sqrt(1-157122)⒉开N (正整数 次方)(x是被开方数)(x)1n=ab * 1[1-(xbn-an)(xbn)]1n而1(1-y)1n = 1 + (1n)y + (1*(n+1))(n*2n)y2 + (1*(1+n)*(1+2n))(n*2n*3n)y3+...它的时间复杂度是 O(n2).牛顿叠代法 (它是目前最快的算法,∴这是同时是最重要的方法)先求出1sqrt(A)的近似值并赋给X,反复运算下式hn=1-Axn2xn+1=xn+xn*hn2直到得到想要的精度(每算一次上式,可比前次多差不多一倍的精度){也可以用X←X+X[4(1-AX2)+3(1-AX2)2]8,算一次,可比前次多差不多2倍的精度}最后X←AX 就得到Sqrt(A)反复算的过程有许多地方可以优化:While X0 do beginMul(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;⒉开N (正整数 次方)(A是被开方数)X≈Exp(-Ln(A)n); {X约等于A开N次方的倒数}While X精度不够doX ← X+X(1-AXn)n; {算一次,可比前次多差不多一倍的精度}X←A*Xn-1 {得到A开N次方}