我正在寻找确定一个值是否是完全平方的最快方法（即它的平方根是另一个整数）：long

1. 我已经通过使用内置
   函数以简单的方式完成了它，但我想知道是否有一种方法可以通过将自己限制为仅整数域来
   更快地做到这一点。Math.sqrt()
2. 维护查找表是不切实际的（因为大约有
   2^31.5 个整数的平方小于 2⁶³）。

这是我现在做的非常简单明了的方法：

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

  long tst = (long)(Math.sqrt(n) + 0.5);
  return tst*tst == n;
}

_{注意：我在许多欧拉项目问题中使用了这个函数。因此，没有其他人必须维护此代码。这种微优化实际上可能会有所作为，因为部分挑战是在不到一分钟的时间内完成每个算法，并且在某些问题中需要调用数百万次此函数。}

我已经尝试了这个问题的不同解决方案：

• 经过详尽的测试，我发现没有必要添加到 Math.sqrt（） 的结果中，至少在我的机器上不是这样。0.5
• 快速平方根反比更快，但它给出了 n >= 410881 的错误结果。但是，正如BobbyShaftoe所建议的那样，我们可以将FISR黑客用于n< 410881。
• 牛顿的方法比.这可能是因为使用了类似于牛顿方法的东西，但在硬件中实现，所以它比Java快得多。此外，牛顿方法仍然需要使用双精度。Math.sqrt()Math.sqrt()
• 修改后的牛顿方法使用了一些技巧，因此只涉及整数数学，需要一些技巧来避免溢出（我希望这个函数适用于所有正 64 位有符号整数），它仍然比 .Math.sqrt()
• 二进制斩击甚至更慢。这是有道理的，因为二进制斩章平均需要 16 次传递才能找到 64 位数字的平方根。
• 根据 John 的测试，使用 语句在C++ 中比使用 a 更快，但在 Java 和 C# 中，和 之间似乎没有区别。orswitchorswitch
• 我还尝试制作一个查找表（作为 64 个布尔值的私有静态数组）。然后，我只想说，而不是开关或语句。令我惊讶的是，这（只是稍微）慢了一点。这是因为数组边界是在 Java 中检查的。orif(lookup[(int)(n&0x3F)]) { test } else return false;

网友回答：

我参加聚会很晚了，但我希望能提供更好的答案;更短，（假设我的基准是正确的）也快得多。

long goodMask; // 0xC840C04048404040 computed below
{
    for (int i=0; i<64; ++i) goodMask |= Long.MIN_VALUE >>> (i*i);
}

public boolean isSquare(long x) {
    // This tests if the 6 least significant bits are right.
    // Moving the to be tested bit to the highest position saves us masking.
    if (goodMask << x >= 0) return false;
    final int numberOfTrailingZeros = Long.numberOfTrailingZeros(x);
    // Each square ends with an even number of zeros.
    if ((numberOfTrailingZeros & 1) != 0) return false;
    x >>= numberOfTrailingZeros;
    // Now x is either 0 or odd.
    // In binary each odd square ends with 001.
    // Postpone the sign test until now; handle zero in the branch.
    if ((x&7) != 1 | x <= 0) return x == 0;
    // Do it in the classical way.
    // The correctness is not trivial as the conversion from long to double is lossy!
    final long tst = (long) Math.sqrt(x);
    return tst * tst == x;
}

第一个测试可以快速捕获大多数非平方。它使用一个包含 64 项的表，因此没有数组访问成本（间接和边界检查）。对于均匀随机，有81.25%的概率在这里结束。long

第二个测试捕获所有在因式分解中具有奇数 86 的数字。该方法非常快，因为它被JIT转换为单个i<>指令。Long.numberOfTrailingZeros

删除尾随零后，第三个测试处理以二进制形式以 011、101 或 111 结尾的数字，这些数字不是完美的平方。它还关心负数，也处理 0。

最后的测试回到算术。由于只有 53 位尾数，
从 to 的转换包括大值的舍入。尽管如此，测试是正确的（除非证明是错误的）。doubledoublelongdouble

尝试合并mod255的想法并不成功。

网友回答：

我想出了一个比你的35bits+Carmack + sqrt代码快~6%的方法，至少在我的CPU（x86）和编程语言（C / C++）下是这样。你的结果可能会有所不同，特别是因为我不知道Java因素将如何发挥作用。

我的方法有三个方面：

1. 首先，过滤掉显而易见的答案。这包括负数和查看最后 4 位。（我发现看最后六个没有帮助。我也回答是 0。（在阅读下面的代码时，请注意我的输入是 .）int64 x

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

