如果你想要速度，考虑到你的整数是有限的，我怀疑最快的方法是 （a） 按大小划分参数（例如，按最大位集划分类别），然后根据该范围内的完美平方数组检查值。

我在想我在数值分析课程中度过的可怕时光。

然后我记得，在《雷神之锤》源代码中，有这样一个函数围绕着“网络”盘旋：

float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;  // evil floating point bit level hacking
  i  = 0x5f3759df - ( i >> 1 ); // wtf?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

  #ifndef Q3_VM
  #ifdef __linux__
    assert( !isnan(y) ); // bk010122 - FPE?
  #endif
  #endif
  return y;
}

它基本上使用牛顿的近似函数（不记得确切的名称）计算平方根。

它应该是可用的，甚至可能更快，它来自非凡的 id 软件之一的游戏！

它是用 C++ 编写的，但一旦你有了这个想法，在 Java 中重用相同的技术应该不会太难：

我最初在以下位置找到它： https://web.archive.org/web/20110708173806/https://www.codemaestro.com/reviews/9

牛顿的方法在维基百科上解释：http://en.wikipedia.org/wiki/Newton%27s_method

您可以点击链接以获取有关其工作原理的更多解释，但如果您不太关心，那么这大致是我从阅读博客和参加数值分析课程中记住的内容：

• 基本上是一个快速转换为长整型函数，因此可以对原始字节应用整数运算。* (long*) &y
• 该线是近似函数的预先计算的种子值。0x5f3759df - (i >> 1);
• 将值转换回浮点数。* (float*) &i
• 该行基本上再次迭代函数的值。y = y * ( threehalfs - ( x2 * y * y ) )

近似函数给出的值越精确，您对结果迭代函数的次数越多。在 Quake 的案例中，一次迭代“足够好”，但如果它不适合你......然后，您可以根据需要添加任意数量的迭代。

这应该更快，因为它将朴素平方根中完成的除法运算次数减少到简单的除以 2（实际上是乘法运算），并用一些固定数量的乘法运算代替它。* 0.5F

如果你做一个二进制斩波来试图找到“正确”的平方根，你可以很容易地检测出你得到的值是否足够接近，可以判断：

(n+1)^2 = n^2 + 2n + 1
(n-1)^2 = n^2 - 2n + 1

所以经过计算，选项是：n^2

• n^2 = target：完成，返回 true
• n^2 + 2n + 1 > target > n^2：你很接近，但并不完美：返回 false
• n^2 - 2n + 1 < target < n^2：同上
• target < n^2 - 2n + 1：二进制斩波在较低n
• target > n^2 + 2n + 1：二进制斩波在更高的位置n

（对不起，这用作您当前的猜测，并用于参数。对于混乱，我们深表歉意！ntarget

我不知道这是否会更快，但值得一试。

编辑：二进制斩波也不必接受整个整数范围，所以一旦你在目标中找到了顶部设置位（这可以通过位旋转技巧来完成;我忘了具体是怎么回事）你可以快速获得一系列潜在的答案。请注意，幼稚的二进制斩波仍然只需要多达 31 或 32 次迭代。(2^x)^2 = 2^(2x)

我不确定它是否会更快，甚至更准确，但你可以使用约翰·卡马克的神奇平方根算法来更快地求解平方根。您可能可以很容易地针对所有可能的 32 位整数进行测试，并验证您实际上得到了正确的结果，因为它只是一个估计值。然而，现在我想起来，使用双打也是近似的，所以我不确定这将如何发挥作用。

不知道最快，但最简单的方法是以正常方式取平方根，将结果乘以自身，看看它是否与你的原始值匹配。

由于我们在这里谈论的是整数，因此禁食可能涉及一个集合，您可以在其中进行查找。

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

您的算法可能几乎是最佳的，但您可能需要在调用平方根例程之前进行快速检查以排除一些可能性。例如，通过按位执行“and”来查看十六进制数字的最后一位数字。完美的平方只能以 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# 代码影响不大。

使用牛顿方法计算整数平方根，然后对这个数字进行平方并检查应该要快得多，就像在当前解决方案中所做的那样。牛顿的方法是其他一些答案中提到的卡马克解的基础。你应该能够得到一个更快的答案，因为你只对根的整数部分感兴趣，这样你就可以更快地停止近似算法。

您可以尝试的另一个优化：如果数字的数字根不以 1、4、7 或 9 的数字不是一个完美的平方。这可以用作在应用较慢的平方根算法之前消除 60% 输入的快速方法。

如果速度是一个问题，为什么不将最常用的输入集及其值划分到查找表中，然后针对特殊情况使用您想出的任何优化的魔术算法呢？

我希望这个函数可以与所有 正 64 位有符号整数

Math.sqrt()使用双精度作为输入参数，因此对于大于 2^53 的整数，您将无法获得准确的结果。

有人指出，完美正方形的最后几位只能取某些值。一个数字的最后一位数字（以基数为单位）除以 ^d 时与余数相同，即。在 C 符号中。ddbnnbn % pow(b, d)

这可以推广到任何模量，即。 可用于排除一定比例的数字是完美正方形。您当前使用的模数是 64，允许 12，即。余数的 19%，作为可能的正方形。通过一些编码，我找到了模数 110880，它只允许 2016，即。1.8% 的余数作为可能的平方。因此，根据模数运算（即除法）和表查找与计算机上平方根的成本，使用此模数可能会更快。mn % m

