这个开方法速度怎么样

fulee

作者说任意大n位数开方，只需要加减运算n/2次，大牛看看速度怎么样？ 开方运算单元的高层次综合设计.pdf (57.13 KB, 下载次数: 20)

2011-5-13 17:37 上传

点击文件名下载附件

gxqcn

这个只适合小整数或小精度，因为结果每次迭代只新增1bit精度。

而大数开方，或高精度开方，比较高级的算法每次迭代，精度几乎可翻倍，效率更高。

fulee

谢谢。不过这样的话，是不是说开方运算，随着被开方数位数的增大，或者精度位数的提高，开方运算的效率越高？但是我以前所知道的都是，随着被开方数的位数增大，每位耗费计算机资源是呈位数的将近平方计算量增加的。
而文中的算法，计算量只是位数的线性关系，不是平方关系，为什么效率更低呢？

这个只适合小整数或小精度，因为结果每次迭代只新增1bit精度。

而大数开方，或高精度开方，比较高级的算法每次迭代，精度几乎可翻倍，效率更高。
gxqcn 发表于 2011-5-14 08:32

gxqcn

如果问阶乘算法的复杂度是多少？有人会回答：O(n)，因为 1*2*3*...*n 乘法次数随n的增大而线性增大。
果真如此乎？非也！因为大数计算与通常的int类型不同，它的每一步都隐含了一系列运算。

就拿楼主提供的资料来说，需要移位、比较、加减等大数运算，它们本身就是个 O(n) 级别的复杂度，
再需 n 次（或者说 n/2 次）循环，总体复杂度就是 O(n^2) 级别了。

而现在高精度的开方算法，复杂度是可以低于 O(n^2) 的。

fulee

恩我明白了，多谢多谢
想到一种加密方法，如果把一个长256位的数开方，取其第一段小数256位作为密钥流段，第二段小数256位化为整数后再次开方，再取其第一段小数256位作为密钥流段，第二段小数256位化为整数后再次开方，如此循环下去，产生无穷无尽的密钥流进行加密。这种加密容易破解么？
以上说256位，显然可以位数任意增加，例如增加到512位。由于每次开方的位数都是初始密钥长度，因此不存在开方精度无限提高导致的计算机资源耗费的问题。

如果问阶乘算法的复杂度是多少？有人会回答：O(n)，因为 1*2*3*...*n 乘法次数随n的增大而线性增大。
果真如此乎？非也！因为大数计算与通常的int类型不同，它的每一步都隐含了一系列运算。

就拿楼主提供的资料来 ...
gxqcn 发表于 2011-5-15 14:41