最快的方式来确定，如果一个整数的平方根是一个整数
https://stackoverflow.com/questions/295579
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我在寻找最快的方式来确定，如果一个 long 值是一个完全平方(即它的平方根是另一个整数):
- 我已经做了简单的方法，通过使用建立在
Math.sqrt()功能，但我想知道，如果有一个方法可以做得更快的 限制自己整数仅域。 - 维持一个查询表是不切实际的(因为有关 231.5 整数，其方是少于263).
这里是非常简单和直接的方式我做它现在：
public final static boolean isPerfectSquare(long n)
{
if (n < 0)
return false;
long tst = (long)(Math.sqrt(n) + 0.5);
return tst*tst == n;
}
注：我使用这个功能在许多 欧拉项目 问题。所以没有人会以往任何时候都必须维持这个代码。这种微优化可能实际上使一个区别，因为部分挑战是做到的每一个算法在不到一分钟，该功能将需要进行所谓的数百万次，在一些问题。
我已经尝试了不同的解决问题的方案：
- 后详尽的测试，我发现，加入
0.5对结果的数学。sqrt()是不必要的，至少不在我的机器。 - 的 快速反平方根 快，但是它给了错误的结果对于n>=410881.然而，作为建议通过 BobbyShaftoe, 我们可以使用的FISR黑客n < 410881.
- 牛顿的方法是一个很好的位速度慢于
Math.sqrt().这可能是因为Math.sqrt()使用类似于牛顿的方法，但实现硬件，所以很快得多。此外，牛顿的方法，仍然需要使用的一倍。 - 修改的牛顿的方法，该方法使用一些技巧，因此，只有整数的数学是参与，需要一些黑客为了避免溢出(我希望这一功能对工作的所有积极的64位签署整数)，它仍然比较慢
Math.sqrt(). - 二进制砍甚至更慢。这使得有意义的，因为二进制砍会上平均需要16穿找到的平方根64位的数量。
- 根据约翰的试验，使用
or发言快在C++于使用switch, 但在爪哇和C#似乎没有差别or和switch. - 我也试着做一个查询表(作为一个私人静态阵列的64布尔值)。然后而不是开关或
or发言中，我只想说if(lookup[(int)(n&0x3F)]) { test } else return false;.我惊讶的是，这是(只是略)的速度较慢。这是因为 阵列边界检查Java.
解决方案
我想出了一个方法工作~35%的速度比你的6bits+卡马克+sqrt码，至少有我的CPU(86)和编程语言(C/C++)。你的结果可能会有所不同，特别是因为我不知道如何Java因素会发挥出来。
我的方法有三个方面：
- 第一，过滤出明显的答案。这包括负数，并寻找在最后4位。(我发现在过去六个没有帮助。) 我也回答是对于0.(在阅读了代码下面，请注意我输入
int64 x.)if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) ) return false; if( x == 0 ) return true; - 接着，检查，如果它是一个正方形的模255=3 * 5 * 17.因为这是一个产品的三个不同的素，只有大约1/8残mod255平方。然而，在我的经验，呼吁模操作员(%)的成本超过惠益一个得到，所以我用比的技巧涉及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 - 最后，试图计算的平方根采用类似的方法 汉森的理.(我觉得这不是直接适用，但它的工作与一些修改。) 在这样做之前，我把所有的权力2以二进制的搜索：
在这一点上，我们的号码是一方，它必须是1mod8.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;
基本结构的汉森的理如下。(注：未经测试的代码；如果它不起作用，尝试t=2或8。)if((x & 7) != 1) return false;
这个想法是，在每次迭代，添加一个位r到，"当前"的方根x；每平方根是准确的模较大和较大功率的2，即t/2。在结束时，r和t/2-r会平方根x模t/2。(注意，如果r平方根x，那么以为-r.这是真实的，即使是模的数字，但要注意，模一些数字，事情可能甚至已经超过2平方根;值得注意的是，这包括权力2。) 因为我们的实际平方根是少于2^32，在这一点上，我们可能实际上只是检查如果r或t/2-r是真正的平方根。在我的代码，我使用以下的修改：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.
加速这是获得在三个方面：预计算的起始值(相当于-10个迭代的循环)，较早退出的循环，并跳过一些t值。对最后一部分，我看看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) );z = r - x * x, 和设t是最大的电力为2分z一点伎俩。这使我要跳过t值不会受到影响的价值r无论如何。预计算的起始值在我的情况下挑选出"最小的积极"的平方根模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 ) {
// 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;
}其他提示
我非常迟到的缔约方，但我希望提供一个更好的答复;短和(假设我 基准 是正确的)还多 速度更快.
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.numberOfTrailingZeros 是很快的，因为它得到JIT ed入一个单一的i86指令。
之后删除尾随零，第三次测试的处理数字结束011,101,或111二，它是不完美的正方形。它还关心负数，也处理0.
最后的测试回落到 double 算。作为 double 只有53位尾数，
转换 long 要 double 包括四舍五入大价值。尽管如此，该试验是正确的(除非 证明 是错的).
试图纳入mod255的想法没有成功。
你必须做一些基准。最好的算法将取决于分配的投入。
你的算法可以几乎是最佳的，但是你可能想做个快速检查，以排除一些可能性之前呼唤你的平方根惯例。例如，看看这最后一位数字的数量在六角做的一位明智的"和"。 完美的方可以只在有0、1、4、9在基16，因为75%的输入(假定它们均匀地分布)就可以避免一个电话的平方根以交换对一些非常快点摆弄.
硖基准下列代码实现六角诀窍。在测试数字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++，它实际上跑慢于原来的。然而，当我消除了开关声明，六招的又一次使代码快两倍。
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;
}
消除关声明几乎没有影响C#代码。
我想这可怕的时候，我已经花了数值分析的课程。
然后我记得有这个功能的周围盘旋的净额从地震源代码:
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;
}
这基本上计算的平方根，使用牛顿的近似功能(不记得确切名称)。
它应该可以使用，甚至可能更快，这是一个惊人的身份软件是游戏！
这是用C++编写的，但应该不会太难以重复使用相同技术在Java一旦你的想法：
我最初找到它在： http://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 ) )行bascially重复的价值的功能。
近似的功能提供了更多的精确值越多，你迭代的功能的结果。在地震的情况下，一个迭代的"足够好的"，但如果不是因为你...然后你可以增加多次迭代，因为你需要。
这应该可以更快，因为它减少的数量划分的操作做幼稚方生根的下一个简单的划分2(实际上是一个 * 0.5F 乘法运作)，取而代之的是一个几个固定的数乘法运作，而不是。
我不确定如果它会更快，或者甚至是准确的，但是你能用 约翰*卡马克的神奇的平方根, 算法解决的平方根更快。你也许可以很容易地测试，这对于所有可能的32位整数和验证，你实际上得到了正确的结果，因为它是唯一一个appoximation.然而，现在，我想想，采用兼为接近，所以我不确定如何将发挥作用。
如果你不做二进制砍试图找到"正确"方根，你可以很容易检测值如果你已经有了足够近告诉：
(n+1)^2 = n^2 + 2n + 1
(n-1)^2 = n^2 - 2n + 1
因此，拥有计算 n^2, ，选项是：
n^2 = target:完成，真正的返回n^2 + 2n + 1 > target > n^2:你靠近，但它是不完美的：return falsen^2 - 2n + 1 < target < n^2:同上target < n^2 - 2n + 1:二进制砍一下ntarget > n^2 + 2n + 1:二进制砍在一个更高的n
(抱歉，这里使用 n 作为当前的猜测， target 的参数。道歉的混乱！)
我不知道这是否将会更快或不大，但它值得一试。
编辑：二进制的印章没有采取整个范围的整数， (2^x)^2 = 2^(2x), ，所以一旦你已经找到了顶点，在你的目标(它可以做一点-摆弄伎俩;我忘记了如何)可以迅速获得一系列可能的答案。记住你是一个天真的二进制砍仍然只占31 32次迭代。
我跑了我自己的分析的几个算法在这个线程，并提出了一些新的结果。你可以看到那些旧的结果在编辑历史的这个答案，但他们不准确的，因为我犯了一个错误，浪费时间来分析数的算法，它不是关闭。然而，拉的经验教训，从几个不同的答案，我现在有两种算法，粉碎"胜利者"的这个线程。这里的核心事我做不同于其他人：
// 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 发言到一个，如果声明。然而，它可以添加到运行时间如果许多测试的数字具有重要的两个因素。
算法如下如下：
- 互联网 -奇普是张贴的答案
- 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
正如你可以看到， 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 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);
}
}
更新： 我已经有了一个新的算法更快，在某些情况下，速度较慢的人，我已经得到了不同的基准的基础上不同的投入。如果我们计算模 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 (版本一个)在每一个审判我跑了。
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
我想这个功能工作的所有 正64位签署整数
Math.sqrt() 与加倍作为输入参数，这样你就不会获得准确的结果，对于整数大于 2^53.
只是为了记录在案，另一个办法是使用的理解。如果每个因素的分解，然后数是一个完美的正方形。所以你想要的是看到，如果一个号码可以分解成为一个产品方和总理的数字。当然，你不需要获得这样的分解，只是看到，如果它的存在。
第一个建立一个表格总理的数字均低于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不会的工作超过2^54，说mrzl在他的回答。
一个整数问题应该得到整数的解决方案。因此
做二进制上的搜索(非消极的)整数以找到的最大的整数t类， t**2 <= n.然后测试是否 r**2 = n 准确。这需要时间O(日志n)。
如果你不知道如何以二进制的搜索正整数，因为设定的是无限的，这很容易。你开始通过计算增加功能f(上 f(t) = t**2 - n)在权力的两个。当你看到它变成积极的，你已经找到一个上限。然后你可以做二进制的标准搜索。
它已经指出，最后一个 d 数字的一个完美的广场上只能采取的某些价值观。最后一个 d 数字(在基 b)的数量 n 相同的其余部分的时候 n 除 bd, ，即。在C符号 n % pow(b, d).
这个可以推广到任何模 m, ，即。 n % m 可以用来排除一些百分比数字从被完美的正方形。模您目前使用的是64，它允许12,ie。19%的余，尽可能广场。有一个小小的编码我发现的模110880，只允许2016年，ie。1.8%的余，尽可能广场。因此，根据成本的模的操作(ie。司)和一个表中查找和平方根你的机器上，使用这个模可能更快。
顺便说一句，如果Java有一种方式储存装列位于查表，不要使用它。110880 32位字不多RAM这些天和获取一个字机会速度快于获取一个单位。
对性能，你经常做一些compromsies.其他人已经表达的各种方法，但是，你注意到卡马克的黑客很快达到一定的价值观。然后，你应该检查"n"并且如果低于这个数字N，使用卡马克的哈克,别使用一些其他的方法描述的答案在这里。
这是最快的Java实施我能想出，使用组合技术建议由其他人在这个线程。
- 国防部-256测试
- 不精确的国防部-3465测试(可以避免整数部门的成本的一些误报)
- 浮点的平方根和比较用的输入值
我还试验了这些修改，但他们并没有帮助性能：
- 额外的国防部-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;
}
}
}
下面简化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;
会影响性能。
你应该摆脱的2-电力的一部分N从一开始。
第2个编辑 神奇的表达对米以下应该是
m = N - (N & (N-1));
和不作为编写
结束的第2个编辑
m = N & (N-1); // the lawest bit of N
N /= m;
byte = N & 0x0F;
if ((m % 2) || (byte !=1 && byte !=9))
return false;
第1编辑：
轻微的改善：
m = N & (N-1); // the lawest bit of N
N /= m;
if ((m % 2) || (N & 0x07 != 1))
return false;
结束第1编辑
现在继续如往常一样。这样，到时候你得到的浮点的一部分，你已经摆脱了所有数字的2-电力部分是奇数(大约一半)，然后你只考虑的1/8，什么离开。I.e。你浮点运行部分的6%的数字。
这一返工从小到二进制的老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;
};
该sqrt呼吁不是完全准确的，正如已经提到的，但它是有趣和有启发性的，它不吹走的其他答复方面的速度。毕竟，序列的大会语言指令的一sqrt是微小的。英特尔有硬件的指令，该指令并不使用通过Java，我相信，因为它不符合IEEE。
那么为什么慢？因为Java实际上是呼吁C程序通过JNI,它实际上更慢这样做比通话Java子程序，这本身就是慢于这样做的内联。这是非常令人讨厌，并Java应该有一个更好的解决方案，即建筑在浮点图书馆的电话如果有必要的。哦，好的。
C++，我怀疑所有复杂的替代品就失去了对速度，但我没有检查他们所有。我做了什么，什么Java人民将找到有用的，是一个简单的哈克,一个扩展的特殊情况下测试的建议。雷克斯。使用一个单一的长期价值作为一位阵列，这并不是边界检查。这样，你有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;
}
常规isPerfectSquare5运行中大约1/3的时间上我的酷睿2朵机。我怀疑，进一步调整，沿着相同的路线可以减少时间上进一步平均水平，但是每一次检查，你是交易更多的测试，为更多的消除，所以你不能走的太远上这条道路。
当然，而不是具有一种独立的测试为消极的，你可以检查高6位相同的方式。
注意，我所做的是消除可能广场，但是，当我有一个潜在的情况下我得打电话给原来，内联isPerfectSquare.
该init2常被称为一次初始化的静态价值的pp1和pp2。请注意，在我的执行情况在C++，我使用的unsigned long长，所以因为你签名，你不得不使用>>>操作员。
有没有内在的需要对边界检查阵列，但Java的优化了图这东西很快，所以我不责怪他们。
我喜欢这个主意使用一个几乎是正确的方法上的一些输入。这里是一个版本具有较高"offset"。代码似乎工作，并通过我的简单测试的情况。
只是替换您的：
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);
}
项目Euler中提到的标记和许多问题需要检查的数字>> 2^64.最优化上面提到不容易的时候你都工作80字节的缓冲区。
我用java BigInteger并略加修改的牛顿的方法，一个运作更好地与整数。问题是，确切的方 n^2 融合到 (n-1) 而不是的 n 因 n^2-1 = (n-1)(n+1) 和最后的错误只是一个步骤下的最后数和算法的终止。这是容易解决通过增加一个原始参数之前计算错误。(添加两个对立方的根源，等等。)
一个很好的属性，这种算法是，你可以马上告诉我们，如果人数是一个完美的平最终的错误(未修正)在牛顿的方法将为零。一个简单的修改也可以让你快速计算 floor(sqrt(x)) 而不是最接近整数。这是方便与几个欧拉问题。
我检查了所有的可能结果在最后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
它第一次测试是否具有一广场残留与模量的权力，然后它测试的基础上最终模量，然后它使用数学。sqrt做最后的测试。我想从最高职位，并企图以延长。我赞赏任何意见或建议。
更新： 使用试验模量，(modSq)和一个模基础的44352，我的测试运行，96％的时间的一个中运的更新数达到1,000,000,000.
考虑到对于一般的位长(虽然我已经使用的特定类型在这里)时，我想设计简单的算法如下。简单而明显的检查为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;
}
我不知道，如果这已经提到过。但是我找到一个解决方案 在这里，:
int result = (int)(floor(sqrt(b)) - ceil(sqrt(a)) + 1);
如果速度是一个关切的是，为什么不隔离最常用的设的投入和他们的价值观为一个查询表，然后做什么魔术优化算法你来了特殊的情况下？
它应该是可能的包装'不是一个完全平方如果最后一个X的数字是N'更有效地比！我会用java32位整数，产生足够的数据，以检查过去的16位的数量-这就是2048十六int值。
...
"确定"。无论我们遇到一些数字理论就是有点超出了我，还有一个错误，在我的代码。在任何情况下，在这里是代码:
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;图修改历史上来看看。)
这里是最简单和最简洁的方式，虽然我不知道它是如何进行比较方面的CPU周期。这个伟大的工程，如果你只想要知道如果根是一个整数。如果你真的关心，如果它是一个整数，也可以图。这里是一个简单的(和纯粹的)功能：
public static boolean isRootWhole(double number) {
return Math.sqrt(number) % 1 == 0;
}
如果你不需要微型最优化，这个回答是在简单性和可维修性。如果你将会获得负数，也许你会想要利用数学。abs()数量参数的数学。sqrt()参数。
在我的3.6Ghz英特尔i7-4790CPU,一个运行的这种算法上的0-10,000,000的平均35-37毫微秒每计算。我做了10顺序运行的、印刷的平均时间花在每十万sqrt计算。每一个总的了只是小小的过600毫来完成。
如果你正在执行一个较小数量的计算，较早的计算，采取多一点的时间。
这里是一个分而治解决方案。
如果平方根的一个自然的数量(number)是一种自然的数量(solution)，可以很容易地确定一个范围 solution 基于数字的 number:
number有1位数:solution在范围=1-4number有2位数：solution在范围=3-10number有3位数：solution在范围=10-40number有4位数：solution在范围=30-100number有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"
如果你想的速度，鉴于你的整数的大小有限，我怀疑那最快的方式将涉及(a)分区的参数通过的大小(例如进行分类的最大的位置)，然后检查的价值对一系列的完全平方在这一范围。
关于Carmac方法，这似乎是很容易的只是一次迭代更为，这应该双位数的准确性。它毕竟是一个极为截断迭代方法--牛顿，具有非常良好的第一猜测。
关于你目前最好的，我看到两个微优化：
- 移动的检查与0后，检查使用mod255
- 重新排列分割出去的权力的四个跳过所有的检查常用(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;
显然，它想知道有多少个号码获得扑杀，在每个检查点-我不怀疑检查的真正独立，这使事情变得棘手。
"我正在寻找最快速的方式确定，如果一个长期价值是一个完全平方(即它的平方根是另一个整数)。"
答复是令人印象深刻，但是我没有看到一个简单的检查：
检查是否第一个数字上的权利只要它的成员设置(0,1,4,5,6,9).如果不是，则它不可能是一个完美的方'.
例如。
4567-不可能是一个完美的正方形。