顺便说一句，如果 Java 有办法为查找表存储打包的位数组，请不要使用它。110880 32 位字现在的 RAM 并不多，获取机器字将比获取单个比特更快。

为了记录，另一种方法是使用素数分解。如果分解的每个因子都是偶数，那么这个数字就是一个完美的平方。所以你想要的是看看一个数字是否可以分解为素数平方的乘积。当然，你不需要获得这样的分解，只是为了看看它是否存在。

首先构建一个低于 2^32 的素数平方表。这远远小于达到此限制的所有整数的表。

然后，解决方案是这样的：

boolean isPerfectSquare(long number)
{
    if (number < 0) return false;
    if (number < 2) return true;

    for (int i = 0; ; i++)
    {
        long square = squareTable[i];
        if (square > number) return false;
        while (number % square == 0)
        {
            number /= square;
        }
        if (number == 1) return true;
    }
}

我想这有点神秘。它的作用是在每一步检查质数的平方除以输入数。如果是这样，那么它会尽可能长时间地将数字除以平方，以将该正方形从素数分解中删除。 如果通过这个过程，我们得到 1，那么输入数是素数平方的分解。如果正方形变得比数字本身大，那么这个正方形或任何更大的正方形都无法将其整除，因此该数不可能是质数的平方的分解。

鉴于现在在硬件中完成的 sqrt 以及这里计算质数的需要，我想这个解决方案要慢得多。但它应该比使用 sqrt 的解决方案提供更好的结果，sqrt 在 2^54 上不起作用，正如 mrzl 在他的回答中所说。

为了性能，您经常需要做一些复杂的事情。其他人已经表达了各种方法，但是，您注意到 Carmack 的 hack 速度更快，达到某些 N 值。然后，您应该检查“n”，如果它小于该数字 N，请使用 Carmack 的 hack，否则使用此处答案中描述的其他方法。

您应该从一开始就摆脱 N 的 2 次方部分。

第二次编辑下面 m 的神奇表达式应该是

m = N - (N & (N-1));

而不是像写的那样

第二次编辑结束

m = N & (N-1); // the lawest bit of N
N /= m;
byte = N & 0x0F;
if ((m % 2) || (byte !=1 && byte !=9))
  return false;

第一次编辑：

小改进：

m = N & (N-1); // the lawest bit of N
N /= m;
if ((m % 2) || (N & 0x07 != 1))
  return false;

第一次编辑结束

现在像往常一样继续。这样，当你到达浮点部分时，你已经摆脱了所有 2 次方部分是奇数（大约一半）的数字，然后你只考虑剩下的 1/8。也就是说，您在 6% 的数字上运行浮点部分。

这是 Ruby 中旧的 Marchant 计算器算法（对不起，我没有参考）从十进制到二进制的返工，专门针对这个问题进行了改编：

def isexactsqrt(v)
    value = v.abs
    residue = value
    root = 0
    onebit = 1
    onebit <<= 8 while (onebit < residue)
    onebit >>= 2 while (onebit > residue)
    while (onebit > 0)
        x = root + onebit
        if (residue >= x) then
            residue -= x
            root = x + onebit
        end
        root >>= 1
        onebit >>= 2
    end
    return (residue == 0)
end

这是类似内容的检查（可能有编码风格/气味或笨拙的 O/O - 重要的是算法，而 C++ 不是我的母语）。在本例中，我们正在寻找残留物 == 0：

#include <iostream>  

using namespace std;  
typedef unsigned long long int llint;

class ISqrt {           // Integer Square Root
    llint value;        // Integer whose square root is required
    llint root;         // Result: floor(sqrt(value))
    llint residue;      // Result: value-root*root
    llint onebit, x;    // Working bit, working value

public:

    ISqrt(llint v = 2) {    // Constructor
        Root(v);            // Take the root 
    };

    llint Root(llint r) {   // Resets and calculates new square root
        value = r;          // Store input
        residue = value;    // Initialise for subtracting down
        root = 0;           // Clear root accumulator
        
        onebit = 1;                 // Calculate start value of counter
        onebit <<= (8*sizeof(llint)-2);         // Set up counter bit as greatest odd power of 2 
        while (onebit > residue) {onebit >>= 2; };  // Shift down until just < value
        
        while (onebit > 0) {
            x = root ^ onebit;          // Will check root+1bit (root bit corresponding to onebit is always zero)
            if (residue >= x) {         // Room to subtract?
                residue -= x;           // Yes - deduct from residue
                root = x + onebit;      // and step root
            };
            root >>= 1;
            onebit >>= 2;
        };
        return root;                    
    };
    llint Residue() {           // Returns residue from last calculation
        return residue;                 
    };
};

int main() {
    llint big, i, q, r, v, delta;
    big = 0; big = (big-1);         // Kludge for "big number"
    ISqrt b;                            // Make q sqrt generator
    for ( i = big; i > 0 ; i /= 7 ) {   // for several numbers
        q = b.Root(i);                  // Get the square root
        r = b.Residue();                // Get the residue
        v = q*q+r;                      // Recalc original value
        delta = v-i;                    // And diff, hopefully 0
        cout << i << ": " << q << " ++ " << r << " V: " << v << " Delta: " << delta << "\n";
    };
    return 0;
};

