Самый быстрый способ определить, является ли квадратный корень целого числа целым числом

avatar
Kip
17 ноября 2008 в 13:43
296138
35
1536

Я ищу самый быстрый способ определить, является ли значение long точным квадратом (т.е. его квадратный корень - другое целое число):

  1. Я сделал это простым способом, используя встроенный Math.sqrt() функция, но мне интересно, есть ли способ сделать это быстрее, ограничивая себя целочисленным доменом.
  2. Ведение таблицы поиска нецелесообразно (поскольку существует около 2 31,5 целые числа, квадрат которых меньше 2 63 ).

Вот очень простой и понятный способ, которым я сейчас это делаю:

public final static boolean isPerfectSquare(long n)
{
  if (n < 0)
    return false;

  long tst = (long)(Math.sqrt(n) + 0.5);
  return tst*tst == n;
}

Примечание: я использую эту функцию во многих проблемах Project Euler. Так что никому больше никогда не придется поддерживать этот код. И такая микрооптимизация может действительно иметь значение, поскольку часть задачи состоит в том, чтобы выполнить каждый алгоритм менее чем за минуту, а в некоторых задачах эту функцию нужно будет вызывать миллионы раз.


Я пробовал разные решения проблемы:

Источник
T.E.D.
17 ноября 2008 в 14:23
0

Поскольку Integer и Long на самом деле не имеют определенной длины (в большинстве языков C-ish, как выглядит ваш код), лучше сказать, что для 32-битного целого числа есть 2 ** 16 идеальных квадратов .

Kip
17 ноября 2008 в 14:35
23

Это код Java, где int == 32 бита и long == 64 бита, и оба подписаны.

ShreevatsaR
18 ноября 2008 в 16:52
0

Что быстрее: «long tst = (long) Math.sqrt (n); return tst * tst == n;» (что у вас есть) или «double tst = Math.sqrt (n); return tst == (double) Math.round (tst);» ?

Eric Weilnau
21 ноября 2008 в 14:23
0

Какую JVM вы использовали для тестирования? По моему опыту, производительность алгоритма зависит от JVM.

Kip
2 декабря 2008 в 20:03
16

@Shreevasta: Я провел несколько тестов на больших значениях (больше 2 ^ 53), и ваш метод дает несколько ложных срабатываний. Первый встречается для n = 9007199326062755, который не является точным квадратом, но возвращается как единица.

martinus
1 января 2009 в 23:48
0

В вашем коде есть ошибка: sqrt = (long) Math.sqrt (n); вернуть sqrt * sqrt == n; Math.sqrt (n) возвращает представление с плавающей запятой, например Math.sqrt (9) может вернуть 2.99999999999, если вам не повезло, и когда вы разыграете его с (long), вы легко можете получить слишком маленькое число.

A. Rex
7 января 2009 в 23:48
0

Вы можете использовать битовые уловки, чтобы проверить последние 6 бит: if ((x & 2) || ((x & 7) == 5) || ((x & 11) == 8) || ((x & 31) = = 20) || ((x & 47) == 24)) return false;

user9282
11 марта 2009 в 06:27
39

Пожалуйста, не называйте это «взломом Джона Кармака». Он этого не придумал.

Kip
11 марта 2009 в 12:41
1

@martinus: для значений ниже 2 ^ 53 двойное представление является точным, поэтому ошибки округления не будет. Я также проверил каждый идеальный квадрат больше 2 ^ 53, а также +/- 1 от каждого идеального квадрата, и ошибка округления никогда не приводит к неправильному ответу.

Thorbjørn Ravn Andersen
25 мая 2009 в 19:26
0

Я считаю, что современные JVM могут пропускать проверки индекса массива в заданном месте, если можно будет сделать вывод, что они всегда будут там действительны. С какой JVM проводилось тестирование?

Thorbjørn Ravn Andersen
26 мая 2009 в 11:39
0

«Взлом Джона Кармака» должен быть применим для большего диапазона, если нужно выполнить дополнительную итерацию, закомментированную в исходном коде Quake (т.е. число достаточно велико).

Kip
26 мая 2009 в 14:34
0

@ Thorbjørn Ravn Andersen: я использовал j2se 6.0 windows jvm, скачанный с сайта sun. Я также попытался раскомментировать дополнительную итерацию, и IIRC это действительно стало как-то менее точным.

dstibbe
25 сентября 2009 в 09:11
0

Сделайте свой quickfail быстрее и сделайте // Quickfail if (n <0 || ((n & 2)! = 0) || ((n & 7) == 5) || ((n & 11) == 8)) return ложный; если (n == 0) вернуть истину; наоборот: // Quickfail if (n == 0) return true; if (n <0 || ((n & 2)! = 0) || ((n & 7) == 5) || ((n & 11) == 8)) return false;

Kip
25 сентября 2009 в 13:08
0

@dstibbe: это будет быстрее, только если вход равен 0. для 75% других входов (даже не считая отрицательных чисел) он будет быстрее, чем он записан, а для остальных 25% разницы не будет.

Robert Fraser
6 мая 2010 в 10:25
89

@mamama - Возможно, но это ему приписывают. Генри Форд не изобрел машину, братья Райт не изобрели самолет, и Галлелео не был первым, кто выяснил, что Земля вращается вокруг Солнца ... мир состоит из украденных изобретений (и любовь).

bestsss
6 июня 2011 в 19:33
0

@Kip, микробенчмарк для алгоритма может быть отключен из-за относительно большой таблицы. Когда вся таблица находится в кеше (жесткие циклы), промахов в кеше не будет. Логическое значение [] следует заменить длинными константами (или массивом), и оно получит больше.

Nabb
1 ноября 2011 в 12:06
4

Вы можете получить небольшое увеличение скорости в «quickfail», используя что-то вроде ((1<<(n&15))|65004) != 0 вместо трех отдельных проверок.

Koray Tugay
26 мая 2013 в 00:50
1

Почему вы добавляете 0,5?

Kip
28 мая 2013 в 19:42
1

@KorayTugay, чтобы округлить число. Меня беспокоило то, что Math.sqrt может вернуть значение, которое немного отличается из-за ошибки округления. Скажем, если math.sqrt(100) вернул 9.999999999999999 вместо 10. Однако я не уверен, есть ли случаи, когда это действительно происходит.

durron597
10 июня 2013 в 23:10
0

@Kip ознакомьтесь с моим ответом, я получил значительный прирост производительности по вашему опубликованному ответу.

durron597
13 июня 2013 в 14:57
0

@Kip Я отредактировал свой пост, чтобы у него был третий алгоритм, который иногда работает лучше, чем мой предыдущий ответ.

OJFord
1 мая 2014 в 23:14
1

Удивленный тем, что не увидел такого популярного вопроса, кто-то указывал, что вы можете быть точными на более высоком уровне n, используя так называемый «взлом Кармака», выполнив еще одну итерацию (итерации). N.B. Результат не Кармака, а Ньютона / Рафсона, я полагаю, что взлом «магического числа» был бы более справедливым приписыванием Кармаку.

Travis
10 февраля 2015 в 04:40
1

Не уверен, что это то, что вам нужно, но это занимает около 1 миллисекунды. (JavaScript, а не Java.) return math.sqrt(x).split(".").length > 1

Jeutnarg
7 июля 2016 в 15:21
0

Я опаздываю на вечеринку, но я считаю, что вы можете выжать еще больше производительности из своего окончательного фрагмента кода, используя следующие методы: coderhelper.com/questions/15621083/…

Kip
12 октября 2016 в 14:08
1

@ user3932000 Я сделал это, потому что это может привести к небольшой оптимизации компилятора. Вот обсуждение получше: coderhelper.com/questions/5547663/…

Zackkenyon
24 января 2017 в 20:42
1

Я никогда не сталкивался с проблемой PE, которую нельзя было бы вычислить менее чем за минуту в ruby ​​. Так что аргумент о том, что производительность имеет значение для этого, немного невероятен.

Wheezil
28 февраля 2017 в 16:12
0

Мне любопытно, как эта мудрость сохраняется перед лицом таких инноваций, как SSE SQRTPS? felixcloutier.com/x86/SQRTPS.html,

btilly
13 декабря 2017 в 02:12
0

Каков пример проблемы, в которой это имеет значение? Вместо того, чтобы вычислять отдельные квадратные корни для длинного списка, гораздо лучше пройтись по списку полных квадратов и таким образом отфильтровать список.

Thomas Ahle
2 января 2018 в 23:53
1

Для очень больших чисел существует быстрый рандомизированный алгоритм: petr-mitrichev.blogspot.com/2017/12/a-quadratic-week.html

greybeard
25 марта 2018 в 17:32
2

@RobertFraser Галилео Галилей не был первым, кто искалечил свое имя.

Rok Kralj
22 апреля 2018 в 17:03
1

@RobertFraser: Да, и это великая несправедливость, с которой вы ничего не можете поделать. Это никогда не способ оправдать свое плохое поведение.

Viktor
19 января 2019 в 13:25
0

Я бы предложил использовать алгоритм целочисленного квадратного корня coderhelper.com/questions/1100090

ACV
20 февраля 2019 в 18:12
0

Итак, когда вы говорите «быстрее», каков базовый уровень? Насколько быстро у вас версия?

