3

Imagine that we have e.g. 1000 bit word in our memory. I'm wondering if there is any way to calcuate a square root of it (not necessarily accurate, lets say without floating point part). Or we've got only memory location and later specified various size.

I assume that our large number is one array (most significant bits at the beginning?). Square root is more or less half of original number. When trying to use Digit-by-digit algorithm there is a point when usnigned long long is not enough to remember partial result (subtraction with 01 extended number). How to solve it? What with getting single digit of the large number? Only by bitmask?

While thinking about pseudocode stucked at this questions. Any ideas?

4

4 回答 4

1

使用二分搜索算法很容易计算平方根。

伪代码算法：

  • 猜一猜c：1000 位值除以 2（简单位移）。
  • 平方它：
    • 如果平方（几乎）等于你的 1000 位数，你就得到了答案
    • 如果平方小于你的数字，你可以确定根在c你的上限之间。
    • 如果平方大于您的数字，您就知道根位于您的下限和 之间c。
  • 重复直到找到你的根，同时跟踪你的上限和下限。

这种算法应该及时运行log (N)。

于 2014-04-06T12:59:21.843 回答
1

有点取决于你想要它的准确度。考虑 2^32 == 2^16 的平方根。因此，您可以做的一件事就是将 1000 位数字向右移动 500 位，您就会得到一个大概的答案。

这效果如何？让我们来看看。二进制数字 36 是 100100。如果我将它向右移动 3 位，那么我得到 4。嗯……应该是 6。33% 的相当大的错误。1,000,000 的平方根是 1,000。在二进制中，1,000,000 是1111 0100 0010 0100 0000. 那是20位。右移 10 位，即1111 0100 00，或 976。误差为 24/1000，即 2.4%。

当您达到 1,000 位数时，绝对误差可能很大，但百分比误差会非常小。

根据您存储数字的方式，将 1,000 位数字向右移动 500 位应该不会很困难。

于 2014-04-06T14:21:05.557 回答
1

你会怎么用手做呢？你将如何用手将 1000 位数字除以 500 位数字？（想想方法，显然会很耗时）。现在使用平方根，该方法非常类似于除法，您“猜测”第一个数字，然后是第二个数字，依此类推，然后减去。只是对于平方根，您减去稍微不同的东西（但没有那么不同，计算平方根可以以与除法非常相似的方式完成，除了每添加一个数字，除数就会改变）。

我不想告诉你具体怎么做，因为那会破坏你自己发现它的整个乐趣。

诀窍是：不要考虑 x 的平方根，而要考虑找到一个数 y，使得 y*y = x。当你改进 y 时，以最小的努力重新计算 x - y*y。

于 2014-04-06T12:54:30.163 回答
0

牛顿的方法可能是要走的路。在使用牛顿方法的某些时候，您将不得不执行除法（特别是在找到下一个要测试的点时），但可以将其近似为最接近的 2 次幂，然后进行位移。

于 2014-04-06T15:06:00.560 回答