您能通过对二进制数的操作在无符号整数上命名这个平方根算法吗？
您能通过对二进制数的操作在无符号整数上命名这个平方根算法吗？
提问于 2016-09-29 05:42:04
显然，这个算法是众所周知的。
该算法将从最左边到最后一点一点地构建平方根答案。
假设为了简单起见，我们将支持8位无符号整数的平方运算。
让我们成为结果
设x是8位无符号整数
设n是结果中的第n位，其中第0位是最后一个位。
set res to 0
for nth bit from 3 down to 0
change the nth bit of the res to 1
if res * res > x then: <- The Comparison
restore the nth bit back to 0
return res返回结果将是一个4位无符号整数。
例如:查找4的平方根
(见图)
这可能是数字计算的数字吗:二进制数字系统(基数2)？Wiki链接
谢谢您抽时间见我!
回答 3
Software Engineering用户
发布于 2016-11-29 04:53:06
我可以称它为逐次近似，也可以称为二元搜索反演单调函数。
如果您能够执行一个函数f(x)，并且如果您知道f(x)在突出的x域中是严格单调的(严格递增或严格递减)，那么您可以通过这种二进制搜索将f(x)反演到您想要的任何有限精度。为您在结果中需要的每一点进行一次迭代。
Software Engineering用户
发布于 2016-09-29 23:42:32
是的，这基本上是您链接的文章中描述的算法。
主要的区别是你的伪码使用乘法，它的成本比可以做的要多，正如同一篇文章所指出的，“.计算e*e所需的运算可以用更快的位移位操作代替。”
“嗯，
Software Engineering用户
发布于 2016-11-29 01:35:16
简单地说，如果给出了X == Y^2 (sqrt(X) == Y的一个重新表示)，并且您想为整个算法的N值固定的k求解(N*N*X + m) == (N*Y + k)^2，那么您可以简单地从k = 0, 1, ..., N-1将值替换成k，并比较左手侧(固定的)和右手侧(这取决于替换到k的值)之间的大小。
对于N = 2，k的可能值是0, 1，因此它可以简化为二进制搜索。
页面原文内容由Software Engineering提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://softwareengineering.stackexchange.com/questions/332316
复制相关文章
相似问题
腾讯云开发者