Brady Gilg
11 октября 2019 в 16:20
2

@RobertFraser Я никогда не слышал, чтобы кто-нибудь утверждал, что Галилей изобрел гелиоцентрическую модель. Его всегда приписывают Копернику. Вы это имели в виду?

Ответы (35)

avatar
A. Rex
17 ноября 2013 в 23:39
778

Я придумал метод, который работает на ~ 35% быстрее, чем ваш 6-битный код + Carmack + sqrt, по крайней мере, с моим процессором (x86) и языком программирования (C / C ++). Ваши результаты могут отличаться, особенно потому, что я не знаю, как будет действовать фактор Java.

Мой подход состоит из трех частей:

  1. Во-первых, отфильтруйте очевидные ответы. Это включает отрицательные числа и последние 4 бита. (Я обнаружил, что просмотр последних шести не помог.) Я также отвечаю «да» на 0. (Читая приведенный ниже код, обратите внимание, что я ввел int64 x.)
    if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) )
        return false;
    if( x == 0 )
        return true;
  2. Затем проверьте, является ли это квадратом по модулю 255 = 3 * 5 * 17. Поскольку это произведение трех различных простых чисел, только около 1/8 остатков по модулю 255 являются квадратами. Однако, по моему опыту, вызов оператора по модулю (%) стоит дороже, чем получаемая выгода, поэтому я использую битовые трюки с 255 = 2 ^ 8-1 для вычисления остатка. (Хорошо это или плохо, но я не использую трюк чтения отдельных байтов из слова, а только побитовые сдвиги и.)
    int64 y = x;
    y = (y & 4294967295LL) + (y >> 32); 
    y = (y & 65535) + (y >> 16);
    y = (y & 255) + ((y >> 8) & 255) + (y >> 16);
    // At this point, y is between 0 and 511.  More code can reduce it farther.
    
    Чтобы действительно проверить, является ли остаток квадратом, я ищу ответ в предварительно вычисленной таблице.
    if( bad255[y] )
        return false;
    // However, I just use a table of size 512
    
  3. Наконец, попробуйте вычислить квадратный корень, используя метод, аналогичный лемме Хензеля. (Я не думаю, что это применимо напрямую, но оно работает с некоторыми изменениями.) Перед тем, как сделать это, я делю все степени двойки с помощью двоичного поиска:
    if((x & 4294967295LL) == 0)
        x >>= 32;
    if((x & 65535) == 0)
        x >>= 16;
    if((x & 255) == 0)
        x >>= 8;
    if((x & 15) == 0)
        x >>= 4;
    if((x & 3) == 0)
        x >>= 2;
    На этом этапе, чтобы наше число было квадратом, оно должно быть 1 по модулю 8.
    if((x & 7) != 1)
        return false;
    Основная структура леммы Гензеля такова. (Примечание: непроверенный код; если он не работает, попробуйте t = 2 или 8.)
    int64 t = 4, r = 1;
    t <<= 1; r += ((x - r * r) & t) >> 1;
    t <<= 1; r += ((x - r * r) & t) >> 1;
    t <<= 1; r += ((x - r * r) & t) >> 1;
    // Repeat until t is 2^33 or so.  Use a loop if you want.
    Идея состоит в том, что на каждой итерации вы добавляете один бит к r, «текущему» квадратному корню из x; каждый квадратный корень является точным по модулю все большей и большей степени 2, а именно t / 2. В конце концов, r и t / 2-r будут квадратными корнями из x по модулю t / 2. (Обратите внимание, что если r является квадратным корнем из x, то также и -r. Это верно даже по модулю чисел, но будьте осторожны, по модулю некоторых чисел вещи могут иметь даже более двух квадратных корней; в частности, это включает степени двойки. ) Поскольку наш фактический квадратный корень меньше 2 ^ 32, в этот момент мы можем просто проверить, являются ли r или t / 2-r действительными квадратными корнями. В моем фактическом коде я использую следующий модифицированный цикл:
    int64 r, t, z;
    r = start[(x >> 3) & 1023];
    do {
        z = x - r * r;
        if( z == 0 )
            return true;
        if( z < 0 )
            return false;
        t = z & (-z);
        r += (z & t) >> 1;
        if( r > (t >> 1) )
            r = t - r;
    } while( t <= (1LL << 33) );
    Ускорение здесь достигается тремя способами: предварительно вычисленное начальное значение (эквивалентное ~ 10 итерациям цикла), более ранний выход из цикла и пропуск некоторых значений t. В последней части я смотрю на z = r - x * x и устанавливаю t как наибольшую степень двойки, делящую 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;
}
Kip
12 января 2009 в 21:47
7

Вау! Я попытаюсь преобразовать это в Java и провести сравнение, а также проверить точность результатов. Я дам вам знать, что я нашел.

Kip
16 января 2009 в 20:13
2

Проверка всех значений невозможна, но проверка подозрительных значений (+/- 1 от очень больших полных квадратов) оказалась точной. При запуске первого миллиарда целых чисел это заняло только 34% времени, требуемого исходным алгоритмом.

A. Rex
16 января 2009 в 20:50
0

Потрясающий! Я рад, что у тебя все получилось. Одно отличие C (++) и Java заключается в том, что Java проверяет границы при поиске в массиве, поэтому я подумал, что вы можете попасть туда.

Dimitre Novatchev
27 марта 2009 в 23:44
0

Кажется, это возвращает только истину / ложь, а вот сам квадратный корень вернуть будет сложно?

ShreevatsaR
25 мая 2009 в 02:36
93

Вау, это красиво. Я уже видел подъем Хензеля (вычисление корней многочленов по простому модулю), но я даже не осознавал, что лемму можно аккуратно опустить полностью для вычисления квадратных корней чисел; это ... воодушевляет :)

A. Rex
3 декабря 2009 в 23:50
0

@ Димитр Новачев: Нет, это было бы не так уж сложно. Если число является точным квадратом, то его квадратный корень равен r, умноженному на некоторую степень двойки, которая может быть определена при делении на степени 4.

PeterT
11 января 2011 в 15:08
0

@A. Rex: HotSpot может при определенных обстоятельствах исключить проверки границ coderhelper.com/questions/4469483/bounds-checking-in-java, так что попадания, вероятно, удается избежать.

orlp
17 сентября 2012 в 08:20
0

@A. Рекс: Я могу ошибаться, но разве 9 не идеальный квадрат? И разве if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) ) return false; не отфильтровывает это как несуществующее? И аналогично для всех остальных неровных полных квадратов?

primo
2 декабря 2012 в 07:56
3

@nightcracker Это не так. 9 < 0 => false, 9&2 => 0, 9&7 == 5 => false, 9&11 == 8 => false.

Jason C
17 марта 2014 в 03:46
61

Чуть позже Маартинус опубликовал решение, которое в 2 раза быстрее (и намного короче), и оно, похоже, не пользуется большой популярностью.

maaartinus
13 июня 2014 в 19:21
1

@ A.Rex AFAIK, финальный тест t <= (1LL << 33) бесполезен, так как вы либо получаете квадратный корень, либо все равно перескакиваете. Я уронил его, и он работает (но, может быть, есть проблема с номерами, которые я не пробовал?).

user1914292
7 октября 2014 в 17:26
3

Похоже, что большое преимущество в скорости в различных решениях достигается за счет фильтрации очевидных квадратов. Кто-нибудь сравнивал ситуацию с фильтрацией с помощью решения Maartinus, а затем просто использовал функцию sqrt как встроенную функцию?

chux - Reinstate Monica
21 мая 2018 в 08:30
1

LL в y & 4294967295LL не требуется.

Maëlan
29 сентября 2019 в 15:31
1

«Затем проверьте, является ли это квадратом по модулю 255 = 3 * 5 * 17. Поскольку это произведение трех различных простых чисел, только около 1/8 остатков по модулю 255 являются квадратами». На самом деле пропорция квадратов по модулю 255 составляет 54/255 ≃ 0,212, что намного больше, чем 1/8 = 0,125 (потому что доля квадратов по модулю каждого из простых множителей немного больше 1/2). Но учтите, что вы не ограничены простыми числами. Соотношение квадратов по модулю 256 составляет 44/256 ≃ 0,172, и вычисление по модулю 256 намного удобнее.

Maëlan
29 сентября 2019 в 15:50
1

По сути, это одна из вещей, которую делает ответ maaartinus, за исключением того, что он использует 64 вместо 256 (что дает более компактную предварительно вычисленную таблицу с лучшим поведением кеша, но при этом довольно эффективно отфильтровывает неквадраты, как пропорцию квадратов по модулю 64 12/64 ≃ 0,188).

avatar
Steve Storck
15 февраля 2021 в 18:27
1

Вот самый простой и лаконичный способ, хотя я не знаю, как он сравнивается с точки зрения циклов процессора. Это отлично работает, если вы хотите знать, является ли корень целым числом. Если вам действительно важно, является ли это целым числом, вы также можете это выяснить. Вот простая (и чистая) функция:

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

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

Если вам не нужна микрооптимизация, этот ответ лучше с точки зрения простоты и ремонтопригодности. Если вы будете вычислять отрицательные числа, вам нужно будет обработать это соответствующим образом и отправить абсолютное значение в функцию. Я включил небольшую оптимизацию, потому что ни один идеальный квадрат не имеет разряда десятков 2, 3, 7 или 8 из-за квадратичного остатка по модулю 10.

