发现这个开平方挺快的

zeroieme

http://blog.csdn.net/shaily/archive/2008/12/11/3498283.aspx 原帖是整数算法，但公式也对实数适用。 实质是a_n、c_n的逼近。每逼进$1/2^n$，只需要调整a、b、c在 -n到-2n位的数值。所以是O（n Logn ） 比牛顿法大乘法更快。 问题是目前想不到并行优化方法。

liangbch

怀疑楼上没有仔细阅读那篇文章，你给出的复杂度公式O（n Logn ）中的n是被开方数，而不是被开放数的bit数。比如 欲对一个65536 bit的数求其平方根，由于其结果是32768bit，故需要需要计算32768次。 而牛顿迭代法，用查表法得到前4bit的结果后，再需要15-4=11次迭代就能够得到精确值。

zeroieme

2# liangbch 28次迭代=28*4次65536bit的大数乘法 这个是牛顿迭代法的瓶颈

liangbch

对于使用牛顿迭代法求平方根的倒数，因为每迭代一次，精度加倍。且每次计算的误差不累加，上一次迭代的误差不会影响到下次迭代。当应用牛顿迭代法是大数的平方根时，不需要每次计算都采用高精度，而是随着迭代次数的增加，需要保留的精度逐渐增加。 如计算结果需要一个有65536 bit 整数的平方根，其平方根只有32768 bits, step1 计算1/sqrt(a)的初始值x0，使用查表法，精度达到4比特 step2 第1次迭代，得到x1,精度达到8比特，计算过程需要精确到8比特 step3 第2次迭代，得到x2,精度达到16比特，计算过程需要精确到16比特 step4 第3次迭代，得到x3,精度达到32比特，计算过程需要精确到32比特 step5 第4次迭代，得到x4,精度达到64比特，计算过程需要精确到64比特 step6 第5次迭代，得到x5,精度达到128比特，计算过程需要精确到128比特 step7 第6次迭代，得到x6,精度达到256比特，计算过程需要精确到256比特 step8 第7次迭代，得到x7,精度达到512比特，计算过程需要精确到512比特 step9 第8次迭代，得到x8,精度达到1024比特，计算过程需要精确到1024比特 step10 第9次迭代，得到x9,精度达到2048比特，计算过程需要精确到2048比特 step11 第10次迭代，得到x10,精度达到4096比特，计算过程需要精确到4096比特 step12 第11次迭代，得到x11,精度达到8192比特，计算过程需要精确到8192比特 step13 第12次迭代，得到x12,精度达到16384比特，计算过程需要精确到16384比特 step14 第13次迭代，得到x13,精度达到32768比特，计算过程需要精确到32768比特 step15: 计算 x=a*x13,得到最终计算结果，精度须达到32768比特 在step2-step15，计算 x[n+1]= 3/2*x[n] + a/2 x[n]^3的过程中，每次迭代需要3次大数乘法，1次*1.5的单精度乘法，1次大数加法. 若大数乘法使用硬乘法，则step2-step13计算量大体等于1/3 倍的step14的计算量。故总共计算量等价于1(step2-13)+3(step14)+1(step15)=5次精度为32768比特的大数乘法。

liangbch

一个使用牛顿迭代法计算大数平方根的例子，请参照http://bbs.emath.ac.cn/viewthrea ... &fromuid=25#pid1160

zeroieme

变精度，这个要记下。 这里7次精度为32768比特的大数乘法。csdn那里不用乘法，只有加、移和判断。 这个也跟那个数据分支对CPU的影响有关吧。

liangbch

算法对效率的影响是根本性的，在问题的规模较大时，使用一个更好的算法常常能轻易的将速度提高100倍以上。我相信在计算10万比特以上整数的平方根时，牛顿迭代法定可比你那个平方根算法快百倍以上。 消除循环分支属于优化范畴。对程序性能的提高属于微调级的。通常的优化手段将程序提高30%以已属不宜。而将性能提高200%以上是极为罕见的。

liangbch

4#的计算有误（已更正），应该是5次精度为32768比特的大数乘法。

zeroieme

关于初始值x0 有个传奇故事 http://www.lomont.org/math/papers/2003/invsqrt.pdf

fulee

看不大明白，您说的65536是bit数还是数值？对65536位数用牛顿迭代法11次就可以开方么？

怀疑楼上没有仔细阅读那篇文章，你给出的复杂度公式O（n Logn ）中的n是被开方数，而不是被开放数的bit数。比如 欲对一个65536 bit的数求其平方根，由于其结果是32768bit，故需要需要计算32768次。 而牛顿迭代 ... liangbch 发表于 2011-4-5 16:53