我想出了一种方法，它的工作速度比您的 6bits+Carmack+sqrt 代码快 ~35%，至少在我的 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. 最后，尝试使用类似于 Hensel 引理的方法计算平方根。（我不认为它直接适用，但它可以通过一些修改来工作。在此之前，我用二进制搜索除以 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;
   

   Hensel 引理的基本结构如下。（注意：未经测试的代码;如果它不起作用，请尝试 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 的“当前”平方根）上添加一位;每个平方根的精确模数越来越大，幂越来越大，即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 设置为 2 除以 z 的最大幂。这允许我跳过无论如何都不会影响 r 值的 t 值。在我的例子中，预先计算的起始值选出“最小正”平方根模 8192。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;
}

应该可以比这更有效地打包“如果最后 X 位数字是 N，则不能是完美的正方形”！我将使用 java 32 位整数，并生成足够的数据来检查数字的最后 16 位 - 即 2048 个十六进制整数值。

...

要么我遇到了一些超出我范围的数论，要么我的代码中有一个错误。无论如何，这里是代码：

public static void main(String[] args) {
    final int BITS = 16;

    BitSet foo = new BitSet();

    for(int i = 0; i< (1<<BITS); i++) {
        int sq = (i*i);
        sq = sq & ((1<<BITS)-1);
        foo.set(sq);
    }

    System.out.println("int[] mayBeASquare = {");

    for(int i = 0; i< 1<<(BITS-5); i++) {
        int kk = 0;
        for(int j = 0; j<32; j++) {
            if(foo.get((i << 5) | j)) {
                kk |= 1<<j;
            }
        }
        System.out.print("0x" + Integer.toHexString(kk) + ", ");
        if(i%8 == 7) System.out.println();
    }
    System.out.println("};");
}

结果如下：

（编辑：由于 Prettify.js 性能不佳而被省略;查看修订历史记录以查看。

关于 Carmac 方法，似乎再次迭代会很容易，这应该使精度的位数增加一倍。毕竟，这是一种极度截断的迭代方法--牛顿的迭代方法，具有非常好的初步猜测。

关于你目前的最佳状态，我看到了两个微优化：

• 使用 mod255 将检查与 0 之间的距离移动
• 重新排列四的除权范围，以跳过通常 （75%） 情况的所有检查。

即：

// Divide out powers of 4 using binary search

if((n & 0x3L) == 0) {
  n >>=2;

  if((n & 0xffffffffL) == 0)
    n >>= 32;
  if((n & 0xffffL) == 0)
      n >>= 16;
  if((n & 0xffL) == 0)
      n >>= 8;
  if((n & 0xfL) == 0)
      n >>= 4;
  if((n & 0x3L) == 0)
      n >>= 2;
}

更好的可能是一个简单的

while ((n & 0x03L) == 0) n >>= 2;

显然，知道每个检查点有多少数字被剔除会很有趣——我宁愿怀疑这些检查是否真正独立，这让事情变得棘手。

如前所述，sqrt 调用并不完全准确，但它在速度方面并没有吹走其他答案，这很有趣且很有启发性。毕竟，sqrt 的汇编语言指令序列很小。英特尔有一个硬件指令，我相信 Java 没有使用它，因为它不符合 IEEE。

那么为什么它很慢呢？因为 Java 实际上是通过 JNI 调用 C 例程，而且这样做实际上比调用 Java 子例程慢，而 Java 子例程本身比内联调用慢。这很烦人，Java 应该想出一个更好的解决方案，即在必要时构建浮点库调用。那好吧。

在 C++ 中，我怀疑所有复杂的替代方案都会降低速度，但我还没有全部检查它们。 我所做的，以及 Java 用户会发现有用的，是一个简单的 hack，是 A. Rex 建议的特例测试的扩展。使用单个长整型值作为位数组，该数组不进行边界检查。这样，您就有了 64 位布尔值查找。

typedef unsigned long long UVLONG
UVLONG pp1,pp2;

void init2() {
  for (int i = 0; i < 64; i++) {
    for (int j = 0; j < 64; j++)
      if (isPerfectSquare(i * 64 + j)) {
    pp1 |= (1 << j);
    pp2 |= (1 << i);
    break;
      }
   }
   cout << "pp1=" << pp1 << "," << pp2 << "\n";  
}


inline bool isPerfectSquare5(UVLONG x) {
  return pp1 & (1 << (x & 0x3F)) ? isPerfectSquare(x) : false;
}

例程是 PerfectSquare5 在我的 core2 duo 机器上运行的时间约为 1/3。我怀疑沿着相同的思路进一步调整可以平均进一步减少时间，但每次检查时，您都是在用更多的测试来换取更多的消除，所以你不能在这条路上走得太远。

当然，您可以以相同的方式检查高 6 位，而不是单独进行阴性测试。

请注意，我所做的只是消除可能的方块，但是当我有一个潜在的情况时，我必须将原始的内联称为 isPerfectSquare。

调用一次 init2 例程来初始化 pp1 和 pp2 的静态值。 请注意，在 C++ 的实现中，我使用的是 unsigned long long，因此由于您已签名，因此必须使用 >>> 运算符。

本质上不需要对数组进行边界检查，但 Java 的优化器必须很快弄清楚这些东西，所以我不会为此责怪他们。