На моем ЦП выполнение этого алгоритма на 0–10 000 000 занимало в среднем 1000–1100 наносекунд на вычисление.

Если вы выполняете меньшее количество вычислений, более ранние вычисления займут немного больше времени.

У меня был отрицательный комментарий, что моя предыдущая правка не работала для больших чисел. OP упоминает длинные позиции, а наибольший точный квадрат, который является длинным, равен 9223372030926249001, поэтому этот метод работает для всех длинных позиций.

Stefan Reich
4 декабря 2017 в 12:52
2

Я думаю, вы имеете в виду (long) Math.pow(roundedRoot, 2)

Steve Storck
5 декабря 2017 в 11:03
0

Я обновил это решение / предложение, чтобы это был самый простой способ понять это. Интересно, как он будет сравниваться с некоторыми пользовательскими решениями с точки зрения тестов.

aventurin
13 октября 2018 в 21:44
4

Ваш метод возвращает true для 10_000_000_000_000_000L и 10_000_000_000_000_001L, что доказывает, что это не так.

Steve Storck
15 февраля 2021 в 18:32
0

@aventurin Я изменил свой ответ, чтобы учесть вашу точную оценку моей предыдущей попытки. Если вы проголосовали против моего комментария, пожалуйста, подумайте еще раз. Спасибо!

avatar
maaartinus
20 июня 2020 в 09:12
426

Я довольно опаздываю на вечеринку, но надеюсь дать лучший ответ; короче и (при условии, что мой тест верен) также намного быстрее.

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, поэтому нет затрат на доступ к массиву (косвенные проверки и проверки границ). Для равномерно случайного long вероятность завершения здесь составляет 81,25%.

Второй тест выявляет все числа, имеющие нечетное количество двоек в их факторизации. Метод Long.numberOfTrailingZeros очень быстрый, поскольку он преобразуется в одну инструкцию i86 с помощью JIT.

После отбрасывания конечных нулей третий тест обрабатывает числа, оканчивающиеся на 011, 101 или 111 в двоичном формате, которые не являются полными квадратами. Он также обрабатывает отрицательные числа и 0.

Последний тест возвращается к double арифметике. Поскольку double имеет только 53 бита мантиссы, преобразование из long в double включает округление для больших значений. Тем не менее, тест верен (кроме случаев, когда доказательство неверно).

Попытка реализовать идею mod255 не увенчалась успехом.

dfeuer
11 июля 2014 в 01:04
4

Это неявное маскирование значения сдвига немного ... зло. Вы хоть представляете, почему это указано в спецификации Java?

dfeuer
11 июля 2014 в 01:08
0

В частности, вопрос о вашем коде: зачем вам проверять, что нечетное число заканчивается 001? Разве это не обрабатывается тестом goodMask?

maaartinus
11 июля 2014 в 14:55
7

@dfeuer Думаю, есть две причины: 1. Переходить на большее количество не имеет смысла. 2. Это похоже на то, как работает HW, и любой, кто использует побитовые операции, заинтересован в производительности, поэтому делать что-либо еще было бы неправильно. - Тест goodMask делает это, но делает это до сдвига вправо. Так что вам придется повторить это, но так проще и, AFAIK, немного быстрее и одинаково хорошо.

dfeuer
11 июля 2014 в 15:11
0

Я упустил тот факт, что вы сдвигали с нуля там. Полагаю, подсчет конечных нулей слишком дорого обходится в первую очередь? Какие архитектуры используют для сдвигов только младшие биты?

maaartinus
11 июля 2014 в 15:24
3

@dfeuer Для теста важно дать ответ как можно скорее, а сам счетчик нулевых значений не дает ответа; это всего лишь подготовительный шаг. i86 / amd64 сделай это. Понятия не имею о небольших процессорах в мобильных телефонах, но в худшем случае Java должна сгенерировать для них инструкцию AND, что, безусловно, проще, чем наоборот.

dfeuer
13 июля 2014 в 10:29
1

Пожалуйста, взгляните на мой ответ. Если бы вы могли подключить его к своей тестовой системе, я был бы очень благодарен.

durron597
13 марта 2015 в 23:42
1

Можете ли вы опубликовать полные результаты тестов, а не только эти 5?

Sebastian
4 августа 2016 в 16:30
0

Третий тест if ((x&7) != 1 | x <= 0) return x == 0; может быть if ((x&7) != 1 | x < 0) return x == 0; (случай x == 0 уже обнаружен (x&7) != 1). Я не уверен, ускоряет ли это вычисление, но это делает более очевидным, что вы можете удалить второй тест, если ваш ввод положительный: if ((x&7) != 1) return x == 0; Я знаю, что в java нет беззнаковых long, но это может быть полезно для люди переносят этот код на другие языки (как я сейчас делаю).

maaartinus
4 августа 2016 в 16:57
0

@ Себастьян, я думаю, ты прав. Однако IIRC JIT сделал из этого нечто совершенно отличное от того, на что я надеялся, так что это может улучшить или ухудшить ситуацию. Проблема с JIT заключается в том, что скомпилированный код зависит от данных, которыми он был загружен, поэтому агрегирования двух случаев не произошло, поскольку я не использовал (почти нет?) Отрицательных входных данных в моем тесте.

maaartinus
4 августа 2016 в 16:59
2

@Sebastian.Пожалуй, лучший тест: if ((x & (7 | Integer.MIN_VALUE)) != 1) return x == 0;.

Sebastian
4 августа 2016 в 17:02
1

@maaartinus: Я согласен :), а затем, конечно, поместите (7 | Long.MIN_VALUE) в константу (или предположите, что компилятор достаточно умен, чтобы сделать это за вас)

chux - Reinstate Monica
23 марта 2017 в 14:51
4

«Поскольку double имеет только 56-битную мантиссу» -> я бы сказал, что у него более вероятно 53-битная единица. Также

maaartinus
30 июля 2017 в 22:36
1

@Sebastian Это должно быть умно, поскольку это постоянная времени компиляции в соответствии с JLS.

Olivier Grégoire
1 февраля 2018 в 10:49
0

@maaartinus Dropbox говорит: «К сожалению, этого файла здесь больше нет. Возможно, он был перемещен или сделан личным». Вы бы разместили это здесь вместо этого? Stackoverflow поддерживает сообщения размером до 40 КБ. Не помещается ли файл?

maaartinus
1 февраля 2018 в 11:05
0

@ OlivierGrégoire Простите за это. Сделаю это через две недели, когда снова окажусь на нужной машине (она офлайн, извините!). Файл точно подходит. Все ссылки на мой Dropbox сломались, это печально.

maaartinus
15 февраля 2018 в 20:21
0

@ OlivierGrégoire Вместо этого я исправил ссылку. В файле 22k и он подойдет, но я думаю, что текущая ссылка прослужит несколько лет. Я предпочитаю не публиковать его здесь, так как он довольно длинный и скучный, но не стесняйтесь редактировать, если вы считаете иначе.

maaartinus
25 февраля 2018 в 23:17
0

