Я ищу самый быстрый способ определить, является ли длинное
значение совершенным квадратом (т.е. его квадратный корень равен другому целому числу):
Math.sqrt()
но мне интересно, есть ли способ сделать это быстрее, если
ограничиваясь только целочисленной областью.Вот очень простой и понятный способ, которым я сейчас это делаю:
public final static boolean isPerfectSquare(long n)
{
if (n < 0)
return false;
long tst = (long)(Math.sqrt(n) + 0.5);
return tst*tst == n;
}
Примечание: я'использую эту функцию во многих <a href="http://projecteuler.net/">- задачах проекта Эйлер. Так что никому больше не придется поддерживать этот код. И такая микрооптимизация может действительно иметь значение, поскольку часть задачи состоит в том, чтобы выполнить каждый алгоритм менее чем за минуту, а эту функцию придется вызывать миллионы раз в некоторых задачах.
Я'пробовал различные решения этой проблемы:
0.5
к результату Math.sqrt() не является необходимым, по крайней мере, на моей машине.Math.sqrt()
. Возможно, это потому, что Math.sqrt()
использует что-то похожее на метод Ньютона, но реализованное в аппаратном обеспечении, поэтому он намного быстрее, чем в Java. Кроме того, метод Ньютона по-прежнему требует использования удвоителей.Math.sqrt()
.or
быстрее в C++, чем switch
, но в Java и C#, похоже, нет разницы между or
и switch
.or
я просто сказал if(lookup[(int)(n&0x3F)]) { test } else return false;
. К моему удивлению, это оказалось (совсем немного) медленнее. Это происходит потому, что <a href="https://stackoverflow.com/questions/299079/why-is-this-code-with-several-or-statements-slightly-faster-than-using-a-lookup-t#299205">- границы массивов проверяются в Java.Я придумал способ, который работает ~35% быстрее, чем ваши 6bits+Кармак+код получается, по крайней мере, с мой процессор (x86) и языка программирования (Си/Си++). Ваши результаты могут отличаться, особенно потому, что я Дон'т знаю, как Java-фактор будет играть. Мой подход состоит из трех частей: <пр> <ли>во-первых, отфильтровать очевидные ответы. Сюда входят отрицательные числа, и глядя на последние 4 бита. (Я обнаружил, глядя на последние шесть не'т помочь). Мне тоже ответьте Да для 0. (При чтении кода ниже, обратите внимание, что мой вклад в <код>тип int64 х</код>.) в <предварительно><код>если( Х &ЛТ; 0 || (х&2) || ((х & 7) == 5) || ((х & 11) == 8) ) возвращает false; если( Х == 0 ) возвратите True;</код></пре> </ли> в <ли>В следующий, проверить, если он's в квадрат по модулю 255 = 3 5 17. Потому что's в произведение трех различных простых чисел, только около 1/8 мод остатков 255-квадраты. Однако, по моему опыту, позвонив оператору по модулю (%) стоит больше, чем выгода складывается, поэтому я использую немного трюков с 255 = 2^8-1 для вычисления остатка. (Для лучше или хуже, я не использую трюк чтения отдельных байтов в словах, только побитовое и и смены.) в <предварительно><код>в int64 у = Х; г = (г & 4294967295LL) + (г &ГТ;&ГТ; 32); г = (г & 65535) + (г &ГТ;&ГТ; 16); г = (г & 255) + ((й &ГТ;&ГТ; 8) & 255) + (г &ГТ;&ГТ; 16); // На данный момент, Y-от 0 до 511. Больше кода может уменьшить ее дальше. </пре></код> На самом деле проверить, если остаток представляет собой квадрат, я смотрю на ответ в предварительно вычисляемые таблицы. в <предварительно><код>если( bad255[г] ) возвращает false; Однако//, я просто использовать таблицу размером 512 </код></пре> </ли> <ли>и, наконец, попытаться вычислить квадратный корень с помощью метода, аналогичного в <а href="и http://en.wikipedia.org/wiki/Hensel%27s_lemma">Хенсел'ы lemma</а>. (Я не'т думаю, что это's применяется непосредственно, но он работает с некоторыми изменениями.) Прежде чем сделать это, я делю все полномочия 2 с двоичным поиском: в <предварительно><код>если((Х & 4294967295LL) == 0) х &ГТ;&ГТ;= 32; если((Х & 65535) == 0) х &ГТ;&ГТ;= 16; если((Х & 255) == 0) х &ГТ;&ГТ;= 8; если((Х & 15) == 0) х &ГТ;&ГТ;= 4; если((Х & 3) == 0) х &ГТ;&ГТ;= 2;</код></пре> На данный момент, для нашего номера, чтобы быть квадратным, оно должно быть 1 мод 8. в <предварительно><код>если((Х & 7) != 1) возвратить false;</код></пре> Базовая структура Хенсел'ы леммы является следующее. (Примечание: непроверенный код; если это не'т работу, попробуйте T=2 или 8.) в <предварительно><код>тип int64 Т = 4, р = 1; Т &ЛТ;&ЛТ;= 1; р += ((х - р р) & Т) &ГТ;&ГТ; 1; Т &ЛТ;&ЛТ;= 1; р += ((х - р р) & Т) &ГТ;&ГТ; 1; Т &ЛТ;&ЛТ;= 1; р += ((х - р р) & Т) &ГТ;&ГТ; 1; // Повторять, пока Т 2^33 или около того. Использовать цикл, если вы хотите.</код></пре> Идея заключается в том, что на каждой итерации добавляется один бит на R, то на "настоящих" у квадратный корень из х; каждого квадратного корня является точной дулю большую степень числа 2, а именно Т/2. В конце концов, R и T/2-R будет квадратный корень из х по модулю Т/2. (Заметим, что если R представляет собой квадратный корень из х, то -р. Это верно даже по модулю числа, но будьте осторожны, по модулю некоторого числа, вещи могут иметь даже больше, чем 2 квадратные корни; в частности, это включает полномочия 2.) Ведь наша настоящая квадратный корень меньше, чем 2^32, в этот момент мы можем просто проверить, если R или T/2-р реальные квадратные корни. В мой фактический код, я использую следующие модифицированные петли: в <предварительно><код>типа int64, р, т, Z; р = с[(х &ГТ;&ГТ; 3) & 1023]; делать { З = х - р р; если( я == 0 ) возвратите True; если( з &ЛТ; 0 ) возвращает false; т = з & (-з); р += (з & Т) &ГТ;&ГТ; 1; если( Р &ГТ; (Т &ГТ;&ГТ; 1) ) р = т - р; } пока( Т &ЛТ;= (1LL &ЛТ;&ЛТ; 33) );</код></пре> Ускорение здесь достигается тремя способами: предварительно вычисляемые значения начала (эквивалентно ~10 итераций цикла), в начале выхода петли, и пропуская некоторые значения t. Для последней части, я смотрю в <код>У з = р - х * х на< код>, А присвоить t к величине мощности 2 деления Z с немного трюк. Это позволяет мне пропустить Т значения, что бы'т иметь в любом случае влияет на значение R. Значение начать пересчитывать в моем случае выбирает по себе "маленькое положительное, что" квадратный корень по модулю 8192. </ли> </ол> Даже если этот код не'т работать быстрее для вас, я надеюсь, вам понравится некоторые из идей, которые он содержит. Полный, проверенный код образом, в том числе предварительно вычисляемые таблицы. в <предварительно><код>определение типа подписал длинный инт типа int64; инт начала[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}; боол 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}; площадь встроенного типа bool( тип int64 х ) { // Quickfail если( Х &ЛТ; 0 || (х&2) || ((х & 7) == 5) || ((х & 11) == 8) ) возвращает false; если( Х == 0 ) возвратите 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-элемент таблицы упакованные в длинный, поэтому там's нет выбора стоимости доступа (косвенный и границы проверяет). Для абсолютно случайная "длинные", там'ы на 81.25% вероятностью заканчивается здесь.
Второй тест ловит всех чисел, имеющих нечетное число двоек в их факторизации. Долго метод`.numberOfTrailingZeros очень быстро, как он получает с помощью JIT-ЭД в один i86 инструкция.
После падения нули, третий тест ручки, номера, заканчивающиеся на 011, 101 или 111 в двоичной форме, не совершенные квадраты. Он также заботится о отрицательные числа и 0.
Итоговый тест возвращается к "двойным" арифметика. Как "двойной" имеет только 53 бита мантиссы,
преобразование из длинных
в тип double
включает округления для больших значений. Тем не менее, этот тест является правильным (если доказательства - это неправильно).
Пытаюсь включить mod255 идея была'т успеха.
[источник]: https://www.dropbox.com/s/ad4r6oxfcilqkch/IsSquareBenchmark.java?dl=0
Вы'll должны сделать некоторые бенчмаркинг. Лучший алгоритм будет зависеть от распределения входных данных.
Ваш алгоритм может быть почти оптимальным, но вы можете сделать быструю проверку, чтобы исключить некоторые возможности, прежде чем звонить корень квадратный рутины. Например, посмотрите на последнюю цифру вашего номера в hex делать немного-Мудрый "и.&идеальный квадратов может закончиться только в 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++, на самом деле она побежала медленнее, чем оригинал. Однако, когда я ликвидировал оператор 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#.
Я думал о тех ужасных временах, которые я провел на курсе "Численный анализ".
И тут я вспомнил, что была одна функция, кружащаяся по 'сети из исходного кода 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 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 Software!
Он написан на 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 )
в основном итерирует значение над функцией снова.Функция аппроксимации дает тем более точные значения, чем больше итераций функции над результатом. В случае с Quake одна итерация - это "достаточно хорошо", но если это не так... то вы можете добавить столько итераций, сколько вам нужно.
Это должно быть быстрее, поскольку сокращает количество операций деления, выполняемых в наивном квадратичном корне, до простого деления на 2 (фактически операция умножения * 0.5F
) и заменяет их несколькими фиксированными операциями умножения.
Я'м не уверен, если это будет быстрее, или даже точно, но вы могли бы использовать Джон Кармак'ы магический квадрат корень, алгоритм решения квадратного корня быстрее. Вы, вероятно, может легко проверить это для всех возможных 32-битные целые числа, и проверить, что вы на самом деле получил правильные результаты, как это's только один appoximation. Однако, теперь, когда я думаю об этом, используя парный, приближая тоже, поэтому я'м не уверен, как это будет вступать в игру.
Если вы выполняете бинарное преобразование, пытаясь найти "правильный" квадратный корень, вы можете довольно легко определить, достаточно ли близко полученное вами значение:
(n+1)^2 = n^2 + 2n + 1
(n-1)^2 = n^2 - 2n + 1
Итак, вычислив n^2
, можно выбрать следующие варианты:
n^2 = target
: сделано, return truen^2 + 2n + 1 > target > n^2
: вы'близки, но это'не идеально: return falsen^2 - 2n + 1 < target < n^2
: dittotarget < n^2 - 2n + 1
: двоичная отбивка на меньшем n
target > n^2 + 2n + 1
: двоичная отбивка по большему n
(Извините, здесь используется n
как ваше текущее предположение, а target
как параметр. Прошу прощения за путаницу!)
Я не знаю, будет ли это быстрее или нет, но попробовать стоит.
EDIT: Двоичное сокращение не обязательно должно принимать весь диапазон целых чисел, также как и (2^x)^2 = 2^(2x)
, так что как только вы найдете верхний бит набора в вашей цели (что можно сделать с помощью трюка с перестановкой битов; я забыл, как именно), вы можете быстро получить диапазон потенциальных ответов. Имейте в виду, что наивное двоичное преобразование все равно займет не более 31 или 32 итераций.
Я провел анализ нескольких алгоритмов в этой теме и придумал некоторые новые результаты. Вы можете посмотреть эти старые результаты в изменение истории этого ответа, но они'повторно не точная, так как я допустил ошибку и потратили время анализа нескольких алгоритмов, которые еще't закройте. Однако, вытягивать уроки из несколько разных ответов, у меня теперь есть два алгоритма, которые давят на "победитель" из этого потока. Здесь'ы главное я сделал по-другому, чем все остальные:
// 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;
Однако, эта простая линия, которая большую часть времени добавляет один или два очень быстро объяснят, что значительно упрощает переключения
заявление в случае, если заявление. Однако, он может добавить к выполнения если многие проверенные цифры имеют значительные мощности-из-двух факторов.
Приведенные ниже алгоритмы являются следующие:
Вот пример выполнения, если цифры генерируются с помощью математика.АБС(Ява.утиль.Случайные.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
А вот пример выполнения, если это's запускает на Первом только миллионов тоскует:
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
делает лучше для больших входов, потому что он добирается, чтобы использовать фокус очень часто, но будет повреждена по сравнению с первым алгоритмом и математике.корень, потому что эти цифры намного меньше. Между тем, проще 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;
}
И мой тест проводов (требуется 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];
@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 х 3 х 5 х 7 х 13 х 17 х 241
, мы можем исключить 97.82% чисел, которые не могут быть квадратами. Это можно (вроде) сделать в одну строчку, с 5 побитовые операции:
if (!goodLookupSquares[(int) ((n & 0xFFFFFFl) + ((n >> 24) & 0xFFFFFFl) + (n >> 48))]) return false;
В результате индекс является либо 1) осадок, 2) остаток + цвет 0xffffff
, или 3) остаток + 0x1FFFFFE
. Конечно, мы должны иметь таблицы подстановки для цвет 0xffffff по модулю остатков, которая составляет около 3 МБ файл (в этом случае хранятся в виде чисел текст десятичный код 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;
}
Я загрузить его в логическое
массив такой:
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
Это должно быть намного быстрее, чтобы использовать Ньютон'ы Способ для расчета число, квадратный корень, тогда квадрат этого числа и проверить, как вы делаете в ваше текущее решение. Ньютон'ы метод является основой для решения Кармак упоминал в некоторых других ответов. Вы должны быть в состоянии получить быстрее ответ, так как вы'вновь интересует только целая часть от корня, что позволяет остановить приближение алгоритма рано.
Другая оптимизация, которую вы можете попробовать: если цифровой корень ряда не'т в 1, 4, 7, или 9 номер **** не идеальный квадрат. Это может быть использован как быстрый способ избавиться от 60% вашего вклада перед нанесением медленнее корневой алгоритм площади.
Я хочу, чтобы эта функция работала со всеми позитивный 64-разрядных целых чисел со знаком
Математика.работает функция 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, которая выиграла'т работу над 2^54, Как говорит mrzl в ответ.
Проблема целочисленного заслуживает целочисленное решение. Таким образом
Сделать бинарный поиск по (неотрицательных) целых чисел найти наибольшее целое число Т такое, что Т2 <= Н. Затем проверить, является ли
р2 = н` точно. Это занимает время o(зарегистрируйте N).
Если вы Don'т знаю, как двоичный поиск положительных чисел, потому что набор неограничен, он's легко. Вы начинаете путем вычисления своего увеличения функция f (выше `ф(т) = т**2 - п) по степени двойки. Когда вы видите, что это станет положительным, вы'вэ нашел верхнюю границу. Затем вы можете сделать стандартный двоичный поиск.
Это'ы было указано, что последняя " д " цифры идеальный квадрат может принимать только определенные значения. Последняя " д "цифры (в базовом уровне "B") с номером N является таким же, как остальные, когда Н
делится на б
<суп>д
</суп>, Т. е.. в нотации c Н % Пау(Б, г)
.
Это можно обобщить на любой модуль м
, т. Е. Н % м
может быть использован, чтобы исключить какой-то процент чисел от совершенства квадратов. Модуль в настоящее время вы используете 64, что позволяет 12, т. е.. 19% пожнивных остатков, квадратов, как это возможно. С минимум кода, я нашел модуль 110880, которая позволяет только в 2016, т. е. 1,8% от остатков квадратов, как это возможно. Поэтому в зависимости от стоимость операции модуля (т. е. дивизии) и таблицы подстановки или квадратный корень на компьютере, с помощью этого модуля можно быстрее.
Кстати, если Java имеет возможности хранить упакованный массив битов для таблицы подстановки, Дон'т использовать его. 110880 32-битных слов не много оперативной памяти и извлечения машинное слово-это будет быстрее, чем получение одного бита.
Для производительности, вы очень часто приходится делать некоторые compromsies. Другие выражают различные методы, однако отметил Кармак'ы Хак был быстрее до определенных значений и т. п. Затем, вы должны проверить на "Н" и если оно меньше, чем число 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;
будет влиять на производительность.
Это самая быстрая реализация Java, который я мог придумать, используя комбинацию методов, предложенных другими в этой теме.
Я также экспериментировал с этими изменениями, но они не помогали производительности:
<Р/>
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;
}
}
}
Вы должны избавиться от 2-силовая часть Н с самого начала.
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 часть, что осталось. Т. е. вы запустите с плавающей запятой часть на 6% чисел.
Проект Эйлера упоминается в тегах и многие проблемы в ней требует проверки номера >> 2^64
. Большинство оптимизаций упомянутый выше Дон'т работать легко, когда вы работаете с 80-байтовый буфер.
Я использовал в Java BigInteger и слегка модифицированная версия Ньютон'ы метод, который лучше работает с целыми числами. Проблема в том, что точные квадраты-н^2вместе
(П-1)вместо
Н, потому что
Н^2-1 = (П-1)(п+1) и окончательной ошибка была только на один шаг ниже окончательной делитель и алгоритм завершается. Это было легко исправить путем добавления одного к первоначальному аргументов перед вычислением ошибки. (Добавить двух корней куб и т. д.)
Один хороший атрибут этого алгоритма заключается в том, что вы можете сразу сказать, если число является полным квадратом - окончательная ошибка (не коррекция) в Ньютон'ы способ будет ноль. Простая модификация также позволяет быстро вычислить пол(функция sqrt(х)) вместо ближайшего целого числа. Это удобно с нескольких проблем Эйлера.
Это переделки из десятичной в двоичную старого алгоритма калькулятора Маршан (к сожалению, я не'Т есть ссылка), в Ruby, адаптированные специально для этого вопроса:
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
Здесь'ы обследования что-то подобное (пожалуйста, Дон'т голосовать меня за стиль кодирования/запахи или неуклюжим О/О - это'ы алгоритм, который рассчитывает, и 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;
};
Мне нравится идея использовать почти правильный способ на некоторых входных данных. Вот версия с более высоким "в зачет" по. Код, кажется, работает и проходит мой простой тестовый случай.
Просто заменить:
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);
}
Этот корень называют не вполне точным, как уже было сказано, но это'ы интересна и поучительна, что он не'т удар от других ответов с точки зрения скорости. В конце концов, последовательность инструкции языка ассемблера для неотрицательных крошечный. Intel имеет аппаратную инструкция, которой нет'т используется Java-я считаю, что это не'т соответствовать стандарту IEEE.
Так почему это медленно? Потому что Java-это на самом деле вызов процедуры на C через JNI, и он'ов на самом деле медленнее, чем в вызов Java подпрограмму, которая сама по себе медленнее, чем встроенные. Это очень раздражает, и Java следовало бы придумать лучшего решения, т. е. строят в плавучей библиотеке точка звонки, если это необходимо. Да ладно.
В C++, я подозреваю, что все сложные альтернативы проигрывают по скорости, но я еще'т проверил их все. То, что я сделал, и что Ява люди найдут полезный, простой лайфхак, расширения, проведения специальной проверки случае предложенной А. Рекс. Использовать один длинный значение как битовый массив, что это'т границы проверяется. Таким образом, Вы имеете 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 машина дуэта. Я подозреваю, что дальнейших изменений в том же духе может еще больше сократить время на среднем, но каждый раз, когда вы проверяете, Вы торгуете больше испытывать дополнительные исключения, так что вы можете't идти слишком далеко по этому пути.
Конечно, вместо того, чтобы иметь отдельный тест отрицательный, вы можете проверить высокий 6 бит одинаково.
Обратите внимание, что все, что я'м делаю исключения возможных квадратов, но когда у меня есть потенциальный случай, если мне придется назвать оригинальным, isPerfectSquare встроен.
В init2 процедура вызывается один раз для инициализации статического значения РР1 и рр2. Обратите внимание, что в моей реализации в C++, я'м через неподписанные долго долго, что вы'вновь подписали, вы'd должны использовать >>> оператор.
Нет внутренней необходимости, чтобы проверить границы массива, но Java'ы оптимизатора со всем этим разобраться довольно быстро, так что я не'т винить их за это.