6

数値（整数）の平方根（整数）を計算する最速の方法を探していました。私はウィキペディアでこの解決策に出くわしました。これは、数値の平方根（完全な平方の場合）または最も近い下の完全な平方の平方根（指定された数値が完全な平方でない場合）を見つけます。

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)。誰かが私にこの部分を説明できますか？

4

1 に答える 1

3

私もいくつかの小さな例をたどりました、そして私はそれを手に入れたと思います。私が理解している限りでは、アルゴリズムは、最高ビットから最低ビットまで、一度に1桁ずつ答えを構築しています。

「num_init」を関数の先頭のnumの値とします。ある反復で、ビット= 4 ^ xがあり、numが値 "num_curr"に等しいとします（ビットが0になるまで、常に4の累乗であることが一目でわかります）。その場合、resはy * 2 ^（x + 1）の形式になります。ここで、y ^ 2 + num_curr = num_initであり、yは実際の答えよりも小さいですが、2^x以内です。

num、res、およびbitの値に対するこの不変条件が重要になります。これがコードで行われる方法は次のとおりです

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

は架空のポインタを左から右に移動し、各ステップでこのビットが0か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です。その後、ポイントを取得します

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

これは、必要に応じて架空のスポットに1ビットを追加し、resとnumを更新して不変を維持します。最後に

bit >>= 2;

ビットを更新し、すべてを1つのステップに沿って移動します。

于 2012-06-30T00:37:01.250 に答える