标签中提到了欧拉项目，其中的许多问题都需要检查数字>>。当您使用 80 字节缓冲区时，上面提到的大多数优化都不容易工作。2^64

我使用了 java BigInteger 和 Newton 方法的略微修改版本，该方法更适合整数。问题在于精确的平方收敛到而不是因为，最终误差仅比最终除数低一步，算法终止。在计算错误之前，通过在原始参数中添加一个可以很容易地修复。（为立方体根等添加两个）n^2(n-1)nn^2-1 = (n-1)(n+1)

该算法的一个很好的属性是，您可以立即判断该数字是否为完美平方 - 牛顿方法中的最终误差（不是校正）将为零。简单的修改还可以让您快速计算，而不是最接近的整数。这对于几个欧拉问题很方便。floor(sqrt(x))

我喜欢对某些输入使用几乎正确的方法的想法。这是一个具有更高“偏移量”的版本。该代码似乎可以工作并通过我的简单测试用例。

只需替换您的：

if(n < 410881L){...}

用这个代码：

if (n < 11043908100L) {
    //John Carmack hack, converted to Java.
    // See: http://www.codemaestro.com/reviews/9
    int i;
    float x2, y;

    x2 = n * 0.5F;
    y = n;
    i = Float.floatToRawIntBits(y);
    //using the magic number from 
    //http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf
    //since it more accurate
    i = 0x5f375a86 - (i >> 1);
    y = Float.intBitsToFloat(i);
    y = y * (1.5F - (x2 * y * y));
    y = y * (1.5F - (x2 * y * y)); //Newton iteration, more accurate

    sqrt = Math.round(1.0F / y);
} else {
    //Carmack hack gives incorrect answer for n >= 11043908100.
    sqrt = (long) Math.sqrt(n);
}

“我正在寻找最快的方法来确定一个长值是否是一个完美的平方（即它的平方根是另一个整数）。

答案令人印象深刻，但我没有看到一个简单的检查：

检查右边的第一个数字是否为集合的成员（0,1,4,5,6,9）。如果不是，那么它就不可能是一个“完美的正方形”。

例如。

4567 - 不可能是一个完美的正方形。

这是我能想到的最快的 Java 实现，使用了此线程中其他人建议的技术组合。

• Mod-256测试
• 不精确的 mod-3465 测试（避免整数除法，但代价是一些误报）
• 浮点平方根，四舍五入并与输入值进行比较

我也尝试了这些修改，但它们对性能没有帮助：

• 额外的 mod-255 测试
• 将输入值除以 4 的幂
• 快速平方反比根（要处理高值的 N，它需要 3 次迭代，足以使其比硬件平方根函数慢。

public class SquareTester {

    public static boolean isPerfectSquare(long n) {
        if (n < 0) {
            return false;
        } else {
            switch ((byte) n) {
            case -128: case -127: case -124: case -119: case -112:
            case -111: case -103: case  -95: case  -92: case  -87:
            case  -79: case  -71: case  -64: case  -63: case  -60:
            case  -55: case  -47: case  -39: case  -31: case  -28:
            case  -23: case  -15: case   -7: case    0: case    1:
            case    4: case    9: case   16: case   17: case   25:
            case   33: case   36: case   41: case   49: case   57:
            case   64: case   65: case   68: case   73: case   81:
            case   89: case   97: case  100: case  105: case  113:
            case  121:
                long i = (n * INV3465) >>> 52;
                if (! good3465[(int) i]) {
                    return false;
                } else {
                    long r = round(Math.sqrt(n));
                    return r*r == n; 
                }
            default:
                return false;
            }
        }
    }

    private static int round(double x) {
        return (int) Double.doubleToRawLongBits(x + (double) (1L << 52));
    }

    /** 3465<sup>-1</sup> modulo 2<sup>64</sup> */
    private static final long INV3465 = 0x8ffed161732e78b9L;

    private static final boolean[] good3465 =
        new boolean[0x1000];

    static {
        for (int r = 0; r < 3465; ++ r) {
            int i = (int) ((r * r * INV3465) >>> 52);
            good3465[i] = good3465[i+1] = true;
        }
    }

}

考虑到一般的位长度（尽管我在这里使用了特定的类型），我尝试设计简单的算法，如下所示。最初需要简单明了地检查 0、1、2 或 <0。 从某种意义上说，以下内容很简单，因为它不会尝试使用任何现有的数学函数。大多数运算符可以替换为按位运算符。不过，我还没有用任何基准数据进行测试。我既不擅长数学，也不是计算机算法设计方面的专家，我很想看到你指出问题。我知道那里有很多改进的机会。

int main()
{
    unsigned int c1=0 ,c2 = 0;  
    unsigned int x = 0;  
    unsigned int p = 0;  
    int k1 = 0;  
    scanf("%d",&p);  
    if(p % 2 == 0) {  
        x = p/2; 
    }  
    else {  
        x = (p/2) +1;  
    }  
    while(x) 
    {
        if((x*x) > p) {  
            c1 = x;  
            x = x/2; 
        }else {  
            c2 = x;  
            break;  
        }  
    }  
    if((p%2) != 0)  
        c2++;

    while(c2 < c1) 
    {  
        if((c2 * c2 ) == p) {  
            k1 = 1;  
            break;  
        }  
        c2++; 
    }  
    if(k1)  
        printf("\n Perfect square for %d", c2);  
    else  
        printf("\n Not perfect but nearest to :%d :", c2);  
    return 0;  
}  

