Самый быстрый способ определить, является ли квадратный корень целого числа целым числом
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для результата Math.sqrt() не требуется, по крайней мере, на моей машине. - А быстрый обратный квадратный корень был быстрее, но давал неверные результаты для n >= 410881.Однако, как предполагает Бобби Шафто, мы можем использовать хак FISR для n < 410881.
- Метод Ньютона был немного медленнее, чем
Math.sqrt().Вероятно, это потому, чтоMath.sqrt()использует нечто похожее на метод Ньютона, но реализованное аппаратно, поэтому оно намного быстрее, чем в Java.Кроме того, метод Ньютона по-прежнему требовал использования двойников. - Модифицированный метод Ньютона, в котором использовалось несколько приемов, чтобы использовались только целочисленные математические операции, требовал некоторых хитростей, чтобы избежать переполнения (я хочу, чтобы эта функция работала со всеми положительными 64-битными целыми числами со знаком), и он все равно был медленнее, чем
Math.sqrt(). - Бинарный чоп был еще медленнее.Это имеет смысл, поскольку двоичная обработка в среднем потребует 16 проходов, чтобы найти квадратный корень из 64-битного числа.
- Согласно тестам Джона, использование
orинструкции выполняются быстрее в C++, чем при использованииswitch, но в Java и C#, похоже, нет никакой разницы междуorиswitch. - Я также попытался создать таблицу поиска (как частный статический массив из 64 логических значений).Тогда вместо переключения или
orутверждение, я бы просто сказалif(lookup[(int)(n&0x3F)]) { test } else return false;.К моему удивлению, это было (немного) медленнее.Это потому что границы массива проверяются в Java.
Решение
Я нашел метод, который работает примерно на 35% быстрее, чем ваш 6-битный код + Carmack + sqrt, по крайней мере, с моим процессором (x86) и языком программирования (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 остатков по модулю 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 - Наконец, попробуйте вычислить квадратный корень, используя метод, аналогичный Лемма Гензеля.(Я не думаю, что это применимо напрямую, но с некоторыми модификациями работает.) Прежде чем сделать это, я делю все степени 2 с помощью двоичного поиска:
На этом этапе, чтобы наше число было квадратом, оно должно быть 1 по модулю 8.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^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 значение наибольшей степени двойки, делящей 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-компоновывается в одну инструкцию i86.
После удаления конечных нулей третий тест обрабатывает числа, оканчивающиеся на 011, 101 или 111 в двоичном формате, которые не являются точными квадратами.Он также заботится об отрицательных числах, а также обрабатывает 0.
Последний тест возвращается к double арифметика.Как double имеет только 53 бита Mantissa, преобразование из long к double включает округление для больших значений.Тем не менее, тест верен (если только доказательство неправильно).
Попытка реализовать идею mod255 не увенчалась успехом.
Вам придется провести некоторый сравнительный анализ.Лучший алгоритм будет зависеть от распределения ваших входных данных.
Ваш алгоритм может быть почти оптимальным, но вам может потребоваться выполнить быструю проверку, чтобы исключить некоторые возможности, прежде чем вызывать процедуру квадратного корня.Например, посмотрите на последнюю цифру вашего номера в 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++, он работал медленнее оригинала.Однако когда я исключил оператор переключения, шестнадцатеричный трюк снова сделал код вдвое быстрее.
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 ) )line по сути снова повторяет значение функции.
Функция аппроксимации дает более точные значения, чем больше вы повторяете функцию по результату.В случае с Quake одной итерации «достаточно хорошо», но если бы не вы…тогда вы можете добавить столько итераций, сколько вам нужно.
Это должно быть быстрее, поскольку сокращает количество операций деления, выполняемых при простом извлечении квадратного корня, до простого деления на 2 (на самом деле * 0.5F операцию умножения) и вместо этого замените ее несколькими фиксированными числами операций умножения.
Я не уверен, будет ли это быстрее или даже точнее, но вы можете использовать Волшебный квадратный корень Джона Кармака, алгоритм для более быстрого извлечения квадратного корня.Вероятно, вы могли бы легко проверить это для всех возможных 32-битных целых чисел и убедиться, что вы действительно получили правильные результаты, поскольку это всего лишь аппроксимация.Однако теперь, когда я думаю об этом, использование двойных чисел также является приблизительным, поэтому я не уверен, как это войдет в игру.
Если вы выполните двоичную операцию, чтобы попытаться найти «правильный» квадратный корень, вы можете довольно легко определить, достаточно ли близко полученное значение, чтобы сказать:
(n+1)^2 = n^2 + 2n + 1
(n-1)^2 = n^2 - 2n + 1
Итак, подсчитав n^2, варианты:
n^2 = target:готово, вернуть truen^2 + 2n + 1 > target > n^2:ты близок, но это не идеально:вернуть ложьn^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 оператор в один оператор if.Однако это может увеличить время выполнения, если многие из протестированных чисел имеют значительную степень двойки.
Алгоритмы ниже следующие:
- Интернет - опубликованный ответ Кипа
- Дюррон - Мой измененный ответ с использованием однопроходного ответа в качестве основы
- ДюрронДва - Мой измененный ответ с использованием двухпроходного ответа (от @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;
}
И мой эталонный жгут:(Требуется штангенциркуль 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 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, который представляет собой файл размером около 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;
}
Я загружаю его в 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
Использование должно быть намного быстрее метод Ньютона рассчитать Целочисленный квадратный корень, затем возведите это число в квадрат и проверьте, как вы это делаете в текущем решении.Метод Ньютона является основой решения Кармака, упомянутого в некоторых других ответах.Вы сможете получить более быстрый ответ, поскольку вас интересует только целая часть корня, что позволит вам быстрее остановить алгоритм аппроксимации.
Еще одна оптимизация, которую вы можете попробовать:Если Цифровой корень числа не заканчивается в 1, 4, 7 или 9. нет идеальный квадрат.Это можно использовать как быстрый способ исключить 60% входных данных перед применением более медленного алгоритма квадратного корня.
Я хочу, чтобы эта функция работала со всеми положительными 64-битными подписанными целыми числами
Math.sqrt() работает с числами типа double в качестве входных параметров, поэтому вы не получите точных результатов для целых чисел больше 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(log n).
Если вы не знаете, как выполнять двоичный поиск положительных целых чисел, поскольку их множество неограничено, это легко.Вы начинаете с вычисления возрастающей функции f (выше f(t) = t**2 - n) по степеням двойки.Когда вы увидите, что он стал положительным, вы нашли верхнюю границу.Затем вы можете выполнить стандартный двоичный поиск.
Было отмечено, что последнее d цифры идеального квадрата могут принимать только определенные значения.Последний d цифры (в базе b) числа n такое же, как остаток, когда n делится на bd, т.е.в нотации C n % pow(b, d).
Это можно обобщить на любой модуль m, т.е. n % m может использоваться, чтобы исключить некоторый процент чисел из числа идеальных квадратов.Модуль, который вы сейчас используете, равен 64, что позволяет 12, т.е.19% остатков, как возможные квадраты.Немного кодируя нашел модуль 110880, который позволяет только 2016 год, т.е.1,8% остатков как возможные квадраты.Таким образом, в зависимости от стоимости операции модуля (т.деление) и поиск по таблице вместо квадратного корня на вашем компьютере, использование этого модуля может быть быстрее.
Кстати, если в Java есть способ хранения упакованного массива битов для таблицы поиска, не используйте его.В наши дни 110880 32-битных слов — это не так много оперативной памяти, и получение машинного слова будет быстрее, чем выборка одного бита.
Для производительности очень часто приходится идти на некоторые компромиссы.Другие предлагали различные методы, однако вы отметили, что хак Кармака был быстрее до определенных значений N.Затем вам следует проверить «n», и если оно меньше этого числа N, используйте хак Кармака, иначе используйте другой метод, описанный в ответах здесь.
Это самая быстрая реализация Java, которую я смог придумать, используя комбинацию методов, предложенных другими в этой теме.
- Испытание Мод-256
- Неточный тест mod-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 ниже должно быть
m = N - (N & (N-1));
и не так, как написано
Конец второй редакции
m = N & (N-1); // the lawest bit of N
N /= m;
byte = N & 0x0F;
if ((m % 2) || (byte !=1 && byte !=9))
return false;
1-е редактирование:
Небольшое улучшение:
m = N & (N-1); // the lawest bit of N
N /= m;
if ((m % 2) || (N & 0x07 != 1))
return false;
Конец первого редактирования
Теперь продолжайте как обычно.Таким образом, к тому моменту, когда вы доберетесь до части с плавающей запятой, вы уже избавитесь от всех чисел, чья 2-степенная часть нечетна (около половины), и затем вы учитываете только 1/8 того, что осталось.Т.е.вы запускаете часть с плавающей запятой для 6% чисел.
Это переделка старого алгоритма калькулятора Маршана с десятичного на двоичный (извините, у меня нет ссылки) на 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;
};
Как уже упоминалось, вызов sqrt не совсем точен, но он интересен и поучителен тем, что не превосходит другие ответы с точки зрения скорости.В конце концов, последовательность инструкций языка ассемблера для sqrt крошечная.У Intel есть аппаратная инструкция, которая, я полагаю, не используется 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 выполняется примерно втрое быстрее, чем на моей машине с Core2 Duo.Я подозреваю, что дальнейшие настройки в том же духе могут в среднем еще больше сократить время, но каждый раз, когда вы проверяете, вы жертвуете дополнительным тестированием на большее количество исключений, поэтому вы не можете пойти слишком далеко по этому пути.
Конечно, вместо того, чтобы проводить отдельный тест на отрицательный результат, вы можете таким же образом проверить старшие 6 бит.
Обратите внимание: все, что я делаю, это исключаю возможные квадраты, но когда у меня есть потенциальный случай, мне приходится вызывать исходный встроенный метод isPerfectSquare.
Процедура init2 вызывается один раз для инициализации статических значений pp1 и pp2.Обратите внимание, что в моей реализации на C++ я использую unsigned long long, поэтому, поскольку вы подписаны, вам придется использовать оператор >>>.
Нет никакой внутренней необходимости проверять границы массива, но оптимизатор Java должен разобраться в этом довольно быстро, поэтому я не виню их в этом.
Мне нравится идея использовать почти правильный метод для некоторых входных данных.Вот версия с более высоким «смещением».Кажется, код работает и проходит мой простой тестовый пример.
Просто замените:
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);
}
В тегах упоминается проект Эйлер и многие задачи в нем требуют проверки цифр >> 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.
Сначала он проверяет, имеет ли он квадратичный остаток с модулем степени двойки, затем проверяет на основе окончательного модуля, а затем использует Math.sqrt для выполнения окончательного теста.Я придумал эту идею из верхнего поста и попытался ее развить.Я ценю любые комментарии или предложения.
Обновлять: Используя тест по модулю (modSq) и базе модуля 44352, мой тест выполняется в 96% случаев по сравнению с тестом в обновлении OP для чисел до 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» гораздо эффективнее, чем это!Я буду использовать 32-битные целые числа Java и получу достаточно данных для проверки последних 16 бит числа — это 2048 шестнадцатеричных целочисленных значений.
...
Хорошо.Либо я столкнулся с какой-то теорией чисел, которая мне немного непонятна, либо в моем коде есть ошибка.В любом случае вот код:
public static void main(String[] args) {
final int BITS = 16;
BitSet foo = new BitSet();
for(int i = 0; i< (1<<BITS); i++) {
int sq = (i*i);
sq = sq & ((1<<BITS)-1);
foo.set(sq);
}
System.out.println("int[] mayBeASquare = {");
for(int i = 0; i< 1<<(BITS-5); i++) {
int kk = 0;
for(int j = 0; j<32; j++) {
if(foo.get((i << 5) | j)) {
kk |= 1<<j;
}
}
System.out.print("0x" + Integer.toHexString(kk) + ", ");
if(i%8 == 7) System.out.println();
}
System.out.println("};");
}
и вот результаты:
(ред:исключен из-за низкой производительности в prettify.js;просмотрите историю изменений, чтобы увидеть.)
Вот самый простой и краткий способ, хотя я не знаю, как его можно сравнить с точки зрения циклов процессора.Это отлично работает, если вы хотите знать, является ли корень целым числом.Если вас действительно волнует, является ли это целым числом, вы также можете это выяснить.Вот простая (и чистая) функция:
public static boolean isRootWhole(double number) {
return Math.sqrt(number) % 1 == 0;
}
Если вам не нужна микрооптимизация, этот ответ лучше с точки зрения простоты и удобства обслуживания.Если вы будете получать отрицательные числа, возможно, вы захотите использовать Math.abs() для числового аргумента в качестве аргумента Math.sqrt().
На моем процессоре Intel i7-4790 с частотой 3,6 ГГц выполнение этого алгоритма на 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"
Если вам нужна скорость, учитывая, что ваши целые числа имеют конечный размер, я подозреваю, что самый быстрый способ будет включать (а) разделение параметров по размеру (например,на категории по наибольшему набору битов), а затем сверяем значение с массивом идеальных квадратов в этом диапазоне.
Что касается метода Кармака, кажется, что было бы довольно легко просто повторить итерацию еще раз, что должно удвоить количество цифр точности.В конце концов, это чрезвычайно усеченный итеративный метод — метод Ньютона, с очень хорошим первым предположением.
Что касается вашего текущего лучшего результата, я вижу две микрооптимизации:
- переместить чек vs.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 – не может быть идеальным квадратом.