2. 接下来，检查它是否是平方模 255 = 3 * 5 * 17。因为这是三个不同素数的乘积，所以只有大约 1/8 的残基 mod 255 是正方形的。然而，根据我的经验，调用模运算符 （%） 的成本高于获得的好处，所以我使用涉及 255 = 2^8-1 的位技巧来计算残差。（无论好坏，我都没有使用从单词中读取单个字节的技巧，只是按位和移位。

   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;
   

   此时，要使我们的数字成为正方形，它必须是 1 mod 8。

   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 和 t/2-r 将是 x 模 t/2 的平方根。（请注意，如果 r 是 x 的平方根，那么 -r 也是如此。即使是模数也是正确的，但要注意，模化一些数字，事物甚至可以超过 2 个平方根;值得注意的是，这包括 2.） 的幂。因为我们的实际平方根小于 2^32，所以此时我们实际上可以检查 r 或 t/2-r 是否是实平方根。在我的实际代码中，我使用以下修改后的循环：

   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 值。对于最后一部分，我看了看 ，并用一些技巧将 t 设置为除以 z 的最大幂。这允许我跳过无论如何都不会影响 r 值的 t 值。在我的例子中，预先计算的起始值挑选出“最小正”平方根模 2。z = r - x * x

即使这段代码对你来说不能更快地工作，我也希望你喜欢它包含的一些想法。下面是经过测试的完整代码，包括预先计算的表。

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,
1343,445,937,1083,1617,883,185,1515,225,1443,1225,869,1423,1235,39,1973,
769,259,489,1797,1391,1485,1287,341,289,99,1271,1701,1713,915,537,1781,
1215,963,41,581,303,243,1337,1899,353,1245,329,1563,753,595,1113,1589,
897,1667,407,635,785,1971,135,43,417,1507,1929,731,207,275,1689,1397,
1087,1725,855,1851,1873,397,1607,1813,481,163,567,101,1167,45,1831,1205,
1025,1021,1303,1029,1135,1331,1017,427,545,1181,1033,933,1969,365,1255,1013,
959,317,1751,187,47,1037,455,1429,609,1571,1463,1765,1009,685,679,821,
1153,387,1897,1403,1041,691,1927,811,673,227,137,1499,49,1005,103,629,
831,1091,1449,1477,1967,1677,697,1045,737,1117,1737,667,911,1325,473,437,
1281,1795,1001,261,879,51,775,1195,801,1635,759,165,1871,1645,1049,245,
703,1597,553,955,209,1779,1849,661,865,291,841,997,1265,1965,1625,53,
1409,893,105,1925,1297,589,377,1579,929,1053,1655,1829,305,1811,1895,139,
575,189,343,709,1711,1139,1095,277,993,1699,55,1435,655,1491,1319,331,
1537,515,791,507,623,1229,1529,1963,1057,355,1545,603,1615,1171,743,523,
447,1219,1239,1723,465,499,57,107,1121,989,951,229,1521,851,167,715,
1665,1923,1687,1157,1553,1869,1415,1749,1185,1763,649,1061,561,531,409,907,
319,1469,1961,59,1455,141,1209,491,1249,419,1847,1893,399,211,985,1099,
1793,765,1513,1275,367,1587,263,1365,1313,925,247,1371,1359,109,1561,1291,
191,61,1065,1605,721,781,1735,875,1377,1827,1353,539,1777,429,1959,1483,
1921,643,617,389,1809,947,889,981,1441,483,1143,293,817,749,1383,1675,
63,1347,169,827,1199,1421,583,1259,1505,861,457,1125,143,1069,807,1867,
2047,2045,279,2043,111,307,2041,597,1569,1891,2039,1957,1103,1389,231,2037,
65,1341,727,837,977,2035,569,1643,1633,547,439,1307,2033,1709,345,1845,
1919,637,1175,379,2031,333,903,213,1697,797,1161,475,1073,2029,921,1653,
193,67,1623,1595,943,1395,1721,2027,1761,1955,1335,357,113,1747,1497,1461,
1791,771,2025,1285,145,973,249,171,1825,611,265,1189,847,1427,2023,1269,
321,1475,1577,69,1233,755,1223,1685,1889,733,1865,2021,1807,1107,1447,1077,
1663,1917,1129,1147,1775,1613,1401,555,1953,2019,631,1243,1329,787,871,885,
449,1213,681,1733,687,115,71,1301,2017,675,969,411,369,467,295,693,
1535,509,233,517,401,1843,1543,939,2015,669,1527,421,591,147,281,501,
577,195,215,699,1489,525,1081,917,1951,2013,73,1253,1551,173,857,309,
1407,899,663,1915,1519,1203,391,1323,1887,739,1673,2011,1585,493,1433,117,
705,1603,1111,965,431,1165,1863,533,1823,605,823,1179,625,813,2009,75,
1279,1789,1559,251,657,563,761,1707,1759,1949,777,347,335,1133,1511,267,
833,1085,2007,1467,1745,1805,711,149,1695,803,1719,485,1295,1453,935,459,
1151,381,1641,1413,1263,77,1913,2005,1631,541,119,1317,1841,1773,359,651,
961,323,1193,197,175,1651,441,235,1567,1885,1481,1947,881,2003,217,843,
1023,1027,745,1019,913,717,1031,1621,1503,867,1015,1115,79,1683,793,1035,
1089,1731,297,1861,2001,1011,1593,619,1439,477,585,283,1039,1363,1369,1227,
895,1661,151,645,1007,1357,121,1237,1375,1821,1911,549,1999,1043,1945,1419,
1217,957,599,571,81,371,1351,1003,1311,931,311,1381,1137,723,1575,1611,
767,253,1047,1787,1169,1997,1273,853,1247,413,1289,1883,177,403,999,1803,
1345,451,1495,1093,1839,269,199,1387,1183,1757,1207,1051,783,83,423,1995,
639,1155,1943,123,751,1459,1671,469,1119,995,393,219,1743,237,153,1909,
1473,1859,1705,1339,337,909,953,1771,1055,349,1993,613,1393,557,729,1717,
511,1533,1257,1541,1425,819,519,85,991,1693,503,1445,433,877,1305,1525,
1601,829,809,325,1583,1549,1991,1941,927,1059,1097,1819,527,1197,1881,1333,
383,125,361,891,495,179,633,299,863,285,1399,987,1487,1517,1639,1141,
1729,579,87,1989,593,1907,839,1557,799,1629,201,155,1649,1837,1063,949,
255,1283,535,773,1681,461,1785,683,735,1123,1801,677,689,1939,487,757,
1857,1987,983,443,1327,1267,313,1173,671,221,695,1509,271,1619,89,565,
127,1405,1431,1659,239,1101,1159,1067,607,1565,905,1755,1231,1299,665,373,
1985,701,1879,1221,849,627,1465,789,543,1187,1591,923,1905,979,1241,181};