当观察到正方形的最后 n 位时，我检查了所有可能的结果。通过连续检查更多位，可以消除多达 5/6 的输入。实际上，我设计这个算法是为了实现费马的因式分解算法，而且速度非常快。

public static boolean isSquare(final long val) {
   if ((val & 2) == 2 || (val & 7) == 5) {
     return false;
   }
   if ((val & 11) == 8 || (val & 31) == 20) {
     return false;
   }

   if ((val & 47) == 32 || (val & 127) == 80) {
     return false;
   }

   if ((val & 191) == 128 || (val & 511) == 320) {
     return false;
   }

   // if((val & a == b) || (val & c == d){
   //   return false;
   // }

   if (!modSq[(int) (val % modSq.length)]) {
        return false;
   }

   final long root = (long) Math.sqrt(val);
   return root * root == val;
}

伪代码的最后一位可用于扩展测试以消除更多值。上面的测试是针对 k = 0、1、2、3

a 的形式为 （3 << 2k） - 1

b 的格式为 （2 << 2k）

c 的形式为 （2 << 2k + 2） - 1

d 的形式为 （2 << 2k - 1） * 10

它首先测试它是否具有模数为 2 的平方残差，然后根据最终模量进行测试，然后使用 Math.sqrt 进行最终测试。我从上面的帖子中提出了这个想法，并试图扩展它。我感谢任何意见或建议。

更新：使用模量 （modSq） 和模数基数 44352 的测试，我的测试在 OP 更新中 96% 的时间内运行，数字高达 1,000,000,000。

我对此线程中的几种算法进行了自己的分析，并得出了一些新结果。你可以在这个答案的编辑历史中看到这些旧结果，但它们并不准确，因为我犯了一个错误，浪费时间分析了几个不接近的算法。然而，从几个不同的答案中吸取教训，我现在有两种算法可以粉碎这个线程的“赢家”。这是我与其他人不同的核心做法：

// This is faster because a number is divisible by 2^4 or more only 6% of the time
// and more than that a vanishingly small percentage.
while((x & 0x3) == 0) x >>= 2;
// This is effectively the same as the switch-case statement used in the original
// answer. 
if((x & 0x7) != 1) return false;

然而，这行简单的行，大多数时候会添加一两个非常快速的指令，大大简化为一个 if 语句。但是，如果许多测试的数字具有显著的 2 次幂因子，则它可能会增加运行时。switch-case

算法如下：

• 互联网 - Kip 发布的答案
• Durron - 我修改后的答案，使用一次性答案作为基础
• DurronTwo - 我修改后的答案使用两遍答案（按 @JohnnyHeggheim），并进行了一些其他轻微的修改。

下面是一个示例运行时，如果数字是使用Math.abs(java.util.Random.nextLong())

 0% Scenario{vm=java, trial=0, benchmark=Internet} 39673.40 ns; ?=378.78 ns @ 3 trials
33% Scenario{vm=java, trial=0, benchmark=Durron} 37785.75 ns; ?=478.86 ns @ 10 trials
67% Scenario{vm=java, trial=0, benchmark=DurronTwo} 35978.10 ns; ?=734.10 ns @ 10 trials

benchmark   us linear runtime
 Internet 39.7 ==============================
   Durron 37.8 ============================
DurronTwo 36.0 ===========================

vm: java
trial: 0

下面是一个示例运行时，如果它仅在前一百万个多头上运行：

 0% Scenario{vm=java, trial=0, benchmark=Internet} 2933380.84 ns; ?=56939.84 ns @ 10 trials
33% Scenario{vm=java, trial=0, benchmark=Durron} 2243266.81 ns; ?=50537.62 ns @ 10 trials
67% Scenario{vm=java, trial=0, benchmark=DurronTwo} 3159227.68 ns; ?=10766.22 ns @ 3 trials

benchmark   ms linear runtime
 Internet 2.93 ===========================
   Durron 2.24 =====================
DurronTwo 3.16 ==============================

vm: java
trial: 0

正如你所看到的，对于大输入来说效果更好，因为它可以非常非常频繁地使用魔术，但与第一种算法相比，它被搞砸了，而且因为数字要小得多。同时，较简单的是一个巨大的赢家，因为它永远不必在前一百万个数字中多次除以 4。DurronTwoMath.sqrtDurron

这里是：Durron

public final static boolean isPerfectSquareDurron(long n) {
    if(n < 0) return false;
    if(n == 0) return true;

    long x = n;
    // This is faster because a number is divisible by 16 only 6% of the time
    // and more than that a vanishingly small percentage.
    while((x & 0x3) == 0) x >>= 2;
    // This is effectively the same as the switch-case statement used in the original
    // answer. 
    if((x & 0x7) == 1) {

        long sqrt;
        if(x < 410881L)
        {
            int i;
            float x2, y;

            x2 = x * 0.5F;
            y  = x;
            i  = Float.floatToRawIntBits(y);
            i  = 0x5f3759df - ( i >> 1 );
            y  = Float.intBitsToFloat(i);
            y  = y * ( 1.5F - ( x2 * y * y ) );

            sqrt = (long)(1.0F/y);
        } else {
            sqrt = (long) Math.sqrt(x);
        }
        return sqrt*sqrt == x;
    }
    return false;
}

