How Can I Quickly Determine if a Large Integer is a Perfect Square Using Bitwise Operations?

Although the algorithm is about 35% faster than the code you gave, the actual results may vary between different CPUs (x86) and programming languages ​​(C/C). The method in this article is divided into three parts:

1. Filter obvious answers: include negative numbers, check the last 4 digits (found that checking the last 6 digits is not helpful), answer 0. (When reading the following code, please note that my input is an int64 The product of two different prime numbers, so the square modulo 255 only has a remainder of about 1/8. However, in my experience, the costs of using the modulo operator (%) outweigh the benefits, so I used a bit trick involving 255 to calculate the remainder. (Better or worse, I didn't use the trick of reading individual bytes from the word, just bitwise AND and shifting.)

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

I used a precomputed table to actually check if the remainder is square number.

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.

   Trying to calculate the square root using a method similar to Hensel's Lemma

   : Before this, I used two The search divides all remainders raised by powers of 2:

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

At this point, for our number to be a square number, its modulus must be 1 over 8.

3. The basic structure of Hensel’s lemma is as follows. (Note: untested code; if that doesn't work, try t=2 or 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;

   The idea is that on each iteration, you add one bit to r," The square root of (Note that if r is the square root of Power of .) Since our actual square root is less than 2^32, at that point we can actually check if r or t/2-r is the actual square root of x. In my actual code, I used the following modified loop:

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

   The speed gain here can be obtained in three ways: Precomputed starting value (equivalent to about 10 loop iterations ), exit the loop earlier, and skip some t values. For the last part, I observe z=r-x*x and use bit tricks to set t to the largest power of 2 divided by z. This allows me to skip those t values ​​that don't affect the r value anyway. My precomputed starting value picked out the "least positive" square root modulo 8192 in my case.

   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.

   Even if this code doesn't work for you any faster, I hope you enjoy some of the ideas. The complete test code is as follows, including precalculated tables.

   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) );

The above is the detailed content of How Can I Quickly Determine if a Large Integer is a Perfect Square Using Bitwise Operations?. For more information, please follow other related articles on the PHP Chinese website!