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

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

然后我记得，有这个函数在Quake源代码的网络周围盘旋：

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 hackingi  = 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#endifreturn y;}

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

它应该是可用的，甚至可能更快，它来自一个惊人的id软件的游戏！

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

我最初发现它在：http://www.codemaestro.com/reviews/9

牛顿方法解释于wikipedia：http://en.wikipedia.org/wiki/Newton%27s_method

你可以点击链接了解它是如何工作的，但如果你不太关心，那么这大致是我从阅读博客和参加数值分析课程中记得的：

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

在结果上迭代函数越多，近似函数给出的值就越精确。在Quake的情况下，一次迭代“足够好”，但如果不适合你……然后你可以根据需要添加尽可能多的迭代。

这应该更快，因为它减少了在朴素平方中执行的除法运算的数量，将其归结为简单的除以2（实际上是* 0.5F乘法运算），并将其替换为一些固定数量的乘法运算。

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

(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上的二进制印章

（对不起，这使用n作为您当前的猜测，使用target作为参数。为混淆道歉！）

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

编辑：二进制印章不一定要包含整数的整个范围，(2^x)^2 = 2^(2x)也是如此，所以一旦你找到了目标中的顶部设置位（这可以用一个有点玩弄的技巧来完成；我忘了具体是怎么做的），你可以很快得到一系列潜在的答案。请注意，一个天真的二进制印章仍然只需要31或32次迭代。

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

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

由于我们在这里讨论的是整数，所以Fasted可能涉及一个集合，您可以在其中进行查找。

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

您的算法可能接近最佳，但您可能希望在调用平方根例程之前进行快速检查以排除某些可能性。例如，通过按位执行“and”来查看十六进制数字的最后一位数字。完美的平方只能以16进制的0、1、4或9结尾，因此对于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 possibleif (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位只能取某些值。数字n的最后d位（在基数b中）与n除以b^#0时的余数相同，即。在C符号n % pow(b, d)中。

这可以推广到任何模m，即。n % m可用于排除某些百分比的数字是完美平方。你目前使用的模是64，这允许12，即19%的余数作为可能的平方。通过一点编码，我找到了模110880，它只允许2016，即。1.8%的余数作为可能的平方。因此，根据模操作（即除法）和表格查找的成本与机器上的平方根，使用这个模可能更快。

顺便说一句，如果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 NN /= m;byte = N & 0x0F;if ((m % 2) || (byte !=1 && byte !=9))return false;

第一次编辑：

小改进：

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

第一次编辑结束

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

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

def isexactsqrt(v)value = v.absresidue = valueroot = 0onebit = 1onebit <<= 8 while (onebit < residue)onebit >>= 2 while (onebit > residue)while (onebit > 0)x = root + onebitif (residue >= x) thenresidue -= xroot = x + onebitendroot >>= 1onebit >>= 2endreturn (residue == 0)end

这里有一个类似的检查（请不要因为编码风格/气味或笨重的O/O而否决我——重要的是算法，C++不是我的母语）。在这种情况下，我们要寻找残差==0：

#include <iostream>
using namespace std;typedef unsigned long long int llint;
class ISqrt {           // Integer Square Rootllint value;        // Integer whose square root is requiredllint root;         // Result: floor(sqrt(value))llint residue;      // Result: value-root*rootllint onebit, x;    // Working bit, working value
public:
ISqrt(llint v = 2) {    // ConstructorRoot(v);            // Take the root};
llint Root(llint r) {   // Resets and calculates new square rootvalue = r;          // Store inputresidue = value;    // Initialise for subtracting downroot = 0;           // Clear root accumulator
onebit = 1;                 // Calculate start value of counteronebit <<= (8*sizeof(llint)-2);         // Set up counter bit as greatest odd power of 2while (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 residueroot = x + onebit;      // and step root};root >>= 1;onebit >>= 2;};return root;};llint Residue() {           // Returns residue from last calculationreturn residue;};};
int main() {llint big, i, q, r, v, delta;big = 0; big = (big-1);         // Kludge for "big number"ISqrt b;                            // Make q sqrt generatorfor ( i = big; i > 0 ; i /= 7 ) {   // for several numbersq = b.Root(i);                  // Get the square rootr = b.Residue();                // Get the residuev = q*q+r;                      // Recalc original valuedelta = v-i;                    // And diff, hopefully 0cout << i << ": " << q << " ++ " << r << " V: " << v << " Delta: " << delta << "\n";};return 0;};

我找到了一种比你的6bit+Carmack+sqrt代码快35%的方法，至少用我的CPU（x86）和编程语言（C/C++）。你的结果可能会有所不同，尤其是因为我不知道Java因素将如何发挥作用。

我的方法有三个：

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=3*5*17。因为这是三个不同素数的乘积，只有大约1/8的残差模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;

   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的“当前”平方根；每个平方根都精确地模了越来越大的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值。对于最后一部分，我查看z = r - x * x，并使用一点技巧将t设置为2除以z的最大幂。这允许我跳过那些无论如何都不会影响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,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 ) {// Quickfailif( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) )return false;if( x == 0 )return true;
// Check mod 255 = 3 * 5 * 17, for funint64 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 searchif((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 lemmaint64 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位int，并产生足够的数据来检查数字的最后16位-即2048个十六进制int值。

…

好的。要么我遇到了一些超出我能力范围的数论，要么我的代码中有bug。无论如何，下面是代码：

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("};");}

以下是结果：

（ed：由于prettify.js表现不佳而省略；查看修订历史以查看。

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

关于你目前最好的，我看到两个微优化：

• 使用mod255在检查后移动检查与0
• 重新排列4的除法，跳过通常情况下（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应该想出更好的解决方案，即在必要时构建浮点库调用。哦，好吧。

在C++，我怀疑所有复杂的替代方案都会失去速度，但我还没有检查它们。我所做的，以及Java人会发现有用的，是一个简单的hack，A. Rex建议的特殊情况测试的扩展。使用单个long值作为位数组，不受边界检查。这样，你就有了64位布尔查找。

typedef unsigned long long UVLONGUVLONG 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;}

在我的core2二重奏机器上，这个例程是完美方块5运行的时间大约是1/3。我怀疑沿着同样的路线进一步调整可以平均进一步减少时间，但是每次你检查时，你都在用更多的测试来换取更多的消除，所以你不能在这条路上走得太远。

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

请注意，我所做的只是消除可能的方格，但是当我有一个潜在的情况下，我必须调用原始的，内联的是完美方格。

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

没有必要对数组进行边界检查，但Java的优化器必须很快解决这个问题，所以我不怪他们。

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

我使用了java BigInteger和牛顿方法的一个稍微修改的版本，它更适合整数。问题是精确的平方n^2收敛到(n-1)而不是n，因为n^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/9int 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 accuratei = 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);}

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

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

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

eg.

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

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);elseprintf("\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

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

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

然而，这一行简单的代码，大部分时间增加了一个或两个非常快速的指令，大大简化了switch-case语句为一个if语句。然而，如果许多测试数字具有显着的二次方因子，它可以添加到运行时。

下面的算法如下：

• 互联网-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 trials33% Scenario{vm=java, trial=0, benchmark=Durron} 37785.75 ns; ?=478.86 ns @ 10 trials67% Scenario{vm=java, trial=0, benchmark=DurronTwo} 35978.10 ns; ?=734.10 ns @ 10 trials
benchmark   us linear runtimeInternet 39.7 ==============================Durron 37.8 ============================DurronTwo 36.0 ===========================
vm: javatrial: 0

这是一个示例运行时，如果它仅在前一百万个long上运行：

 0% Scenario{vm=java, trial=0, benchmark=Internet} 2933380.84 ns; ?=56939.84 ns @ 10 trials33% Scenario{vm=java, trial=0, benchmark=Durron} 2243266.81 ns; ?=50537.62 ns @ 10 trials67% Scenario{vm=java, trial=0, benchmark=DurronTwo} 3159227.68 ns; ?=10766.22 ns @ 3 trials
benchmark   ms linear runtimeInternet 2.93 ===========================Durron 2.24 =====================DurronTwo 3.16 ==============================
vm: javatrial: 0

如你所见，DurronTwo在大输入方面做得更好，因为它经常使用魔术，但与第一个算法和Math.sqrt相比，它被击败了，因为数字要小得多。同时，更简单的Durron是一个巨大的赢家，因为它不必在第一个一百万个数字中多次除以4。

这里是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 loopif(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 accuratei = 0x5f375a86 - (i >> 1);y = Float.intBitsToFloat(i);y = y * (1.5F - (x2 * y * y));y = y * (1.5F - (x2 * y * y)); //Newton iteration, more accuratesqrt = (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;}

和我的基准线束：（需要Google卡尺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];
@Overrideprotected 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);}}

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

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