@ OlivierGrégoire Я просто использую его для projecteuler.net/problem=621, и печально то, что использование ничего, кроме теста с плавающей запятой, одинаково хорошо. :(

Nuwan Harshakumara Piyarathna
26 апреля 2020 в 09:25
0

Как я могу использовать это для очень больших чисел (BigInteger). Тогда какое будет значение маски? Как его рассчитать?

maaartinus
26 апреля 2020 в 22:54
0

@NuwanHarshakumaraPiyarathna И goodMask, и numberOfTrailingZeros можно использовать одинаково (одинаковое значение goodMask).

HiddenBabel
26 июля 2020 в 23:06
0

@maaartinus Как тест goodMask улавливает 81% всех длинных позиций? Разве goodMask << x не равно 0 для всех x > 64?

Aleksandr Dubinsky
8 августа 2021 в 15:47
0

@HiddenBabel Нет, потому что в спецификации языка Java сказано: «Если расширенный тип левого операнда длинный, то в качестве расстояния сдвига используются только шесть младших битов правого операнда. Это как если бы правый операнд был подвергнут поразрядному логическому оператору AND & (§15.22.1) со значением маски 0x3f (0b111111). Фактически используемое расстояние сдвига всегда находится в диапазоне от 0 до 63 включительно ». docs.oracle.com/javase/specs/jls/se11/jls11.pdf

avatar
Sajjad Ali Vayani
1 ноября 2019 в 08:28
2

Квадратный корень числа, учитывая, что число является точным квадратом.

Сложность - log (n)

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

public static int calculateSquareRoot(int number) {

    int sum=1;
    int count =1;
    int squareRoot=1;
    while(sum<number) {
        count+=2;
        sum+=count;
        squareRoot++;
    }
    return squareRoot;
}
cisnjxqu
15 декабря 2020 в 15:40
0

Я не думаю, что сложность правильная. Сложность должна представлять собой количество квадратов, меньшее или равное n, или приблизительно O (sqrt (n)).

avatar
Kibbee
2 июля 2019 в 00:37
38

Я не уверен, будет ли это быстрее или даже точнее, но вы могли бы использовать алгоритм Магический квадратный корень Джона Кармака, чтобы быстрее вычислить квадратный корень. Вероятно, вы могли бы легко проверить это для всех возможных 32-битных целых чисел и убедиться, что вы действительно получили правильные результаты, поскольку это всего лишь приближение. Однако теперь, когда я думаю об этом, использование двойников также приближается, поэтому я не уверен, как это повлияет на игру.

jalf
17 ноября 2008 в 15:22
11

Я считаю, что уловка Кармака в наши дни довольно бессмысленна. Встроенная инструкция sqrt намного быстрее, чем раньше, поэтому вам может быть лучше просто выполнить обычный квадратный корень и проверить, является ли результат int. Как всегда, протестируйте его.

luke
17 ноября 2008 в 18:45
0

двойники всегда могут точно представлять целые числа в своем диапазоне

Kip
17 ноября 2008 в 19:55
4

Это разрывы, начиная с n = 410881, магическая формула Джона Кармака возвращает 642,00104, когда фактический квадратный корень равен 641.

finnw
7 января 2010 в 11:57
12

Недавно я использовал уловку Кармака в Java-игре, и она оказалась очень эффективной, давая ускорение примерно на 40%, так что она по-прежнему полезна, по крайней мере, в Java.

Robert Fraser
6 мая 2010 в 10:27
0

@finnw - + 40% фактической частоты кадров или только в функции sqrt? На самом деле я очень удивлен по этому поводу, поскольку большинство игр, в которые я играл (и та, которую я сделал в XNA), в любом случае были привязаны к графическому процессору, а не к процессору (хотя я знаю, что это может отличаться в зависимости от используемой машины. , бла бла бла)

finnw
6 мая 2010 в 10:48
3

@Robert Fraser: Да + 40% к общей частоте кадров. В игре была система физики элементарных частиц, которая занимала почти все доступные циклы процессора, в которой преобладала функция квадратного корня и функция округления до ближайшего целого числа (которую я также оптимизировал, используя аналогичный хакерский прием).

Antimony
27 августа 2013 в 14:28
0

@luke, но они не могут представлять длинные числа больше 2 ^ 53.

maaartinus
19 мая 2014 в 21:07
0

@Antimony Верно, но это работает, если все сделано правильно, см. Мое решение ниже.

Daniel Gray
2 июля 2019 в 00:38
0

Ссылка была исправлена ​​путем указания ее на снимок Wayback Machine примерно в то время, когда это было опубликовано :)

avatar
bgiles
25 июня 2019 в 22:02
7

Project Euler упоминается в тегах, и многие проблемы в нем требуют проверки номеров >> 2^64. Большинство упомянутых выше оптимизаций не работают легко, когда вы работаете с 80-байтовым буфером.

Я использовал java BigInteger и слегка измененную версию метода Ньютона, который лучше работает с целыми числами. Проблема заключалась в том, что точные квадраты n^2 сходились к (n-1) вместо n, потому что n^2-1 = (n-1)(n+1) и окончательная ошибка была всего на один шаг ниже конечного делителя, и алгоритм завершился. Это было легко исправить, добавив единицу к исходному аргументу перед вычислением ошибки. (Добавьте два для кубических корней и т. Д.)

Одним из хороших свойств этого алгоритма является то, что вы можете сразу определить, является ли число точным квадратом - окончательная ошибка (не исправление) в методе Ньютона будет равна нулю. Простая модификация также позволяет быстро вычислить floor(sqrt(x)) вместо ближайшего целого числа. Это удобно при решении нескольких задач Эйлера.

user2975337
14 июля 2015 в 02:27
1

То же самое я думал об этих алгоритмах, которые плохо переносятся в буферы с множественной точностью. Так что подумал, что воткну вот это ... Я на самом деле нашел тест на вероятностный квадрат с лучшей асимптотической сложностью для огромных чисел ... где приложения теории чисел нередко оказываются. Не знаком с Project Euler ... выглядит интересно.

avatar
19 января 2019 в 13:44
1

Возможно, лучший алгоритм для решения проблемы - это алгоритм быстрого целочисленного квадратного корня https://coderhelper.com/a/51585204/5191852

Там @Kde утверждает, что трех итераций метода Ньютона будет достаточно для точности ± 1 для 32-битных целых чисел. Конечно, для 64-битных целых чисел требуется больше итераций, может быть 6 или 7.

avatar
27 декабря 2018 в 17:13
2

Вот решение "разделяй и властвуй".

Если квадратный корень натурального числа (number) является натуральным числом (solution), вы можете легко определить диапазон для solution на основе количества цифр number:

  • number имеет 1 цифру: solution в диапазоне = 1–4
  • number имеет 2 цифры: solution в диапазоне = 3-10
  • number состоит из 3 цифр: solution в диапазоне = 10-40
  • number имеет 4 цифры: solution в диапазоне = 30-100
  • number имеет 5 цифр: solution в диапазоне = 100-400

Обратите внимание на повторение?

Вы можете использовать этот диапазон в подходе двоичного поиска, чтобы узнать, существует ли solution, для которого:

number == solution * solution

Вот код

Вот мой класс SquareRootChecker

public class SquareRootChecker {

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

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

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

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

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

}

А вот пример того, как его использовать.

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

long notSquare = square + 1;
squareRootChecker = new SquareRootChecker(notSquare);
System.out.println(notSquare + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677490: false"
Jack Giffin
23 января 2020 в 21:45
2

Мне нравится эта концепция, но я хотел бы вежливо указать на главный недостаток: числа представлены в двоичной системе с основанием 2. Преобразование основания 2 в основание 10 через toString - невероятно дорогая операция по сравнению с побитовыми операторами. Таким образом, чтобы удовлетворить цель вопроса - производительность - вы должны использовать побитовые операторы вместо строк с базой 10. Опять же, мне очень нравится ваша концепция. Тем не менее, ваша реализация (в ее нынешнем виде) является самым медленным из всех возможных решений, опубликованных для этого вопроса.

avatar
27 декабря 2018 в 02:42
1

Вычисление квадратных корней методом Ньютона происходит ужасно быстро ... при условии, что начальное значение разумно. Однако разумного начального значения нет, и на практике мы заканчиваем делением пополам и поведением журнала (2 ^ 64).
Чтобы быть действительно быстрым, нам нужен быстрый способ получить разумное начальное значение, а это означает, что нам нужно перейти на машинный язык. Если процессор предоставляет такую ​​команду, как POPCNT в Pentium, которая считает ведущие нули, мы можем использовать это для получения начального значения с половиной значащих битов. С осторожностью мы можем найти фиксированное количество шагов Ньютона, которого всегда будет достаточно. (Таким образом, отпадает необходимость в цикле и очень быстрое выполнение.)

Второе решение идет через средство с плавающей запятой, которое может иметь быстрое вычисление sqrt (как сопроцессор i87). Даже переход через exp () и log () может быть быстрее, чем Ньютон выродился в двоичный поиск. В этом есть непростой аспект - зависимый от процессора анализ того, что и если впоследствии необходимо доработать.

Третье решение решает несколько иную проблему, но о нем стоит упомянуть, потому что ситуация описана в вопросе. Если вы хотите вычислить большое количество квадратных корней для чисел, которые немного отличаются, вы можете использовать итерацию Ньютона, если вы никогда не повторно инициализируете начальное значение, а просто оставите его там, где остановился предыдущий расчет. Я успешно использовал это как минимум в одной задаче Эйлера.

MWB
27 декабря 2018 в 17:58
0

Получить хорошую оценку не так уж сложно. Вы можете использовать количество цифр числа, чтобы оценить нижнюю и верхнюю границу решения. См. Также мой ответ, в котором я предлагаю решение «разделяй и властвуй».

Albert van der Horst
29 декабря 2018 в 16:27
0

В чем разница между POPCNT и подсчетом количества цифр? За исключением того, что вы можете сделать POPCNT за одну наносекунду.

avatar
17 октября 2018 в 22:49
2

Метод Ньютона с целочисленной арифметикой

Если вы хотите избежать нецелочисленных операций, вы можете использовать метод ниже. Он в основном использует метод Ньютона, модифицированный для целочисленной арифметики.

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

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

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

Эта реализация не может конкурировать с решениями, использующими Math.sqrt. Однако его производительность можно улучшить, используя механизмы фильтрации, описанные в некоторых других сообщениях.

avatar
26 сентября 2018 в 16:32
-1

Не уверен, что это самый быстрый способ, но я наткнулся на него (давным-давно в старшей школе), когда мне было скучно и я играл со своим калькулятором во время урока математики. В то время я был действительно поражен, как это работает ...

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

private static boolean isIntRootHelper(int number, int index) {
    if (number == index) {
        return true;
    }
    if (number < index) {
        return false;
    }
    else {
        return isIntRootHelper(number - 2 * index, index + 1);
    }
}
Albert van der Horst
27 декабря 2018 в 11:57
0

К сожалению, это алгоритм O (N ^ .5), поэтому он действительно плохо влияет на скорость и длится вечно для 63-битных чисел, которые могут быть введены. Я изменил свое одобрение на отрицательное. О чем я думал, когда проголосовал за это. По крайней мере, идея верна, но я ее не тестировал.

avatar
mrzl
6 апреля 2018 в 09:07
15

Я хочу, чтобы эта функция работала со всеми положительные 64-битные целые числа со знаком

Math.sqrt() работает с двойными значениями в качестве входных параметров, поэтому вы не получите точных результатов для целых чисел больше 2 ^ 53 .

Kip
6 января 2009 в 14:33
5

Я действительно проверил ответ на всех полных квадратах больше 2 ^ 53, а также на всех числах от 5 под каждым квадратом до 5 над каждым квадратом, и получил правильный результат. (ошибка округления исправляется, когда я округляю ответ sqrt до длинного, затем возводите это значение в квадрат и сравниваю)

maaartinus
8 сентября 2013 в 19:12
2

@ Кип: Думаю, я доказал, что работает.

mwfearnley
22 апреля 2014 в 00:54
0

Результаты не совсем точны, но точнее, чем вы думаете. Если мы предположим, что после преобразования в удвоение и после квадратного корня мы предположим не менее 15 точных цифр, то этого достаточно, потому что нам нужно не более 11: 10 цифр для 32-битного квадратного корня и меньше 1 для десятичного разряда, потому что +0,5 оборота до ближайшего.

gnasher729
1 мая 2014 в 23:27
3

Math.sqrt () не совсем точен, но это не обязательно. В самом первом посте tst - это целое число, близкое к sqrt (N). Если N не является квадратом, тогда tst * tst! = N, независимо от значения tst. Если N - точный квадрат, тогда sqrt (N) <2 ^ 32, и пока sqrt (N) вычисляется с ошибкой <0,5, все в порядке.

avatar
nabam serbang
5 марта 2018 в 21:50
6

Учитывая общую длину в битах (хотя здесь я использовал конкретный тип), я попытался разработать упрощенный алгоритм, как показано ниже. Изначально требуется простая и очевидная проверка на 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;  
}  
nabam serbang
18 декабря 2010 в 15:06
0

