ビット単位の演算を使用して、大きな整数が完全な平方であるかどうかをすばやく判断するにはどうすればよいですか?

アルゴリズムは指定したコードよりも約 35% 高速ですが、実際の結果は CPU (x86) やプログラミング言語 (C/C) によって異なる場合があります。この記事の方法は 3 つの部分に分かれています:

1. 明白な答えをフィルタリング: 負の数値を含め、最後の 4 桁をチェックします (最後の 6 桁をチェックすると判明しました)役に立ちません)、答えは 0 です。 (次のコードを読むとき、私の入力は 2 つの異なる素数の積である int64 であることに注意してください。そのため、255 を法とする平方の余りは約 1/8 しかありません。ただし、私の経験では、モジュロ演算子 (%) を使用するコストが利点を上回るため、255 を使用したちょっとしたトリックを使用して剰余を計算しました。 (良くも悪くも、単語から個々のバイトを読み取るトリックは使用せず、ビット単位の AND とシフトを実行するだけでした。)

   if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) )
       return false;
   if( x == 0 )
       return true;

事前計算されたテーブルを使用して、剰余が平方数であるかどうかを実際にチェックしました。 。

2. int64 y = x;
   y = (y & 4294967295LL) + (y >> 32); 
   y = (y & 65535) + (y >> 16);
   y = (y & 255) + ((y >> 8) & 255) + (y >> 16);
   // At this point, y is between 0 and 511.  More code can reduce it farther.

   ヘンゼルの補題に似た方法を使用して平方根を計算しようとしています

   : この前は、次の 2 つを使用しました。検索では、すべての剰余を 2 の累乗で除算します:

   if( bad255[y] )
       return false;
   // However, I just use a table of size 512

この時点で、数値が平方数であるためには、その係数が 8 の 1 でなければなりません。

3. ヘンゼルの補題の基本構造は次のとおりです。 (注: 未テストのコードです。うまくいかない場合は、t=2 または 8 を試してください。)

   if((x & 4294967295LL) == 0)
       x >>= 32;
   if((x & 65535) == 0)
       x >>= 16;
   if((x & 255) == 0)
       x >>= 8;
   if((x & 15) == 0)
       x >>= 4;
   if((x & 3) == 0)
       x >>= 2;

   考え方は、各反復で r に 1 ビットを追加するということです。」 (r が のべき乗の平方根であることに注意してください。) 実際の平方根は 2^32 より小さいため、その時点で、r または t/2-r が x の実際の平方根であるかどうかを実際に確認できます。実際のコードでは、次の変更されたループを使用しました:

   if((x & 7) != 1)
       return false;

   ここでの速度ゲインは 3 つの方法で取得できます: 事前に計算された開始値 (ループの約 10 回の反復に相当)、ループを早めに終了する、および一部の t 値をスキップします。最後の部分では、z=r-x*x を観察し、ビットトリックを使用して t を 2 を z で割った最大の累乗に設定します。これにより、r 値に影響を与えない t 値をスキップすることができます。私の場合、事前に計算された開始値は、8192 を法とする「最小の正」平方根を選択しました。

   int64 t = 4, r = 1;
   t <<= 1; r += ((x - r * r) & t) >> 1;
   t <<= 1; r += ((x - r * r) & t) >> 1;
   t <<= 1; r += ((x - r * r) & t) >> 1;
   // Repeat until t is 2^33 or so.  Use a loop if you want.

   たとえこのコードがすぐに機能しなかったとしても、いくつかのアイデアを楽しんでいただければ幸いです。事前計算されたテーブルを含む完全なテスト コードは次のとおりです。

   int64 r, t, z;
   r = start[(x >> 3) & 1023];
   do {
       z = x - r * r;
       if( z == 0 )
           return true;
       if( z < 0 )
           return false;
       t = z & (-z);
       r += (z & t) >> 1;
       if( r > (t >> 1) )
           r = t - r;
   } while( t <= (1LL << 33) );

以上がビット単位の演算を使用して、大きな整数が完全な平方であるかどうかをすばやく判断するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。