如何透過位元運算快速判斷一個大整數是否為完全平方數？

儘管演算法速度比你給的程式碼快35%左右，但不同CPU（x86）和程式語言（C/C ）的實際結果可能有所不同。本文的方法分為三個部分：

1. 過濾明顯答案：包括負數、檢查最後4位（發現檢查最後6位並無幫助）、回答0。 （在閱讀以下程式碼時，請注意我的輸入是int64 x。）

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

2. 檢查是否為模255平方數：因為255是三個不同質數的乘積，所以模255的平方只有大約1/8的餘數。然而，就我經驗而言，使用模運算子（％）的代價高於收益，因此我使用了涉及255的位元技巧來計算餘數。 （好壞參半，我沒有使用從字中讀取單個字節的技巧，只使用按位與和移位。）

   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.

   我用預先計算的表來實際檢查餘數是否為平方數。

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

3. 使用類似於亨瑟爾引理的方法嘗試計算平方根：在此之前，我使用二分搜尋將所有2的次方的餘數除盡：

   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;

   在這一點上，我們的數要成為平方數，它的模必須是8的1。

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

   亨瑟爾引理的基本結構如下。 （注意：未經測試的程式碼；如果不工作，請嘗試t=2或8。）

   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.

   思想是，在每次迭代中，你都將一位加到r，“目前」的x平方根；每個平方根都模一個越來越大的2的次冪，即t/2。 （注意，如果r是x的平方根，那麼-r也是。這在模數的情況下也是成立的，但要注意，模某些數，事情甚至可以有超過2個平方根；特別是，這包括2的次方。在我的實際程式碼中，我使用了以下修改後的循環：

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

   這裡的速度提升可以透過三種方式獲得：預先計算的起始值（相當於大約10次循環迭代）、更早退出循環、跳過一些t值。對於最後一部分，我觀察z=r-x*x，並使用位元技巧設定t為除以z的最大2的次方。這允許我跳過那些無論如何都不會影響r值的t值。我的預先計算起始值在我的情況下選出了模8192的「最小正」平方根。

即使本程式碼不會更快地為您工作，我希望您也能享受其中的一些想法。完整測試程式碼如下，包含預計算表。

typedef signed long long int int64;

int start[1024] =
{1,3,1769,5,1937,1741,7,1451,479,157,9,91,945,659,1817,11,
1983,707,1321,1211,1071,13,1479,405,415,1501,1609,741,15,339,1703,203,
129,1411,873,1669,17,1715,1145,1835,351,1251,887,1573,975,19,1127,395,
1855,1981,425,453,1105,653,327,21,287,93,713,1691,1935,301,551,587,
257,1277,23,763,1903,1075,1799,1877,223,1437,1783,859,1201,621,25,779,
1727,573,471,1979,815,1293,825,363,159,1315,183,27,241,941,601,971,
385,131,919,901,273,435,647,1493,95,29,1417,805,719,1261,1177,1163,
1599,835,1367,315,1361,1933,1977,747,31,1373,1079,1637,1679,1581,1753,1355,
513,1539,1815,1531,1647,205,505,1109,33,1379,521,1627,1457,1901,1767,1547,
1471,1853,1833,1349,559,1523,967,1131,97,35,1975,795,497,1875,1191,1739,
641,1149,1385,133,529,845,1657,725,161,1309,375,37,463,1555,615,1931,

以上是如何透過位元運算快速判斷一個大整數是否為完全平方數？的詳細內容。更多資訊請關注PHP中文網其他相關文章！