和DurronTwo

public final static boolean isPerfectSquareDurronTwo(long n) {
    if(n < 0) return false;
    // Needed to prevent infinite loop
    if(n == 0) return true;

    long x = n;
    while((x & 0x3) == 0) x >>= 2;
    if((x & 0x7) == 1) {
        long sqrt;
        if (x < 41529141369L) {
            int i;
            float x2, y;

            x2 = x * 0.5F;
            y = x;
            i = Float.floatToRawIntBits(y);
            //using the magic number from 
            //http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf
            //since it more accurate
            i = 0x5f375a86 - (i >> 1);
            y = Float.intBitsToFloat(i);
            y = y * (1.5F - (x2 * y * y));
            y = y * (1.5F - (x2 * y * y)); //Newton iteration, more accurate
            sqrt = (long) ((1.0F/y) + 0.2);
        } else {
            //Carmack hack gives incorrect answer for n >= 41529141369.
            sqrt = (long) Math.sqrt(x);
        }
        return sqrt*sqrt == x;
    }
    return false;
}

还有我的基准测试安全带：（需要谷歌卡尺 0.1-rc5）

public class SquareRootBenchmark {
    public static class Benchmark1 extends SimpleBenchmark {
        private static final int ARRAY_SIZE = 10000;
        long[] trials = new long[ARRAY_SIZE];

        @Override
        protected void setUp() throws Exception {
            Random r = new Random();
            for (int i = 0; i < ARRAY_SIZE; i++) {
                trials[i] = Math.abs(r.nextLong());
            }
        }


        public int timeInternet(int reps) {
            int trues = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < ARRAY_SIZE; j++) {
                    if(SquareRootAlgs.isPerfectSquareInternet(trials[j])) trues++;
                }
            }

            return trues;   
        }

        public int timeDurron(int reps) {
            int trues = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < ARRAY_SIZE; j++) {
                    if(SquareRootAlgs.isPerfectSquareDurron(trials[j])) trues++;
                }
            }

            return trues;   
        }

        public int timeDurronTwo(int reps) {
            int trues = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < ARRAY_SIZE; j++) {
                    if(SquareRootAlgs.isPerfectSquareDurronTwo(trials[j])) trues++;
                }
            }

            return trues;   
        }
    }

    public static void main(String... args) {
        Runner.main(Benchmark1.class, args);
    }
}

更新：我制作了一种新算法，在某些情况下速度更快，在其他情况下速度较慢，我根据不同的输入得到了不同的基准测试。如果我们计算模，我们可以消除 97.82% 不能是平方的数。这可以（某种程度上）在一行中完成，有 5 个按位运算：0xFFFFFF = 3 x 3 x 5 x 7 x 13 x 17 x 241

if (!goodLookupSquares[(int) ((n & 0xFFFFFFl) + ((n >> 24) & 0xFFFFFFl) + (n >> 48))]) return false;

所得指标为1）残基，2）残基，或3）残基。当然，我们需要有一个残基模的查找表，它大约是一个 3mb 的文件（在这种情况下存储为 ascii 文本十进制数，不是最佳的，但显然可以通过 a 等改进。但既然这是预先计算，那就没那么重要了。您可以在此处找到该文件（或自行生成）：+ 0xFFFFFF+ 0x1FFFFFE0xFFFFFFByteBuffer

public final static boolean isPerfectSquareDurronThree(long n) {
    if(n < 0) return false;
    if(n == 0) return true;

    long x = n;
    while((x & 0x3) == 0) x >>= 2;
    if((x & 0x7) == 1) {
        if (!goodLookupSquares[(int) ((n & 0xFFFFFFl) + ((n >> 24) & 0xFFFFFFl) + (n >> 48))]) return false;
        long sqrt;
        if(x < 410881L)
        {
            int i;
            float x2, y;

            x2 = x * 0.5F;
            y  = x;
            i  = Float.floatToRawIntBits(y);
            i  = 0x5f3759df - ( i >> 1 );
            y  = Float.intBitsToFloat(i);
            y  = y * ( 1.5F - ( x2 * y * y ) );

            sqrt = (long)(1.0F/y);
        } else {
            sqrt = (long) Math.sqrt(x);
        }
        return sqrt*sqrt == x;
    }
    return false;
}

我把它加载到一个数组中，如下所示：boolean

private static boolean[] goodLookupSquares = null;

public static void initGoodLookupSquares() throws Exception {
    Scanner s = new Scanner(new File("24residues_squares.txt"));

    goodLookupSquares = new boolean[0x1FFFFFE];

    while(s.hasNextLine()) {
        int residue = Integer.valueOf(s.nextLine());
        goodLookupSquares[residue] = true;
        goodLookupSquares[residue + 0xFFFFFF] = true;
        goodLookupSquares[residue + 0x1FFFFFE] = true;
    }

    s.close();
}

示例运行时。在我运行的每个试验中，它都击败了（版本一）。Durron

 0% Scenario{vm=java, trial=0, benchmark=Internet} 40665.77 ns; ?=566.71 ns @ 10 trials
33% Scenario{vm=java, trial=0, benchmark=Durron} 38397.60 ns; ?=784.30 ns @ 10 trials
67% Scenario{vm=java, trial=0, benchmark=DurronThree} 36171.46 ns; ?=693.02 ns @ 10 trials

  benchmark   us linear runtime
   Internet 40.7 ==============================
     Durron 38.4 ============================