@ Кип: Некоторые проблемы с моим браузером.

avatar
dfeuer
13 июля 2014 в 19:24
10

Следующее упрощение решения 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;

повлияет на производительность.

maaartinus
16 июля 2014 в 11:45
2

Результаты: , здесь. Удаление первого теста - это плохо, поскольку в большинстве случаев он решает довольно дешево. Источник в моем ответе (обновлен).

avatar
Colonel Panic
16 октября 2013 в 10:18
12

Целочисленная задача заслуживает целочисленного решения. Таким образом

Выполните двоичный поиск (неотрицательных) целых чисел, чтобы найти наибольшее целое число t такое, что t**2 <= n. Затем проверьте, является ли r**2 = n точным. Это занимает время O (log n).

Если вы не знаете, как выполнять двоичный поиск положительных целых чисел, потому что набор неограничен, это легко. Вы начинаете с вычисления возрастающей функции f (выше f(t) = t**2 - n) по степеням двойки. Когда вы видите, что он становится положительным, вы нашли верхнюю границу. Затем вы можете выполнить стандартный двоичный поиск.

user2975337
14 июля 2015 в 02:05
0

Фактически время будет не менее O((log n)^2), потому что умножение не является постоянным временем, а фактически имеет нижнюю границу O(log n), что становится очевидным при работе с большими числами с множественной точностью. Но объем этой вики кажется 64-битным, так что, возможно, это nbd.

Alnitak
1 июня 2021 в 11:52
0

Умножение целых чисел размером с собственное слово составляет O (1) на многих современных процессорах.

avatar
13 июня 2013 в 17:42
25

Я провел собственный анализ нескольких алгоритмов в этом потоке и получил некоторые новые результаты. Вы можете увидеть эти старые результаты в истории редактирования этого ответа, но они неточны, так как я допустил ошибку и потратил время на анализ нескольких алгоритмов, которые не близки. Однако, извлекая уроки из нескольких разных ответов, у меня теперь есть два алгоритма, которые сокрушают «победителя» этой ветки. Вот основная вещь, которую я делаю не так, как все остальные:

// 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. Однако он может увеличить время выполнения, если многие из протестированных чисел имеют значительную степень двойки.

Ниже приведены следующие алгоритмы:

  • Интернет - опубликованный ответ Кипа
  • Дюррон - Мой измененный ответ с использованием однопроходного ответа в качестве основы
  • DurronTwo - Мой измененный ответ с использованием двухпроходного ответа (от @JohnnyHeggheim) с некоторыми другими небольшими изменениями.

Вот пример времени выполнения, если числа генерируются с использованием Math.abs(java.util.Random.nextLong())

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

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

vm: java
trial: 0

А вот пример среды выполнения, если она работает только на первом миллионе длинных:

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

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

vm: java
trial: 0

Как видите, DurronTwo лучше подходит для больших входных данных, потому что он очень часто использует магический трюк, но затирается по сравнению с первым алгоритмом и Math.sqrt, потому что числа намного меньше. Между тем, более простой Durron является огромным победителем, потому что ему никогда не нужно много раз делить на 4 в первом миллионе чисел.

Вот Durron:

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

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

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

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

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

И DurronTwo

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

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

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

И мой тестовый комплект: (Требуется штангенциркуль 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
Peter Cordes
21 августа 2015 в 02:05
4

Гигантская таблица поиска не кажется хорошей идеей. Промах в кэше происходит медленнее (~ 100–150 циклов), чем аппаратная инструкция sqrt x86 (~ 20 циклов). Что касается пропускной способности, вы можете выдержать множество выдающихся промахов кеша, но вы все равно удаляете другие полезные данные. Огромная таблица поиска того стоила бы, только если бы она была НАМНОГО быстрее, чем любой другой вариант, и эта функция была бы основным фактором производительности всей вашей программы.

Swiss Frank
30 октября 2018 в 19:09
0

@Peter Cordes, сначала у вас должно быть несколько промахов в кеше, тогда все будет в кеше, верно?

Peter Cordes
30 октября 2018 в 22:13
1

@SwissFrank: проверка методом точных квадратов только , что делает ваша программа? Таблица поиска может хорошо выглядеть в микробенчмарке, который вызывает ее многократно в замкнутом цикле, но в реальной программе, имеющей другие данные в своем рабочем наборе, это нехорошо.

Peter Cordes
30 октября 2018 в 22:18
1

Битовая карта из битов 0x1FFFFFE занимает 4 мегабайта , если она хранится как упакованная битовая карта. Кэш L3 попадание на современном настольном компьютере Intel имеет задержку> 40 циклов, и даже хуже на большом Xeon; дольше, чем аппаратная задержка sqrt + mul. Если сохранить как байт -карту с 1 байтом на значение, это около 32 МБ; больше, чем кэш L3 чего-либо, кроме многоядерного Xeon, где все ядра используют один огромный кеш. Таким образом, если ваши входные данные имеют равномерное случайное распределение по достаточно большому диапазону входных данных, вы получите много промахов кэша L2 даже в тесном цикле. (частный L2 на ядро ​​на Intel составляет всего 256 КБ, с задержкой ~ 12 циклов.)

Swiss Frank
31 октября 2018 в 09:36
0

@Peter Cordes, оригинальный плакат, кажется, говорит, что это основная часть его программы. Как математик-любитель, он может не запускать какие-либо другие процессы во время этого процесса, поэтому можно ожидать, что кеш будет принадлежать самому себе. Однако, если я понимаю ваши числа, если вы не можете получить его в L2 - и вы не можете - тогда sqrt будет быстрее, чем переход на L3. Не в тему, но есть ли у вас удобный справочник по времени доступа на различных процессорах?

Peter Cordes
31 октября 2018 в 09:47
1

@SwissFrank: О, если все, что вы делаете, это проверка корня, тогда есть потенциал для этого с растровым изображением, чтобы получить попадания L3. Я смотрел на задержку, но сразу может быть много промахов, поэтому пропускная способность потенциально хорошая. OTOH, SIMD sqrtps пропускная способность или даже sqrtpd (двойная точность) неплохо для Skylake, но не намного лучше, чем задержка на старых процессорах. В любом случае 7-cpu.com/cpu/Haswell.html содержит несколько хороших экспериментальных чисел и страниц для других процессоров. Руководство по микроархитектуре Agner Fog в формате PDF содержит некоторые значения задержки кэша для архивов Intel и AMD: agner.org/optimize

Peter Cordes
31 октября 2018 в 09:52
1

Использование x86 SIMD из Java является проблемой, и к тому времени, когда вы добавите стоимость преобразования int-> fp и fp-> int, вполне вероятно, что растровое изображение могло быть лучше. Вам нужна точность double, чтобы избежать округления некоторого целого числа за пределами диапазона + -2 ^ 24 (поэтому 32-битное целое число может быть вне этого диапазона), а sqrtpd медленнее, чем sqrtps, а также обрабатывает только половину. много элементов на инструкцию (на вектор SIMD).

Swiss Frank
31 октября 2018 в 14:45
0

> «к тому времени, когда вы добавите стоимость преобразования int-> fp и fp-> int, вполне вероятно, что растровое изображение могло быть лучше» Только что проверил свой профиль, много поклонов! Одна идея, которая приходит в голову, - это запуск вашего цикла в int и double бок о бок, используя double там, где вам это нужно, и int, где вам это нужно. Я совершенно не проверял, подходит ли это вообще для более широкой дискуссии, но это всего лишь одна вещь, которую я сделал. Кстати, я занимаюсь программным обеспечением для синтезаторов и очень хочу попробовать SIMD в одном из аспектов ...

avatar
13 апреля 2012 в 06:18
54

Я думал о тех ужасных временах, которые провел на курсе численного анализа.

И потом я вспомнил, что в исходном коде 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!

Он написан на 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 операция умножения) и заменяет его несколькими фиксированными операциями умножения.