生成的索引是1）残数，2）残数+ 0xFFFFFF，或3）残数+ 0x1FFFFFE。当然，我们需要有一个残数模0xFFFFFF的查找表，它大约是一个3mb的文件（在这种情况下，存储为ascii文本十进制数，不是最佳的，但显然可以使用ByteBuffer等进行改进。但由于这是预计算，所以没那么重要。你可以在这里找到文件（或自己生成）：

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（版本1）。

 0% Scenario{vm=java, trial=0, benchmark=Internet} 40665.77 ns; ?=566.71 ns @ 10 trials33% Scenario{vm=java, trial=0, benchmark=Durron} 38397.60 ns; ?=784.30 ns @ 10 trials67% Scenario{vm=java, trial=0, benchmark=DurronThree} 36171.46 ns; ?=693.02 ns @ 10 trials
benchmark   us linear runtimeInternet 40.7 ==============================Durron 38.4 ============================DurronThree 36.2 ==========================
vm: javatrial: 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%的概率在这里结束。

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

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

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

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

一个整数问题需要一个整数解

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

如果你不知道如何二进制搜索正整数，因为集合是无界的，这很容易。你从计算2的幂上的递增函数f（高于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，没有完美的正方形有10位数的2、3、7或8。

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

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

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

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

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）行为结束。
为了真正快速，我们需要一种快速的方法来获得合理的起始值，这意味着我们需要下降到机器语言。如果处理器在Pentium中提供POPCNT这样的指令，它计算前导零，我们可以用它来获得一个具有一半有效位的起始值。小心地，我们可以找到一个固定数量的牛顿步，这总是足够的。（因此无需循环并具有非常快速的执行。）

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

第三种解决方案解决了一个略有不同的问题，但值得一提，因为问题中描述了这种情况。如果你想计算大量略有不同的数字的平方根，你可以使用牛顿迭代，如果你永远不会重新初始化起始值，而是将其保留在前一次计算结束的地方。我至少在一个欧拉问题中成功地使用了这一点。

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

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

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

注意到重复？

您可以在二分搜索方法中使用此范围来查看是否存在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);}

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

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

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.binAll OK.
real    11m37.096suser    11m35.053ssys 0m0.272s

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