DurronThree 36.2 ==========================

vm: java
trial: 0

我来晚了，但我希望能提供更好的答案;更短，而且（假设我的基准是正确的）也快得多。

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 个项目的表，该表打包在一个 long 中，因此没有数组访问成本（间接和边界检查）。对于一个均匀随机的，有81.25%的概率在这里结束。long

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

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

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

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

整数问题需要整数解决方案。因此

对（非负）整数进行二叉搜索以找到最大的整数 t，使得 .然后测试是否准确。这需要时间 O（log n）。t**2 <= nr**2 = n

如果你不知道如何对正整数进行二值搜索，因为集合是无界的，这很容易。你首先计算你的递增函数 f（上图）的 2 的幂。当你看到它变成正数时，你就找到了上限。然后，您可以进行标准的二进制搜索。f(t) = t**2 - n

以下对 maaartinus 解决方案的简化似乎将运行时缩短了几个百分点，但我在基准测试方面还不够好，无法生成我可以信任的基准测试：

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;
    // Remove an even number of trailing zeros, leaving at most one.
    x >>= (Long.numberOfTrailingZeros(x) & (-2);
    // Repeat the test on the 6 least significant remaining bits.
    if (goodMask << x >= 0 | 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;
}

值得检查如何省略第一个测试，

if (goodMask << x >= 0) return false;

会影响性能。

这是最简单、最简洁的方法，虽然我不知道它在 CPU 周期方面如何比较。如果您只想知道根是否为整数，则效果很好。如果你真的在乎它是否是一个整数，你也可以弄清楚。下面是一个简单（且纯）的函数：

private static final MathContext precision = new MathContext(20);

private static final Function<Long, Boolean> isRootWhole = (n) -> {
    long digit = n % 10;
    if (digit == 2 || digit == 3 || digit == 7 || digit == 8) {
        return false;
    }
    return new BigDecimal(n).sqrt(precision).scale() == 0;
};

如果你不需要微优化，这个答案在简单性和可维护性方面更好。如果要计算负数，则需要相应地处理该数，并将绝对值发送到函数中。我做了一个小的优化，因为由于二次残差 mod 10，没有完美的正方形有 2、3、7 或 8 的十位数字。

在我的 CPU 上，在 0 - 10,000,000 上运行此算法平均每次计算需要 1000 - 1100 纳秒。

如果执行的计算次数较少，则较早的计算需要更长的时间。

我有一个负面评论，说我之前的编辑不适用于大量数字。OP 提到了 Longs，而 Long 的最大完美平方是 9223372030926249001，所以这种方法适用于所有 Longs。

不确定这是否是最快的方法，但这是我（很久以前在高中时）在数学课上无聊地玩计算器时偶然发现的。当时，我真的很惊讶这是有效的......

public static boolean isIntRoot(int number) {
    return isIntRootHelper(number, 1);
}

private static boolean isIntRootHelper(int number, int index) {
    if (number == index) {
        return true;
    }
    if (number < index) {
        return false;
    }
    else {
        return isIntRootHelper(number - 2 * index, index + 1);
    }
}

整数算术的牛顿方法

如果您希望避免非整数运算，可以使用以下方法。它基本上使用牛顿方法修改为整数算术。

/**
 * Test if the given number is a perfect square.
 * @param n Must be greater than 0 and less
 *    than Long.MAX_VALUE.
 * @return <code>true</code> if n is a perfect
 *    square, or <code>false</code> otherwise.
 */
public static boolean isSquare(long n)
{
    long x1 = n;
    long x2 = 1L;

    while (x1 > x2)
    {
        x1 = (x1 + x2) / 2L;
        x2 = n / x1;
    }

    return x1 == x2 && n % x1 == 0L;
}

此实现无法与使用 .但是，可以通过使用其他一些帖子中描述的过滤机制来提高其性能。Math.sqrt

用牛顿的方法计算平方根的速度快得可怕......前提是起始值是合理的。然而，没有合理的起始值，在实践中，我们以平分和 log（2^64） 行为结束。
为了真正快速，我们需要一种快速的方法来获得合理的起始值，这意味着我们需要下降到机器语言中。 如果处理器在奔腾中提供类似 POPCNT 的指令，则计算前导零，我们可以使用它来获得具有一半有效位的起始值。只要小心，我们可以找到固定数量的牛顿步长，这总是足够的。 （因此，无需循环并具有非常快速的执行速度。

第二种解决方案是通过浮点工具，它可能具有快速的sqrt计算（如i87协处理器）。即使是通过 exp（） 和 log（） 的偏移也可能比牛顿退化为二进制搜索更快。这有一个棘手的方面，即依赖于处理器的分析，分析之后是否需要改进。

第三种解决方案解决了一个略有不同的问题，但非常值得一提，因为问题中描述了这种情况。如果你想计算略有差异的数字的大量平方根，你可以使用牛顿迭代，如果你从不重新初始化起始值，而只是把它留在上一个计算中断的地方。我已经成功地在至少一个欧拉问题中使用了它。

这是一个分而治之的解决方案。

如果自然数 （） 的平方根是自然数 （），则可以根据 的位数轻松确定 的范围：numbersolutionsolutionnumber

• number有 1 位数字：在 = 1 - 4 范围内solution
• number有 2 位数字：范围 = 3 - 10solution
• number有 3 位数字：范围 = 10 - 40solution
• number有 4 位数字：范围 = 30 - 100solution
• number有 5 位数字：范围 = 100 - 400solution

注意到重复了吗？

您可以在二叉搜索方法中使用此范围来查看是否存在：solution

number == solution * solution

这是代码

这是我的类 SquareRootChecker

public class SquareRootChecker {

    private long number;
    private long initialLow;
    private long initialHigh;

    public SquareRootChecker(long number) {
        this.number = number;

        initialLow = 1;
        initialHigh = 4;
        if (Long.toString(number).length() % 2 == 0) {
            initialLow = 3;
            initialHigh = 10;
        }
        for (long i = 0; i < Long.toString(number).length() / 2; i++) {
            initialLow *= 10;
            initialHigh *= 10;
        }
        if (Long.toString(number).length() % 2 == 0) {
            initialLow /= 10;
            initialHigh /=10;
        }
    }

    public boolean checkSquareRoot() {
        return findSquareRoot(initialLow, initialHigh, number);
    }

    private boolean findSquareRoot(long low, long high, long number) {
        long check = low + (high - low) / 2;
        if (high >= low) {
            if (number == check * check) {
                return true;
            }
            else if (number < check * check) {
                high = check - 1;
                return findSquareRoot(low, high, number);
            }
            else  {
                low = check + 1;
                return findSquareRoot(low, high, number);
            }
        }
        return false;
    }

}

这里有一个关于如何使用它的示例。

long number =  1234567;
long square = number * number;
SquareRootChecker squareRootChecker = new SquareRootChecker(square);
System.out.println(square + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677489: true"

long notSquare = square + 1;
squareRootChecker = new SquareRootChecker(notSquare);
System.out.println(notSquare + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677490: false"

可能解决问题的最佳算法是快速整数平方根算法 https://stackoverflow.com/a/51585204/5191852

@Kde声称牛顿方法的三次迭代足以使 32 位整数的精度达到 ±1。当然，64 位整数需要更多的迭代，可能是 6 位或 7 位。

一个数字的平方根，假设该数字是一个完美的平方。

复杂度为 log（n）

/**
 * Calculate square root if the given number is a perfect square.
 * 
 * Approach: Sum of n odd numbers is equals to the square root of n*n, given 
 * that n is a perfect square.
 *
 * @param number
 * @return squareRoot
 */

public static int calculateSquareRoot(int number) {

    int sum=1;
    int count =1;
    int squareRoot=1;
    while(sum<number) {
        count+=2;
        sum+=count;
        squareRoot++;
    }
    return squareRoot;
}

static boolean isPerfectSquare (int input) {
  return Math.sqrt(input) == (int) Math.sqrt(input);
}

如果 的平方根的整数值等于双精度值，则返回此值。这意味着它是一个整数，它将返回 .否则，它将返回 .inputtruefalse

这个问题让我想知道，所以我做了一些简单的编码，我在这里展示它，因为我认为它很有趣，相关，但我不知道有多大用处。有一个简单的算法

a_n+1 = (a_n + x/a_n)/2

用于计算平方根，但它用于小数。我想知道如果我只是使用整数数学编码相同的算法会发生什么。它甚至会收敛到正确的答案吗？我不知道，所以我写了一个程序......

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <math.h>

_Bool isperfectsquare(uint64_t x, uint64_t *isqrtx) {
  // NOTE: isqrtx approximate for non-squares. (benchmarked at 162ns 3GHz i5)
  uint32_t i;
  uint64_t ai;
  ai = 1 + ((x & 0xffff000000000000) >> 32) + ((x & 0xffff00000000) >> 24) + ((x & 0xffff0000) >> 16);
  ai = (ai + x/ai)/2;
  ai = (ai + x/ai)/2;
  ai = (ai + x/ai)/2;
  ai = (ai + x/ai)/2;
  ai = (ai + x/ai)/2;
  ai = (ai + x/ai)/2;
  ai = (ai + x/ai)/2;
  ai = (ai + x/ai)/2;
  ai = (ai + x/ai)/2;
  ai = (ai + x/ai)/2;
  ai = (ai + x/ai)/2;
  ai = (ai + x/ai)/2;
  ai = ai & 0xffffffff;
  if (isqrtx != NULL) isqrtx[0] = ai;
  return ai*ai == x;
}

void main() {

  uint64_t x, isqrtx;
  uint64_t i;
  for (i=1; i<0x100000000; i++) {
    if (!isperfectsquare(i*i, &isqrtx)) {
      printf("Failed at %li", i);
      exit(1);
    }
  }
  printf("All OK.\n");
} 

因此，事实证明，公式的 12 次迭代足以为所有 64 位无符号多头给出正确的结果，这些多头都是完美的平方，当然，非平方将返回 false。

simon@simon-Inspiron-N5040:~$ time ./isqrt.bin 
All OK.

real    11m37.096s
user    11m35.053s
sys 0m0.272s

所以 697s/2^32 大约是 162ns。事实上，该函数对于所有输入将具有相同的运行时。讨论中其他地方详述的一些措施可以通过检查最后四位等来加快非平方的速度。希望有人像我一样觉得这很有趣。