bool bad255[512] =
{0,0,1,1,0,1,1,1,1,0,1,1,1,1,1,0,0,1,1,0,1,0,1,1,1,0,1,1,1,1,0,1,
 1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,0,1,1,1,
 0,1,0,1,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1,1,0,0,1,1,1,1,1,1,1,1,0,1,
 1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,1,1,0,1,1,1,1,0,0,1,1,1,1,1,1,
 1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,0,1,1,0,1,1,1,1,1,
 1,1,1,1,1,1,0,1,1,0,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,1,
 1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,
 1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,
 0,0,1,1,0,1,1,1,1,0,1,1,1,1,1,0,0,1,1,0,1,0,1,1,1,0,1,1,1,1,0,1,
 1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,0,1,1,1,
 0,1,0,1,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1,1,0,0,1,1,1,1,1,1,1,1,0,1,
 1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,1,1,0,1,1,1,1,0,0,1,1,1,1,1,1,
 1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,0,1,1,0,1,1,1,1,1,
 1,1,1,1,1,1,0,1,1,0,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,1,
 1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,
 1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,
 0,0};

inline bool square( int64 x ) {
    // Quickfail
    if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) )
        return false;
    if( x == 0 )
        return true;

    // Check mod 255 = 3 * 5 * 17, for fun
    int64 y = x;
    y = (y & 4294967295LL) + (y >> 32);
    y = (y & 65535) + (y >> 16);
    y = (y & 255) + ((y >> 8) & 255) + (y >> 16);
    if( bad255[y] )
        return false;

    // Divide out powers of 4 using binary search
    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;

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

    // Compute sqrt using something like Hensel's lemma
    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) );
    
    return false;
}

网友回答：

你必须做一些基准测试。最佳算法将取决于您输入的分布。

您的算法可能接近最佳，但您可能需要在调用平方根例程之前进行快速检查以排除一些可能性。例如，通过按位“和”查看十六进制数字的最后一位数字。完美平方只能以 0、1、4 或 9 结尾，以 16 为底，因此对于 75% 的输入（假设它们是均匀分布的），您可以避免调用平方根以换取一些非常快速的位摆动。

Kip 对以下实现十六进制技巧的代码进行了基准测试。在测试数字 1 到 100，000，000 时，此代码的运行速度是原始代码的两倍。

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

当我在C++中测试类似的代码时，它实际上比原始代码运行得慢。但是，当我删除 switch 语句时，十六进制技巧再次使代码速度提高了一倍。

int isPerfectSquare(int n)
{
    int h = n & 0xF;  // h is the last hex "digit"
    if (h > 9)
        return 0;
    // Use lazy evaluation to jump out of the if statement as soon as possible
    if (h != 2 && h != 3 && h != 5 && h != 6 && h != 7 && h != 8)
    {
        int t = (int) floor( sqrt((double) n) + 0.5 );
        return t*t == n;
    }
    return 0;
}

删除 switch 语句对 C# 代码几乎没有影响。