5

この質問は、こちらの投稿のフォローアップです:整数の平方根が整数であるかどうかを判断する最速の方法、入力が完全な正方形であるかどうかを判断するための優れたアルゴリズムは何ですか? .

そこの投稿の1つに、特定の数値がaperfect squareかどうかを確認するための次の解決策がありました。

public final static boolean isPerfectSquare(long n)
    {
        if (n < 0)
            return false;

        switch((int)(n & 0xF))
        {
        case 0: case 1: case 4: case 9:
            long tst = (long)Math.sqrt(n);
            return tst*tst == n;

        default:
            return false;
        }
    }

これはきちんとした解決策であり、完全にうまく機能します。しかし、それがどのように機能するか、さらに重要なことに、このソリューションがどのように導出されるかについての説明は詳細に説明されていません. このソリューションがどのように導き出されているかを知りたいです。

4

2 に答える 2

3

この質問は直接プログラミングに関するものではありませんが、選択したソリューション メソッドに関連しています。そのため、正しい説明を投稿します。明らかに、これは- つまり、除算から 16 へのモジュロ (対応するビットが残るため。ただし、このトリックは 2 のべき乗でのみ機能します) とx & 0xF同等です。x % 16

この方法は、完全平方に関する非常に重要なことに基づいています。

整数をモジュロ(so ) でK任意の整数に分割する場合、K 2と r 2を で割ると同じモジュロになります。brK%b = rb

なんで？実際、次のようになります: K 2 -r 2 = (Kr)(K+r) であり、整数の結果K-rで に分割されます( は で除算されるモジュロであるため)brKb

それが理由ですb=16：

rr^2 (r^2)%16
0 ----> 0 ---> 0
1 ----> 1 ---> 1
2 --> 4 ---> 4
3 --> 9 ---> 9
4 ---> 16 ---> 0
5 ---> 25 ---> 9
6 ---> 36 ---> 4
7 ---> 49 ---> 1
8 ---> 64 ---> 0
9 ---> 81 ---> 1
10 --> 100 ---> 4
11 --> 121 ---> 9
12 --> 144 ---> 0
13 --> 169 ---> 9
14 --> 196 ---> 4
15 --> 225 ---> 1

したがって、ご覧rのとおり、 が完全平方の除算から導出される場合、モジュロは のモジュロと同じでなければなりません。r^2%16したがって、、、および 0149

もう1つ重要なこと：これは完全な2乗の必要条件であり、十分な条件ではありません（したがって、ポイントは「If modulo is NOT 0,1,4 or 9, then number is NOT perfect square」ですが、それでも「If modulo IS 0,1,4 または 9 の場合、数値は完全平方です17」17%16 = 1

リターン tst*tst == n;

n-つまり、平方根を計算することによって完全な平方であるかどうかをテストします。したがって、この方法は約 4 倍高速になります。なぜならr、12 に対して 16 の可能なモジュロから、常に を返すことができるからfalseです。

于 2014-02-25T08:16:56.507 に答える
2

n & 0xF0xFは1111バイナリであるため、n の最後の 4 ビットを選択するだけです。実際には、n を 16 で割った余りを取得するのと同じです。

mこのアルゴリズムは、完全な正方形の場合、m % 16は0、1、4またはのいずれかになるという事実を利用してい9ます。次のように証明できます。

任意の自然数は、 、、または(自然数 の場合)nとして表すことができます。4k4k+14k+24k+3k

次に、n^2、(4k)^2、(4k+1)^2または(4k+2)^2です(4k+3)^2。= > n^2、16k^2、16k^2+8k+1または。16k^2+16k+416k^2+24k+9

n^2である場合16k^2、n^2 % 16は明らかに 0 です。

n^2がの場合16k^2+8k+1、が偶数か奇数n^2 % 16 = (8k+1) % 16 = (8k % 16) + 1 = 0 or 9かによって異なります。k

n^2の場合16k^2+16k+4、n^2 % 16 = 4。

n^2がの場合16k^2+24k+9、n^2 % 16 = (24k+9) % 16 = (16k+8k+9) % 16 = 1 or 9k が奇数か偶数かによって異なります。

したがって、n^2 % 16できるのは のみです0,1, 4 or 9。

于 2014-02-25T08:11:35.003 に答える