用位移找到整数平方根的最快方法是什么? [英] What is the fastest way to find integer square root using bit shifts?

问题描述

我一直在寻找最快的方法来计算数字(整数)的平方根(整数).我在Wikipedia中遇到过这种解决方案，该解决方案可以找到一个数字的平方根(如果是一个完美的平方)或找到其最近的下一个完美正方形的平方根(如果给定的数字不是一个完美的平方:

I was looking for the fastest method to calculate the square root(integer) of a number(integer). I came across this solution in wikipedia which finds the square root of a number(if its a perfect square) or the square root of its nearest lower perfect square (if the given number is not a perfect square:

short isqrt(short num) {
    short res = 0;
    short bit = 1 << 14; // The second-to-top bit is set: 1L<<30 for long
    // "bit" starts at the highest power of four <= the argument.
    while (bit > num)
        bit >>= 2;
    while (bit != 0) {
        if (num >= res + bit) {
            num -= res + bit;
            res = (res >> 1) + bit;
        }
        else
            res >>= 1;
        bit >>= 2;
    }
    return res;
}

我尝试了很多测试运行以跟踪算法，但是我似乎不太了解while(bit!=0)中的部分.有人可以向我解释这部分吗?

I tried a lot of test runs to trace the algorithm but I do not seem to understand the portion inside while(bit!=0). Can anybody explain this part to me?

推荐答案

我也找到了一些小例子，我想我明白了.据我所知，该算法一次建立了一个二进制数的答案，从最高位到最低位.

I traced out a few small examples too, and I think I got it. As best as I understand it, the algorithm is building up the answer one binary digit at a time, from highest bit to lowest bit.

让"num_init"为函数开头的num值.假设在某个迭代中，我们有bit = 4 ^ x并且num等于某个值"num_curr"(快速浏览一下，直到bit为0时，它始终是4的幂).然后res的形式为y * 2 ^(x + 1)，其中y ^ 2 + num_curr = num_init，y小于实际答案，但在2 ^ x之内.

Let "num_init" be the value of num at the beginning of the function. Suppose at some iteration, we have that bit = 4^x and that num is equal to some value "num_curr" (a quick glance shows that until bit is 0, it is always a power of 4). Then res is of the form y*2^(x+1), where y^2 + num_curr = num_init, and y is less than the actual answer, but within 2^x.

num，res和bit的这个不变性将成为关键.在代码中完成此操作的方式是

This invariant on the values of num, res, and bit is going to be key. The way this is done in the code is that

while (bit != 0) {
    ....
}

正在将假想指针从左向右移动，并在每一步中确定该位是0还是1.

is moving our imaginary pointer left to right, and at each step we determine whether this bit is 0 or 1.

转到第一个if语句，假设我们假想的累积"整数等于y，我们在看2 ^ x位.然后，如果num的原始值至少为(y + 2 ^ x)^ 2 = y ^ 2 + y * 2 ^(x + 1)+ 4 ^ x，则该位为1.换句话说，如果num的值在该点至少为y * 2 ^(x + 1)+ 4 ^ x，则该位为1(因为我们具有num的值已经下降y ^ 2的不变性). .足够方便的是，res = y * 2 ^(x + 1)和bit = 4 ^ x.然后我们得到了要点

Going to the first if statement, suppose our imaginary "built-up" integer is equal to y, and we're looking at the 2^x bit. Then, the bit is 1 iff the original value of num is at least (y + 2^x)^2 = y^2 + y*2^(x+1) + 4^x. In other words, the bit is one if the value of num at that point is at least y*2^(x+1) + 4^x (since we have the invariant that the value of num has dropped by y^2). Conveniently enough, res = y*2^(x+1) and bit = 4^x. We then get the point behind

if (num >= res + bit) {
    num -= res + bit;
    res = (res >> 1) + bit;
}
else 
    res >>= 1;   

在必要时在我们的假想位置加一个1位，然后更新res和num以保持不变.最后

which adds a 1 bit at our imaginary spot if necessary, then updates res and num to keep the invariant. Lastly

bit >>= 2;

更新位并沿一步移动所有内容.

updates bit and moves everything along one step.

这篇关于用位移找到整数平方根的最快方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！