Kip
17 ноября 2008 в 19:56
10

Следует отметить, что это возвращает 1 / sqrt (число), а не sqrt (число). Я провел некоторое тестирование, и это не удается, начиная с n = 410881: магическая формула Джона Кармака возвращает 642,00104, когда фактический квадратный корень равен 641.

user21037
2 декабря 2008 в 10:24
12

Вы можете посмотреть статью Криса Ломонца о быстрых обратных квадратных корнях: lomont.org/Math/Papers/2003/InvSqrt.pdf Здесь используется та же техника, что и здесь, но с другим магическим числом. В документе объясняется, почему было выбрано магическое число.

user21037
2 декабря 2008 в 10:26
4

Кроме того, yond3d.com/content/articles/8 и yond3d.com/content/articles/15 проливают свет на происхождение этого метода. Его часто приписывают Джону Кармаку, но кажется, что исходный код (возможно) был написан Гэри Таролли, Грегом Уолшем и, возможно, другими.

Antimony
27 августа 2013 в 14:29
3

Также вы не можете печатать поплавки и целые числа в Java.

corsiKa
27 мая 2015 в 17:50
12

@ Сурьма, кто говорит? FloatToIntBits и IntToFloatBits существуют с java 1.0.2.

avatar
5 декабря 2011 в 04:29
5

Я проверил все возможные результаты, когда наблюдались последние n бит квадрата. Последовательно исследуя большее количество битов, можно исключить до 5/6 входов. На самом деле я разработал это для реализации алгоритма факторизации Ферма, и это очень быстро.

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

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

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

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

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

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

