发现这个开平方挺快的

zeroieme · 发表于 2011-4-3 12:12:23

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

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 · 发表于 2011-4-5 16:53:52

本帖最后由 liangbch 于 2011-4-6 12:14 编辑

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

zeroieme · 发表于 2011-4-5 22:47:29

2# liangbch

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

liangbch · 发表于 2011-4-6 15:36:39

本帖最后由 liangbch 于 2011-4-6 18:41 编辑

对于使用牛顿迭代法求平方根的倒数，因为每迭代一次，精度加倍。且每次计算的误差不累加，上一次迭代的误差不会影响到下次迭代。当应用牛顿迭代法是大数的平方根时，不需要每次计算都采用高精度，而是随着迭代次数的增加，需要保留的精度逐渐增加。
如计算结果需要一个有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 · 发表于 2011-4-6 15:38:07

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

zeroieme · 发表于 2011-4-6 17:06:42

变精度，这个要记下。

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

liangbch · 发表于 2011-4-6 18:34:44

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

liangbch · 发表于 2011-4-6 18:42:26

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

zeroieme · 发表于 2011-4-6 19:52:11

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

fulee · 发表于 2011-5-13 17:09:46

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

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

账号		自动登录	找回密码
密码			欢迎注册

[分享] 发现这个开平方挺快的

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。