Последний бит псевдокода можно использовать для расширения тестов, чтобы исключить больше значений. Вышеупомянутые тесты предназначены для k = 0, 1, 2, 3

  • a имеет форму (3 << 2k) - 1
  • b имеет форму (2 << 2k)
  • c имеет вид (2 << 2k + 2) - 1
  • d имеет вид (2 << 2k - 1) * 10

    Сначала он проверяет, есть ли квадратная невязка с модулями степени двойки, затем проверяет на основе окончательного модуля, а затем использует Math.sqrt для выполнения окончательного теста. Я пришел к идее из верхнего поста и попытался развить ее. Буду признателен за любые комментарии или предложения.

    Обновление: Используя тест по модулю (modSq) и базе модуля 44352, мой тест выполняется в 96% от времени в обновлении OP для чисел до 1 000 000 000.

  • avatar
    6 мая 2010 в 16:37
    8

    Это самая быстрая реализация Java, которую я мог придумать, с использованием комбинации методов, предложенных другими участниками этого потока.

    • Тест Mod-256
    • Неточный тест mod-3465 (избегает целочисленного деления за счет некоторых ложных срабатываний)
    • Квадратный корень с плавающей запятой, округлить и сравнить с входным значением

    Я тоже экспериментировал с этими модификациями, но они не улучшили производительность:

    • Дополнительный тест mod-255
    • Деление входного значения на степени 4
    • Быстрый обратный квадратный корень (для работы с высокими значениями N требуется 3 итерации, что достаточно, чтобы сделать его медленнее, чем аппаратная функция извлечения квадратного корня)

    public class SquareTester {
    
        public static boolean isPerfectSquare(long n) {
            if (n < 0) {
                return false;
            } else {
                switch ((byte) n) {
                case -128: case -127: case -124: case -119: case -112:
                case -111: case -103: case  -95: case  -92: case  -87:
                case  -79: case  -71: case  -64: case  -63: case  -60:
                case  -55: case  -47: case  -39: case  -31: case  -28:
                case  -23: case  -15: case   -7: case    0: case    1:
                case    4: case    9: case   16: case   17: case   25:
                case   33: case   36: case   41: case   49: case   57:
                case   64: case   65: case   68: case   73: case   81:
                case   89: case   97: case  100: case  105: case  113:
                case  121:
                    long i = (n * INV3465) >>> 52;
                    if (! good3465[(int) i]) {
                        return false;
                    } else {
                        long r = round(Math.sqrt(n));
                        return r*r == n; 
                    }
                default:
                    return false;
                }
            }
        }
    
        private static int round(double x) {
            return (int) Double.doubleToRawLongBits(x + (double) (1L << 52));
        }
    
        /** 3465<sup>-1</sup> modulo 2<sup>64</sup> */
        private static final long INV3465 = 0x8ffed161732e78b9L;
    
        private static final boolean[] good3465 =
            new boolean[0x1000];
    
        static {
            for (int r = 0; r < 3465; ++ r) {
                int i = (int) ((r * r * INV3465) >>> 52);
                good3465[i] = good3465[i+1] = true;
            }
        }
    
    }
    
    avatar
    7 января 2010 в 11:00
    1

    Должна быть возможность упаковать «не может быть идеальным квадратом, если последние X цифр равны N» намного эффективнее, чем это! Я буду использовать 32-битные целые числа Java и произведу достаточно данных для проверки последних 16 бит числа - это 2048 шестнадцатеричных значений int.

    ...

    Хорошо. Либо я столкнулся с какой-то теорией чисел, которая мне немного недоступна, либо в моем коде есть ошибка. В любом случае вот код:

    public static void main(String[] args) {
        final int BITS = 16;
    
        BitSet foo = new BitSet();
    
        for(int i = 0; i< (1<<BITS); i++) {
            int sq = (i*i);
            sq = sq & ((1<<BITS)-1);
            foo.set(sq);
        }
    
        System.out.println("int[] mayBeASquare = {");
    
        for(int i = 0; i< 1<<(BITS-5); i++) {
            int kk = 0;
            for(int j = 0; j<32; j++) {
                if(foo.get((i << 5) | j)) {
                    kk |= 1<<j;
                }
            }
            System.out.print("0x" + Integer.toHexString(kk) + ", ");
            if(i%8 == 7) System.out.println();
        }
        System.out.println("};");
    }
    

    и вот результаты:

    (ed: исключено из-за низкой производительности в prettify.js; просмотрите историю изменений, чтобы увидеть.)

    avatar
    24 сентября 2009 в 09:46
    1

    «Я ищу самый быстрый способ определить, является ли длинное значение точным квадратом (т.е. его квадратный корень - другое целое число)».

    Ответы впечатляют, но простой проверки я не увидел:

    проверяет, является ли первое число справа от длинного членом набора (0,1,4,5,6,9). В противном случае это не может быть «идеальным квадратом».

    например,

    4567 - не может быть идеальным квадратом.

    Kip
    24 сентября 2009 в 13:42
    7

    на самом деле это предлагалось, только в разных базах. Для проверки последней цифры по основанию 10 требуется взять n%10, что является делением (и, следовательно, дорого). Кроме того, это исключило бы только 40% возможных значений. В base-16 вы можете найти последнюю шестнадцатеричную цифру с помощью n&0xf, что является очень быстрой побитовой операцией. В базе 16 последняя цифра полного квадрата должна быть 0, 1, 4 или 9, что означает, что 75% чисел исключаются этой проверкой.

    Kip
    24 сентября 2009 в 13:44
    0

    Это строка, которая проверяет, что последняя шестнадцатеричная цифра равна 0, 1, 4 или 9, хотя для этого используются некоторые оптимизированные битовые трюки: if( n < 0 || ((n&2) != 0) || ((n & 7) == 5) || ((n & 11) == 8) )

    dstibbe
    25 сентября 2009 в 09:47
    0

    Может, следующее будет быстрее? Изменение: if (n <0 || ((n & 2)! = 0) || ((n & 7) == 5) || ((n & 11) == 8)) return false; если (n == 0) вернуть истину; в: если (n == 0) вернуть истину; if (n <0 ||! ((n & 7 == 1) || n == 4)) return false;

    avatar
    25 мая 2009 в 01:38
    6

    Мне нравится идея использовать почти правильный метод для некоторых входных данных. Вот версия с большим «смещением». Код работает и проходит мой простой тестовый пример.

    Просто замените свой:

    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);
    }
    
    avatar
    11 марта 2009 в 13:37
    6

    Вызов 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 выполняется примерно в 1/3 времени на моей машине core2 duo. Я подозреваю, что дальнейшие настройки в том же направлении могут в среднем еще больше сократить время, но каждый раз, когда вы проверяете, вы жертвуете дополнительным тестированием в пользу большего исключения, так что вы не можете слишком далеко продвинуться по этому пути.

    Конечно, вместо того, чтобы проводить отдельный тест на отрицательный результат, вы могли бы таким же образом проверить старшие 6 бит.

    Обратите внимание, что все, что я делаю, это исключаю возможные квадраты, но когда у меня есть потенциальный случай, мне приходится вызывать исходный встроенный isPerfectSquare.

    Процедура init2 вызывается один раз для инициализации статических значений pp1 и pp2. Обратите внимание, что в моей реализации на C ++ я использую unsigned long long, поэтому, поскольку вы подписаны, вам придется использовать оператор >>>.

    Нет никакой внутренней потребности в проверке границ массива, но оптимизатор Java должен выяснить это довольно быстро, поэтому я не виню их за это.

    maaartinus
    8 сентября 2013 в 19:18
    3

    Готов поспорить, ты дважды ошибаешься. 1. Intel sqrt соответствует IEEE. Единственные несоответствующие инструкции - это гониометрические инструкции для аргументов lange. 2. Java использует встроенные функции для Math.sqrt, без JNI.

    maaartinus
    20 февраля 2018 в 16:34
    1

    Вы не забыли использовать pp2? Я понимаю, что pp1 используется для тестирования шести младших значащих битов, но я не верю, что тестирование следующих шести бит имеет какой-либо смысл.

    avatar
    11 марта 2009 в 13:25
    0

    Что касается метода Кармака, кажется, что было бы довольно легко просто повторить итерацию еще раз, что должно удвоить количество цифр точности. В конце концов, это чрезвычайно усеченный итерационный метод - метод Ньютона, с очень хорошим первым предположением.

    Что касается ваших текущих результатов, я вижу две микрооптимизации:

    • переместить чек против 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;
    

    Очевидно, было бы интересно узнать, сколько чисел отбирается на каждой контрольной точке - я очень сомневаюсь, что проверки действительно независимы, что усложняет задачу.

    avatar
    27 января 2009 в 20:35
    135

    Вам нужно будет провести сравнительный анализ. Лучший алгоритм будет зависеть от распределения ваших входных данных.

    Ваш алгоритм может быть почти оптимальным, но вы можете сделать быструю проверку, чтобы исключить некоторые возможности, прежде чем вызывать процедуру извлечения квадратного корня. Например, посмотрите на последнюю цифру своего номера в шестнадцатеричном формате, выполняя побитовое «и». Идеальные квадраты могут оканчиваться только на 0, 1, 4 или 9 в базе 16, поэтому для 75% ваших входных данных (при условии, что они распределены равномерно) вы можете избежать вызова квадратного корня в обмен на очень быстрое вращение битов.

    Кип протестировал следующий код, реализующий шестнадцатеричный трюк. При тестировании чисел от 1 до 100000000 этот код работал вдвое быстрее исходного.

    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 #.

    warren
    17 ноября 2008 в 14:38
    0

    это довольно умно ... не подумал бы об этом

    PeterAllenWebb
    17 ноября 2008 в 14:56
    0

    Хороший момент о конечных битах. Я бы попытался объединить этот тест с некоторыми другими замечаниями.

    Kip
    17 ноября 2008 в 16:09
    0

    Я проверил его для первых 100 миллионов целых чисел .. Это примерно вдвое сокращает необходимое время.

    kenj0418
    8 февраля 2010 в 04:41
    0

    Вы также можете расширить это число за пределы последней цифры. Например, младший байт может иметь всего 44 различных значения.

    Jeel Shah
    7 декабря 2011 в 15:30
    4

    Превосходное решение. Хотите знать, как вы это придумали? Это достаточно устоявшийся принцип или вы только что поняли? : D

    LarsH
    17 октября 2013 в 14:43
    0

    К вашему сведению, я тестировал этот метод на Python. Это дало примерно 3/8 ускорение по сравнению с обычным t = math.floor(math.sqrt(n) + 0.5); return t*t == n (5 секунд против 8 секунд для вычисления первых 100000 целых чисел, 100 раз).

    maaartinus
    13 июня 2014 в 18:12
    3

    @LarsH Нет необходимости добавлять 0,5, см. Мое решение для ссылки на доказательство.

    GorvGoyl
    3 января 2017 в 09:26
    0

    вы сказали, что if-else быстрее, чем switch, но этот вопрос coderhelper.com/questions/6805026/is-switch-faster-than-if говорит о другом.

    fishinear
    10 ноября 2017 в 16:56
    2

    @JerryGoyal Это зависит от компилятора и значений кейсов. В идеальном компиляторе переключение всегда выполняется как минимум так же быстро, как if-else. Но компиляторы не идеальны, поэтому лучше попробовать, как это сделал Джон.

    avatar
    2 января 2009 в 11:25
    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
    

    Вот пример чего-то похожего (пожалуйста, не голосуйте за меня за стиль кодирования / запахи или неуклюжие O / O - это алгоритм, который имеет значение, а C ++ не является моим родным языком). В этом случае мы ищем остаток == 0:

    #include <iostream>  
    
    using namespace std;  
    typedef unsigned long long int llint;
    
    class ISqrt {           // Integer Square Root
        llint value;        // Integer whose square root is required
        llint root;         // Result: floor(sqrt(value))
        llint residue;      // Result: value-root*root
        llint onebit, x;    // Working bit, working value
    
    public:
    
        ISqrt(llint v = 2) {    // Constructor
            Root(v);            // Take the root 
        };
    
        llint Root(llint r) {   // Resets and calculates new square root
            value = r;          // Store input
            residue = value;    // Initialise for subtracting down
            root = 0;           // Clear root accumulator
    
            onebit = 1;                 // Calculate start value of counter
            onebit <<= (8*sizeof(llint)-2);         // Set up counter bit as greatest odd power of 2 
            while (onebit > residue) {onebit >>= 2; };  // Shift down until just < value
    
            while (onebit > 0) {
                x = root ^ onebit;          // Will check root+1bit (root bit corresponding to onebit is always zero)
                if (residue >= x) {         // Room to subtract?
                    residue -= x;           // Yes - deduct from residue
                    root = x + onebit;      // and step root
                };
                root >>= 1;
                onebit >>= 2;
            };
            return root;                    
        };
        llint Residue() {           // Returns residue from last calculation
            return residue;                 
        };
    };
    
    int main() {
        llint big, i, q, r, v, delta;
        big = 0; big = (big-1);         // Kludge for "big number"
        ISqrt b;                            // Make q sqrt generator
        for ( i = big; i > 0 ; i /= 7 ) {   // for several numbers
            q = b.Root(i);                  // Get the square root
            r = b.Residue();                // Get the residue
            v = q*q+r;                      // Recalc original value
            delta = v-i;                    // And diff, hopefully 0
            cout << i << ": " << q << " ++ " << r << " V: " << v << " Delta: " << delta << "\n";
        };
        return 0;
    };
    
    Tadmas
    2 января 2009 в 00:24
    0

    Количество итераций выглядит O (ln n), где n - длина в битах v, поэтому я сомневаюсь, что это сэкономит много для большего v. Sqrt с плавающей запятой медленный, может быть, 100-200 циклов, но целочисленная математика - нет бесплатно тоже. Дюжина итераций по 15 циклов в каждой, и это будет стирка. Тем не менее, +1 за интерес.

    Brent.Longborough
    2 января 2009 в 08:12
    0

    На самом деле, я считаю, что сложение и вычитание можно выполнять с помощью XOR.

    Brent.Longborough
    2 января 2009 в 09:13
    0

    Это был глупый комментарий - с помощью XOR можно выполнить только добавление; вычитание арифметическое.

    Tadmas
    2 января 2009 в 22:59
    1

    В любом случае, есть ли существенная разница между временем выполнения XOR и сложением?

    Brent.Longborough
    4 января 2009 в 00:17
    1

    @Tadmas: вероятно, этого недостаточно, чтобы нарушить правило «оптимизировать позже». (:-)

    avatar
    2 января 2009 в 08:17
    7

    Вам следует с самого начала избавиться от 2-степенной части N.

    2-е редактирование Магическое выражение для m ниже должно быть

    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% чисел.

    avatar
    5 декабря 2008 в 05:36
    9

    Для производительности очень часто приходится идти на компромиссы. Другие описали различные методы, однако вы отметили, что взлом Кармака был быстрее до определенных значений N. Затем вы должны проверить «n», и если оно меньше, чем это число N, используйте взлом Кармака, иначе используйте какой-либо другой описанный метод. в ответах здесь.

    Kip
    5 декабря 2008 в 19:56
    0

    Я тоже включил ваше предложение в решение. Также приятная ручка. :)

    avatar
    2 декабря 2008 в 10:00
    13

    Для записи, другой подход - использовать разложение на простые числа. Если все множители разложения четные, то число представляет собой полный квадрат. Итак, вам нужно посмотреть, можно ли разложить число как произведение квадратов простых чисел. Конечно, вам не нужно получать такое разложение, просто чтобы посмотреть, существует ли оно.

    Сначала постройте таблицу квадратов простых чисел, меньших 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 в своем ответе.

    Peter Cordes
    21 августа 2015 в 02:22
    1

    целочисленное деление медленнее, чем FP sqrt на текущем оборудовании. У этой идеи нет шансов. >. <Даже в 2008 году пропускная способность Core2 sqrtsd составляла один на 6-58c. Его idiv - один на 12–36 циклов. (задержки аналогичны пропускной способности: ни один из модулей не конвейеризован).

    Peter Cordes
    21 августа 2015 в 02:23
    0

    sqrt не обязательно должен быть абсолютно точным. Вот почему вы проверяете, возводя результат в квадрат и выполняя целочисленное сравнение, чтобы решить, имеет ли входное целое точное целое число sqrt.

    President James K. Polk
    19 июня 2021 в 22:07
    1

    Возможно, это не лучший вариант, но мне он нравится, потому что это другой подход.

    avatar
    29 ноября 2008 в 03:52
    11

    Было указано, что последние d цифры полного квадрата могут принимать только определенные значения. Последние d цифры (в базе b) числа n совпадают с остатком, когда n делится на bd <149532>, т.е. в нотации C n % pow(b, d).

    Это может быть обобщено на любой модуль m, т.е. n % m может использоваться для исключения некоторого процента чисел из точных квадратов. Модуль, который вы в настоящее время используете, равен 64, что позволяет 12, т.е. 19% остатков, как возможные квадраты. Немного написав код, я нашел модуль 110880, который допускает только 2016, т.е. 1,8% остатков как возможные квадраты. Таким образом, в зависимости от стоимости операции модуля (например, деления) и поиска в таблице по сравнению с квадратным корнем на вашем компьютере, использование этого модуля может быть быстрее.

    Между прочим, если в Java есть способ хранить упакованный массив битов для таблицы поиска, не используйте его. 110880 32-битных слов в наши дни не так много ОЗУ, и выборка машинного слова будет быстрее, чем выборка одного бита.

    finnw
    7 января 2010 в 12:28
    0

    Хороший. Вы решили это алгебраически или методом проб и ошибок? Я понимаю, почему это так эффективно - много столкновений между идеальными квадратами, например 333 ^ 2% 110880 == 3 ^ 2, 334 ^ 2% 110880 == 26 ^ 2, 338 ^ 2% 110880 == 58 ^ 2 ...

    Hugh Allen
    19 января 2010 в 01:18
    0

    IIRC, это была грубая сила, но обратите внимание, что 110880 = 2 ^ 5 * 3 ^ 2 * 5 * 7 * 11, что дает 6 * 3 * 2 * 2 * 2-1 = 143 правильных делителя.

    Fractaly
    4 декабря 2011 в 05:57
    0

    Я обнаружил, что из-за ограничений поиска 44352 работает лучше с показателем успешности 2,6%. По крайней мере, в моей реализации.

    Peter Cordes
    21 августа 2015 в 02:13
    1

    Целочисленное деление (idiv) равно или хуже по стоимости FP sqrt (sqrtsd) на текущем оборудовании x86. Кроме того, полностью не согласен с отказом от битовых полей. Скорость попадания в кеш будет на много выше с битовым полем, а тестирование битового поля - это всего лишь одна или две более простых инструкции, чем тестирование целого байта. (Для крошечных таблиц, которые помещаются в кеш даже без битовых полей, лучше всего подойдет байтовый массив, а не 32-битные целые числа. X86 имеет однобайтовый доступ с такой же скоростью, что и 32-битное двойное слово.)

    avatar
    17 ноября 2008 в 23:29
    1

    Если скорость вызывает беспокойство, почему бы не разделить наиболее часто используемый набор входных данных и их значений в поисковую таблицу, а затем применить любой оптимизированный магический алгоритм, который вы придумали для исключительных случаев?

    Kip
    6 января 2009 в 14:40
    0

    Проблема в том, что не существует «обычно используемого набора входных данных» - обычно я просматриваю список, поэтому я не буду использовать одни и те же входные данные дважды.

    avatar
    17 ноября 2008 в 15:04
    18

    Должно быть намного быстрее использовать метод Ньютона для вычисления целочисленного квадратного корня, затем возвести это число в квадрат и проверить, как вы это делаете в вашем текущем решении. Метод Ньютона является основой решения Кармака, упомянутого в некоторых других ответах. Вы сможете получить более быстрый ответ, поскольку вас интересует только целая часть корня, что позволит вам быстрее остановить алгоритм аппроксимации.

    Другая оптимизация, которую вы можете попробовать: Если Цифровой корень числа не заканчивается на 1, 4, 7 или 9 число является не точным квадратом. Это можно использовать как быстрый способ исключить 60% ваших входных данных перед применением более медленного алгоритма извлечения квадратного корня.

    Christian Oudard
    8 января 2010 в 16:48
    1

    Цифровой корень строго вычислительно эквивалентен модулю, поэтому его следует рассматривать вместе с другими методами модуля, такими как mod 16 и mod 255.

    Fractaly
    4 декабря 2011 в 04:44
    1

    Вы уверены, что цифровой корень эквивалентен модулю? Вроде бы что-то совсем другое, как объяснено по ссылке. Обратите внимание, что список 1,4,7,9, а не 1,4,5,9.

    Hans Olsson
    19 января 2018 в 12:31
    1

    Цифровой корень в десятичной системе эквивалентен использованию по модулю 9 (хорошо dr (n) = 1 + ((n-1) mod 9); так что небольшой сдвиг). Числа 0,1,4,5,9 соответствуют модулю 16, а 0, 1, 4, 7 - модулю 9, что соответствует 1, 4, 7, 9 для цифрового корня.

    avatar
    17 ноября 2008 в 14:49
    -3

    Не знаю о самом быстром, но самый простой - это извлечь квадратный корень обычным способом, умножить результат на себя и посмотреть, соответствует ли он исходному значению.

    Поскольку мы говорим здесь о целых числах, голодание, вероятно, будет включать коллекцию, в которой вы можете просто выполнить поиск.

    nickf
    17 ноября 2008 в 14:04
    1

    Разве не было бы быстрее и дешевле «извлечь квадратный корень обычным способом» и проверить, является ли это целым числом?

    Joel Coehoorn
    17 ноября 2008 в 15:57
    0

    Я полагаю, это зависит от того, какая операция в вашей системе работает быстрее: мод или групповая операция.

    Steve Storck
    5 декабря 2017 в 10:50
    0

    Проверьте мое предложение выше. Это очень простой подход. Но вы также можете использовать функцию sqrt и изменить ее на 1. Я добавлю это как еще одно предлагаемое решение.

    avatar
    17 ноября 2008 в 14:48
    36

    Если вы выполните двоичную отбивку, чтобы попытаться найти "правильный" квадратный корень, вы можете довольно легко определить, достаточно ли близко полученное вами значение, чтобы сказать:

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

    Итак, вычислив n^2, можно выбрать следующие варианты:

    • n^2 = target: выполнено, вернуть истину
    • n^2 + 2n + 1 > target > n^2: вы близки, но не идеально: верните false
    • n^2 - 2n + 1 < target < n^2: то же самое
    • target < n^2 - 2n + 1: двоичное прерывание по нижнему n
    • target > n^2 + 2n + 1: двоичное прерывание на более высоком n

    (Извините, здесь используется n в качестве вашего текущего предположения и target в качестве параметра. Извините за путаницу!)

    Не знаю, будет ли это быстрее или нет, но попробовать стоит.

    РЕДАКТИРОВАТЬ: двоичный фрагмент не обязательно должен принимать весь диапазон целых чисел, либо (2^x)^2 = 2^(2x), поэтому, как только вы найдете верхний установленный бит в своей цели (что можно сделать с помощью хитрого трюка Я забыл, как именно) можно быстро получить ряд возможных ответов. Имейте в виду, что наивная двоичная отбивка по-прежнему может занять до 31 или 32 итераций.

    PeterAllenWebb
    17 ноября 2008 в 14:44
    0

    Мои деньги идут на такой подход. Избегайте вызова sqrt (), поскольку он вычисляет полный квадратный корень, и вам нужны только первые несколько цифр.

    Jon Skeet
    17 ноября 2008 в 14:49
    3

    С другой стороны, если с плавающей запятой используется специальный блок FP, он может использовать всевозможные забавные трюки. Я бы не хотел ставить на это без теста :) (я могу попробовать его сегодня вечером, хотя и на C #, просто чтобы посмотреть ...)

    Adam Rosenfield
    29 ноября 2008 в 03:58
    8

    Аппаратные sqrts в наши дни действительно работают довольно быстро.

    avatar
    17 ноября 2008 в 13:48
    0

    Если вам нужна скорость, учитывая, что ваши целые числа имеют конечный размер, я подозреваю, что самый быстрый способ будет включать (а) разделение параметров по размеру (например, на категории по наибольшему набору битов), а затем проверку значения по массиву полных квадратов в этом диапазоне.

    PeterAllenWebb
    17 ноября 2008 в 14:54
    2

    Всего 2 ^ 32 полных квадрата в диапазоне длинных. Этот стол был бы огромным. Кроме того, преимущество вычисления стоимости над доступом к памяти может быть огромным.

    Celestial M Weasel
    18 ноября 2008 в 12:04
    0

    О нет, их 2 ^ 16. 2 ^ 32 равно 2 ^ 16 в квадрате. Есть 2 ^ 16.

    Kip
    2 декабря 2008 в 19:14
    3

    да, но диапазон long составляет 64 бита, а не 32 бита. sqrt (2 ^ 64) = 2 ^ 32. (я игнорирую знаковый бит, чтобы немного упростить математику ... на самом деле (длинных) (2 ^ 31,5) = 3037000499 полных квадратов)