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

Я ищу самый быстрый способ определить, является ли 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 . Так что больше никому не придется поддерживать этот код. И этот вид микрооптимизации может реально изменить ситуацию, поскольку одна из задач состоит в том, чтобы выполнить каждый алгоритм менее чем за минуту, и в некоторых задачах эту функцию нужно будет вызывать миллионы раз.


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

  • После исчерпывающего тестирования я обнаружил, что добавление 0.5к результату Math.sqrt () необязательно, по крайней мере, на моей машине.
  • Быстрый обратный квадратный корень был быстрее, но он дал неправильные результаты при п> = 410881. Однако, как это было предложено BobbyShaftoe , мы можем использовать FISR хак для п <410881.
  • Метод Ньютона был немного медленнее, чем Math.sqrt(). Вероятно, это связано с тем, что Math.sqrt()используется метод, подобный методу Ньютона, но реализованный в аппаратном обеспечении, поэтому он намного быстрее, чем в Java. Кроме того, метод Ньютона все еще требовал использования двойных чисел.
  • Модифицированный метод Ньютона, который использовал несколько приемов так, чтобы была задействована только целочисленная математика, требовал некоторых хаков, чтобы избежать переполнения (я хочу, чтобы эта функция работала со всеми положительными 64-битными целыми числами со знаком), и это было все еще медленнее, чем Math.sqrt().
  • Бинарная отбивная была еще медленнее. Это имеет смысл, потому что двоичной отбивке в среднем потребуется 16 проходов, чтобы найти квадратный корень 64-битного числа.
  • Согласно тестам Джона, использование orоператоров в C ++ быстрее, чем использование a switch, но в Java и C #, похоже, нет разницы между orи switch.
  • Я также попытался создать таблицу поиска (как частный статический массив из 64 логических значений). Тогда вместо того, чтобы менять или orутверждать, я бы просто сказал if(lookup[(int)(n&0x3F)]) { test } else return false;. К моему удивлению, это было (немного) медленнее. Это потому, что границы массива проверяются в Java .
17.11.2008 13:43:21
Это код Java, где int == 32 бита и long == 64 бита, и оба подписаны.
Kip 17.11.2008 14:35:13
@Shreevasta: я провел некоторое тестирование на больших значениях (больше 2 ^ 53), и ваш метод дает некоторые ложные срабатывания. Первое, что встречается, относится к n = 9007199326062755, который не является идеальным квадратом, но возвращается как единое целое.
Kip 2.12.2008 20:03:13
Пожалуйста, не называйте это «взломом Джона Кармака». Он не придумал это.
user9282 11.03.2009 06:27:36
@mamama - Возможно, но это приписывается ему. Генри Форд не изобрел автомобиль, братья Райт не изобрели самолет, и Галлелео не был первым, кто понял, что Земля вращается вокруг Солнца ... мир состоит из украденных изобретений (и любовь).
Robert Fraser 6.05.2010 10:25:18
Вы можете получить небольшое увеличение скорости в «быстрой неудаче», используя что-то вроде ((1<<(n&15))|65004) != 0, вместо трех отдельных проверок.
Nabb 1.11.2011 12:06:34
30 ОТВЕТОВ
РЕШЕНИЕ

Я нашел метод, который работает на 35% быстрее, чем ваш код 6bit + 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. Наконец, попробуйте вычислить квадратный корень, используя метод, аналогичный лемме Хензеля . (Я не думаю, что это применимо напрямую, но оно работает с некоторыми модификациями.) Перед этим я делю все степени 2 с помощью двоичного поиска:
    if((x & 4294967295LL) == 0)
        x >>= 32;
    if((x & 65535) == 0)
        x >>= 16;
    if((x & 255) == 0)
        x >>= 8;
    if((x & 15) == 0)
        x >>= 4;
    if((x & 3) == 0)
        x >>= 2;
    На данный момент, чтобы наше число было квадратным, оно должно быть 1 mod 8.
    if((x & 7) != 1)
        return false;
    Основная структура леммы Гензеля заключается в следующем. (Примечание: непроверенный код; если он не работает, попробуйте t = 2 или 8.)
    int64 t = 4, r = 1;
    t <<= 1; r += ((x - r * r) & t) >> 1;
    t <<= 1; r += ((x - r * r) & t) >> 1;
    t <<= 1; r += ((x - r * r) & t) >> 1;
    // Repeat until t is 2^33 or so.  Use a loop if you want.
    Идея состоит в том, что на каждой итерации вы добавляете один бит в r, «текущий» квадратный корень из x; каждый квадратный корень является точным по модулю все большей и большей степени 2, а именно t / 2. В конце r и t / 2-r будут квадратными корнями из x по модулю t / 2. (Обратите внимание, что если r - это квадратный корень из x, то так же и -r. Это верно даже по модулю чисел, но будьте осторожны, по модулю некоторых чисел вещи могут иметь даже более 2 квадратных корней; в частности, это включает степени 2. ) Поскольку наш фактический квадратный корень меньше 2 ^ 32, в этот момент мы можем просто проверить, являются ли r или t / 2-r действительными квадратными корнями. В моем реальном коде я использую следующий модифицированный цикл:
    int64 r, t, z;
    r = start[(x >> 3) & 1023];
    do {
        z = x - r * r;
        if( z == 0 )
            return true;
        if( z < 0 )
            return false;
        t = z & (-z);
        r += (z & t) >> 1;
        if( r > (t >> 1) )
            r = t - r;
    } while( t <= (1LL << 33) );
    Ускорение здесь достигается тремя способами: предварительно вычисленное начальное значение (эквивалентное ~ 10 итерациям цикла), более ранний выход из цикла и пропуск некоторых значений t. В последней части я смотрю z = r - x * xи устанавливаю t как наибольшую степень деления z на 2 с небольшим фокусом. Это позволяет мне пропустить 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,
  
725
17.11.2013 23:39:06
Вот это да! Я постараюсь преобразовать это в Java и сделать сравнение, а также проверку точности результатов. Я дам вам знать, что я нахожу.
Kip 12.01.2009 21:47:11
Вау, это прекрасно. Я уже видел подъем Хензеля (вычисление корней многочленов по модулю простого числа), но я даже не догадывался, что лемму можно аккуратно опустить до полного вычисления квадратных корней чисел; это ...
ShreevatsaR 25.05.2009 02:36:58
@ nightcracker Это не так. 9 < 0 => false, 9&2 => 0, 9&7 == 5 => false, 9&11 == 8 => false.
primo 2.12.2012 07:56:56
Maartinus опубликовал в 2 раза более быстрое решение (и намного короче) ниже, чуть позже, которое, кажется, не получает большой любви.
Jason C 17.03.2014 03:46:49
Кажется, что большое преимущество в скорости в различных решениях достигается за счет фильтрации очевидных квадратов. Кто-нибудь тестировал ситуацию с фильтрацией через решение Maartinus, а затем просто использовал функцию sqrt, поскольку это встроенная функция?
user1914292 7.10.2014 17:26:16

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

0
17.11.2008 13:48:29
В диапазоне длинны 2 ^ 32 идеальных квадрата. Эта таблица будет огромной. Кроме того, преимущество вычисления значения по сравнению с доступом к памяти может быть огромным.
PeterAllenWebb 17.11.2008 14:54:16
О нет, нет, есть 2 ^ 16. 2 ^ 32 равно 2 ^ 16 в квадрате. Есть 2 ^ 16.
Celestial M Weasel 18.11.2008 12:04:05
да, но диапазон длинных составляет 64 бита, а не 32 бита. SQRT (2 ^ 64) = 2 ^ 32. (Я игнорирую знаковый бит, чтобы сделать математику немного проще ... на самом деле (длинные) (2 ^ 31,5) = 3037000499 совершенных квадратов)
Kip 2.12.2008 19:14:57

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

И потом я помню, что эта функция кружила по сети из исходного кода 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основном это функция быстрого преобразования в long, поэтому целые операции могут применяться к необработанным байтам.
  • 0x5f3759df - (i >> 1);линия представляет собой предварительно рассчитанное значение семян для функции аппроксимации.
  • * (float*) &iпреобразует значение обратно с плавающей точкой.
  • y = y * ( threehalfs - ( x2 * y * y ) )линия Bascially итерации значения над функцией снова.

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

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

52
13.04.2012 06:18:29
Следует отметить, что это возвращает 1 / sqrt (число), а не sqrt (число). Я провел некоторое тестирование, и это не удалось, начиная с n = 410881: магическая формула Джона Кармака возвращает 642.00104, когда фактический квадратный корень равен 641.
Kip 17.11.2008 19:56:52
Вы можете посмотреть на статью Криса Ломонца о быстрых обратных квадратных корнях: lomont.org/Math/Papers/2003/InvSqrt.pdf В ней используется та же техника, что и здесь, но с другим магическим числом. В статье объясняется, почему был выбран магический номер.
user21037 2.12.2008 10:24:59
Кроме того, beyond3d.com/content/articles/8 и beyond3d.com/content/articles/15 проливают некоторый свет на истоки этого метода. Его часто приписывают Джону Кармаку, но кажется, что оригинальный код (возможно) был написан Гари Таролли, Грегом Уолшем и, возможно, другими.
user21037 2.12.2008 10:26:33
Также вы не можете печатать плавающие и целые числа в Java.
Antimony 27.08.2013 14:29:43
@ Сурьма кто говорит? FloatToIntBits и IntToFloatBits существуют с java 1.0.2.
corsiKa 27.05.2015 17:50:52

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

(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 : ты близок, но не идеален: верни ложь
  • 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 итерации.

35
17.11.2008 14:48:48
Мои деньги на такой подход. Избегайте вызова sqrt (), так как он вычисляет полный квадратный корень, и вам нужны только первые несколько цифр.
PeterAllenWebb 17.11.2008 14:44:37
С другой стороны, если плавающая точка выполняется в выделенном блоке FP, она может использовать все виды забавных трюков. Я не хотел бы ставить на это без эталона :) (я могу попробовать это сегодня вечером, хотя в C #, просто чтобы посмотреть ...)
Jon Skeet 17.11.2008 14:49:38
Аппаратные средства на самом деле довольно быстрые в наши дни.
Adam Rosenfield 29.11.2008 03:58:51

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

38
2.07.2019 00:37:32
Я считаю, что трюк Кармака в наши дни довольно бессмысленный. Встроенная инструкция sqrt работает намного быстрее, чем раньше, поэтому вам может быть лучше просто выполнить обычный квадратный корень и проверить, что в результате получается int. Как всегда, отметьте это.
jalf 17.11.2008 15:22:49
Это ломается, начиная с n = 410881, магическая формула Джона Кармака возвращает 642.00104, когда фактический квадратный корень равен 641.
Kip 17.11.2008 19:55:13
Недавно я использовал трюк Кармака в Java-игре, и он был очень эффективен, давая ускорение примерно на 40%, поэтому он все еще полезен, по крайней мере, в Java.
finnw 7.01.2010 11:57:49
@ Роберт Фрейзер Да + 40% от общей частоты кадров. В игре была система физики элементарных частиц, которая занимала почти все доступные циклы ЦП, в которой преобладали функция квадратного корня и функция округления до ближайшего целого числа (которую я также оптимизировал с помощью аналогичного
finnw 6.05.2010 10:48:51
Ссылка не работает.
Pixar 2.06.2018 18:45:37

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

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

-3
17.11.2008 14:49:26
не будет ли быстрее и дешевле «взять квадратный корень обычным способом» и проверить, является ли оно целым?
nickf 17.11.2008 14:04:30
Я полагаю, это зависит от того, быстрее ли в вашей системе работает мод или мультиоператор.
Joel Coehoorn 17.11.2008 15:57:35
Проверьте мое предложение выше. Требуется очень простой подход. Но вы также можете использовать функцию sqrt и изменить ее на 1. Я добавлю это в качестве другого предложенного решения.
Steve Storck 5.12.2017 10:50:00

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

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

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

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

    switch((int)(n & 0xF))
    {
    case 0: case 1: case 4: case 9:
        long tst = (long)Math.sqrt(n);
        return tst*tst == n;

    default:
        return false;
    }
}

Когда я тестировал аналогичный код в C ++, он на самом деле работал медленнее, чем оригинал. Однако, когда я исключил оператор switch, шестнадцатеричный трюк снова сделал код в два раза быстрее.

int isPerfectSquare(int n)
{
    int h = n & 0xF;  // h is the last hex "digit"
    if (h > 9)
        return 0;
    // Use lazy evaluation to jump out of the if statement as soon as possible
    if (h != 2 && h != 3 && h != 5 && h != 6 && h != 7 && h != 8)
    {
        int t = (int) floor( sqrt((double) n) + 0.5 );
        return t*t == n;
    }
    return 0;
}

Исключение оператора switch мало повлияло на код C #.

131
27.01.2009 20:35:45
это довольно умно ... не подумал бы об этом
warren 17.11.2008 14:38:07
Хороший момент о конечных битах. Я бы попытался объединить этот тест с некоторыми другими замечаниями здесь.
PeterAllenWebb 17.11.2008 14:56:44
Отличное решение. Хотите знать, как вы пришли к этому? Это довольно устоявшийся принцип или вы что-то выяснили? : D
Jeel Shah 7.12.2011 15:30:15
@LarsH Нет необходимости добавлять 0,5, см. Мое решение для ссылки на доказательство.
maaartinus 13.06.2014 18:12:42
@JerryGoyal Это зависит от компилятора и значений дел. В идеальном компиляторе переключатель всегда по крайней мере так же быстр, как если бы еще. Но компиляторы не идеальны, поэтому лучше попробовать, как Джон.
fishinear 10.11.2017 16:56:34

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

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

18
17.11.2008 15:04:49
Цифровой корень в вычислительном отношении эквивалентен по модулю, поэтому его следует рассматривать вместе с другими методами по модулю, такими как мод 16 и мод 255.
Christian Oudard 8.01.2010 16:48:00
Вы уверены, что цифровой корень эквивалентен модулю? Похоже, что-то совершенно другое, как объясняется по ссылке. Обратите внимание, что список 1,4,7,9, а не 1,4,5,9.
Fractaly 4.12.2011 04:44:42
Цифровой корень в десятичной системе эквивалентен использованию по модулю 9 (скважина dr (n) = 1 + ((n-1) mod 9); так что также небольшое смещение). Числа 0,1,4,5,9 относятся к модулю 16, а 0, 1, 4, 7 - к модулю 9 - что соответствует 1, 4, 7, 9 для цифрового корня.
Hans Olsson 19.01.2018 12:31:44

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

1
17.11.2008 23:29:58
Проблема в том, что не существует «обычно используемого набора входов» - обычно я перебираю список, поэтому я не буду использовать одни и те же входы дважды.
Kip 6.01.2009 14:40:06

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

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

16
6.04.2018 09:07:49
Я на самом деле проверил ответ на всех совершенных квадратах больше 2 ^ 53, а также на всех числах от 5 ниже каждого идеального квадрата до 5 над каждым идеальным квадратом, и я получил правильный результат. (ошибка округления исправляется, когда я округляю sqrt-ответ до long, затем возводю в квадрат это значение и сравниваю)
Kip 6.01.2009 14:33:38
@Kip: Думаю, я доказал, что это работает .
maaartinus 8.09.2013 19:12:27
Результаты не совсем точны, но точнее, чем вы думаете. Если мы примем не менее 15 точных цифр после преобразования в double и после квадратного корня, то этого достаточно, потому что нам нужно не более 11: 10 цифр для 32-битного квадратного корня и меньше 1 для десятичного знака, потому что +0,5 раундов до ближайшего.
mwfearnley 22.04.2014 00:54:04
Math.sqrt () не совсем точен, но это не обязательно. В самом первом посте tst является целым числом, близким к sqrt (N). Если N не является квадратом, то tst * tst! = N, независимо от значения tst. Если N - идеальный квадрат, то sqrt (N) <2 ^ 32, и до тех пор, пока sqrt (N) вычисляется с ошибкой <0.5, мы в порядке.
gnasher729 1.05.2014 23:27:49

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

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

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

11
29.11.2008 03:52:36
Приятно. Вы решали это алгебраически или методом проб и ошибок? Я понимаю, почему это так эффективно - множество столкновений между идеальными квадратами, например, 333 ^ 2% 110880 == 3 ^ 2, 334 ^ 2% 110880 == 26 ^ 2, 338 ^ 2% 110880 == 58 ^ 2 .. .
finnw 7.01.2010 12:28:07
IIRC это была грубая сила, но учтите, что 110880 = 2 ^ 5 * 3 ^ 2 * 5 * 7 * 11, что дает 6 * 3 * 2 * 2 * 2 - 1 = 143 правильных делителя.
Hugh Allen 19.01.2010 01:18:52
Я обнаружил, что из-за ограничений поиска, 44352 работает лучше, с пропускной способностью 2,6%. По крайней мере, в моей реализации.
Fractaly 4.12.2011 05:57:05
Целочисленное деление ( idiv) равно или хуже по стоимости FP sqrt ( sqrtsd) на текущем оборудовании x86. Кроме того, полностью не согласен с избеганием битовых полей. Частота попаданий в кэш будет намного лучше при использовании битового поля, а тестирование в битовом поле - всего одна или две более простые инструкции, чем тестирование целого байта. (Для крошечных таблиц, которые помещаются в кэш даже в виде не битовых полей, лучше использовать байтовый массив, а не 32-битные. X86 имеет однобайтовый доступ с равной скоростью до 32-битного слова.)
Peter Cordes 21.08.2015 02:13:16

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

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

13
2.12.2008 10:00:22
целочисленное деление медленнее, чем FP sqrt на текущем оборудовании. У этой идеи нет шансов. >. <Даже в 2008 году sqrtsdпропускная способность Core2 составляет один на 6-58с. Это idivодин на 12-36 циклов. (задержки аналогичны пропускной способности: ни одна единица не конвейерная).
Peter Cordes 21.08.2015 02:22:01
sqrt не должен быть абсолютно точным. Вот почему вы проверяете результат целочисленным возведением в квадрат и производите сравнение целых чисел, чтобы определить, имеет ли входное целое число точное целое число sqrt.
Peter Cordes 21.08.2015 02:23:56

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

9
5.12.2008 05:36:38
Я включил ваше предложение в решение тоже. Кроме того, хорошая ручка. :)
Kip 5.12.2008 19:56:34

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

2nd Edit Волшебное выражение для м ниже должно быть

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;

Конец первого редактирования

Теперь продолжайте как обычно. Таким образом, к тому времени, как вы доберетесь до части с плавающей запятой, вы уже избавились от всех чисел, чья 2-степенная часть нечетна (примерно половина), и тогда вы будете считать только 1/8 того, что осталось. Т.е. вы запускаете часть с плавающей запятой на 6% чисел.

7
2.01.2009 08:17:46

Это доработка от десятичного к двоичному алгоритму старого калькулятора Марчанта (извините, у меня нет ссылки) в 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;
};
6
2.01.2009 11:25:59
Количество итераций выглядит как O (ln n), где n - это длина в битах v, поэтому я сомневаюсь, что это значительно сэкономит при больших v. С плавающей точкой sqrt медленный, возможно, 100-200 циклов, но целочисленная математика не либо бесплатно. Десяток итераций с 15 циклами в каждой, и это будет стирка. Тем не менее +1 за интерес.
Tadmas 2.01.2009 00:24:34
На самом деле, я считаю, что дополнения и вычитания могут быть сделаны XOR.
Brent.Longborough 2.01.2009 08:12:15
Это был глупый комментарий - только добавление может быть сделано XOR; вычитание арифметическое.
Brent.Longborough 2.01.2009 09:13:29
Есть ли какая-то существенная разница между временем выполнения XOR и дополнением в любом случае?
Tadmas 2.01.2009 22:59:34
@Tadmas: вероятно, недостаточно, чтобы нарушить правило «оптимизировать позже». (:-)
Brent.Longborough 4.01.2009 00:17:51

Должна быть возможность упаковать 'не может быть идеальным квадратом, если последние 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; посмотреть историю изменений, чтобы увидеть.)

1
7.01.2010 11:00:07

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

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

  • переместить чек против 0 после проверки, используя mod255
  • переставить деление на четыре, чтобы пропустить все проверки для обычного (75%) случая.

То есть:

// Divide out powers of 4 using binary search

if((n & 0x3L) == 0) {
  n >>=2;

  if((n & 0xffffffffL) == 0)
    n >>= 32;
  if((n & 0xffffL) == 0)
      n >>= 16;
  if((n & 0xffL) == 0)
      n >>= 8;
  if((n & 0xfL) == 0)
      n >>= 4;
  if((n & 0x3L) == 0)
      n >>= 2;
}

Еще лучше может быть простой

while ((n & 0x03L) == 0) n >>= 2;

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

0
11.03.2009 13:25:39

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

6
11.03.2009 13:37:53
Держу пари, ты дважды ошибаешься. 1. Intel sqrt соответствует IEEE. Единственными несоответствующими инструкциями являются гониометрические инструкции для аргументов языка. 2. Java использует встроенные функции для Math.sqrt, а не JNI .
maaartinus 8.09.2013 19:18:36
Разве вы не забыли использовать pp2? Я понимаю, что pp1это используется для проверки шести младших разрядов, но я не верю, что проверка следующих шести разрядов имеет какой-то смысл.
maaartinus 20.02.2018 16:34:03

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

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

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

7
25.06.2019 22:02:50
Я думал то же самое об этих алгоритмах, которые плохо переводят в буферы с множественной точностью. Так что я подумал, что воткну это здесь ... Я на самом деле нашел вероятностный квадратный тест с лучшей асимптотической сложностью для больших чисел ... где приложения теории чисел нередко оказываются. Не знаком с Project Euler, хотя ... выглядит интересно.
user2975337 14.07.2015 02:27:31

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

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

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);
}
6
25.05.2009 01:38:24

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

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

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

например.

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

0
24.09.2009 09:46:57
на самом деле это было предложено, только на разных основаниях. Проверка последней цифры из 10-ти цифр требует взятия n%10, что является делением (и, следовательно, дорогим). Кроме того, это исключило бы только 40% возможных значений. В base-16 вы можете найти последнюю шестнадцатеричную цифру с n&0xf, что является очень быстрой побитовой операцией. В базе 16 последняя цифра идеального квадрата должна быть 0, 1, 4 или 9, что означает, что 75% чисел удаляются этой проверкой.
Kip 24.09.2009 13:42:31
Это строка, которая проверяет, является ли последняя шестнадцатеричная цифра 0, 1, 4 или 9, хотя для этого используются оптимизированные битовые трюки:if( n < 0 || ((n&2) != 0) || ((n & 7) == 5) || ((n & 11) == 8) )
Kip 24.09.2009 13:44:52
Возможно, следующее будет быстрее? Изменить: если (n <0 || ((n & 2)! = 0) || ((n & 7) == 5) || ((n & 11) == 8)) вернуть false; if (n == 0) вернет true; в: если (n == 0) вернуть истину; if (n <0 ||! ((n & 7 == 1) || n == 4)) вернуть false;
dstibbe 25.09.2009 09:47:42

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

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

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

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

public class SquareTester {

    public static boolean isPerfectSquare(long n) {
        if (n < 0) {
            return false;
        } else {
            switch ((byte) n) {
            case -128: case -127: case -124: case -119: case -112:
            case -111: case -103: case  -95: case  -92: case  -87:
            case  -79: case  -71: case  -64: case  -63: case  -60:
            case  -55: case  -47: case  -39: case  -31: case  -28:
            case  -23: case  -15: case   -7: case    0: case    1:
            case    4: case    9: case   16: case   17: case   25:
            case   33: case   36: case   41: case   49: case   57:
            case   64: case   65: case   68: case   73: case   81:
            case   89: case   97: case  100: case  105: case  113:
            case  121:
                long i = (n * INV3465) >>> 52;
                if (! good3465[(int) i]) {
                    return false;
                } else {
                    long r = round(Math.sqrt(n));
                    return r*r == n; 
                }
            default:
                return false;
            }
        }
    }

    private static int round(double x) {
        return (int) Double.doubleToRawLongBits(x + (double) (1L << 52));
    }

    /** 3465<sup>-1</sup> modulo 2<sup>64</sup> */
    private static final long INV3465 = 0x8ffed161732e78b9L;

    private static final boolean[] good3465 =
        new boolean[0x1000];

    static {
        for (int r = 0; r < 3465; ++ r) {
            int i = (int) ((r * r * INV3465) >>> 52);
            good3465[i] = good3465[i+1] = true;
        }
    }

}
8
6.05.2010 16:37:40

Учитывая общую длину в битах (хотя я использовал здесь определенный тип), я попытался разработать упрощенный алгоритм, как показано ниже. Первоначально требуется простая и очевидная проверка на 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;  
}  
6
5.03.2018 21:50:20
@Kip: Некоторые проблемы с моим браузером.
nabam serbang 18.12.2010 15:06:26
Тебе нужен отступ.
Steve Kuo 10.03.2011 03:25:26

Я проверил все возможные результаты, когда наблюдаются последние 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)
  • с имеет вид (2 << 2k + 2) - 1
  • d имеет вид (2 << 2k - 1) * 10

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

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

  • 5
    5.12.2011 04:29:48

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

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

    Алгоритмы ниже следующие:

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

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

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

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

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

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

    Вот Durron:

    public final static boolean isPerfectSquareDurron(long n) {
        if(n < 0) return false;
        if(n == 0) return true;
    
        long x = n;
        // This is faster because a number is divisible by 16 only 6% of the time
        // and more than that a vanishingly small percentage.
        while((x & 0x3) == 0) x >>= 2;
        // This is effectively the same as the switch-case statement used in the original
        // answer. 
        if((x & 0x7) == 1) {
    
            long sqrt;
            if(x < 410881L)
            {
                int i;
                float x2, y;
    
                x2 = x * 0.5F;
                y  = x;
                i  = Float.floatToRawIntBits(y);
                i  = 0x5f3759df - ( i >> 1 );
                y  = Float.intBitsToFloat(i);
                y  = y * ( 1.5F - ( x2 * y * y ) );
    
                sqrt = (long)(1.0F/y);
            } else {
                sqrt = (long) Math.sqrt(x);
            }
            return sqrt*sqrt == x;
        }
        return false;
    }

    А также DurronTwo

    public final static boolean isPerfectSquareDurronTwo(long n) {
        if(n < 0) return false;
        // Needed to prevent infinite loop
        if(n == 0) return true;
    
        long x = n;
        while((x & 0x3) == 0) x >>= 2;
        if((x & 0x7) == 1) {
            long sqrt;
            if (x < 41529141369L) {
                int i;
                float x2, y;
    
                x2 = x * 0.5F;
                y = x;
                i = Float.floatToRawIntBits(y);
                //using the magic number from 
                //http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf
                //since it more accurate
                i = 0x5f375a86 - (i >> 1);
                y = Float.intBitsToFloat(i);
                y = y * (1.5F - (x2 * y * y));
                y = y * (1.5F - (x2 * y * y)); //Newton iteration, more accurate
                sqrt = (long) ((1.0F/y) + 0.2);
            } else {
                //Carmack hack gives incorrect answer for n >= 41529141369.
                sqrt = (long) Math.sqrt(x);
            }
            return sqrt*sqrt == x;
        }
        return false;
    }

    И мой тестовый жгут: (Требуется Google Caliper 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, не оптимально, но явно с точностью до a 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
    24
    13.06.2013 17:42:46
    Гигантская таблица поиска не кажется хорошей идеей. Промежуток в кеше происходит медленнее (~ 100-150 циклов), чем инструкция аппаратного обеспечения x86 (~ 20 циклов). Что касается пропускной способности, вы можете выдержать много невыполненных кеш-ошибок, но вы по-прежнему извлекаете другие полезные данные. Огромная таблица поиска будет стоить того, только если она будет ОЧЕНЬ быстрее, чем любая другая опция, и эта функция была основным фактором производительности всей вашей программы.
    Peter Cordes 21.08.2015 02:05:13
    @SwissFrank: проверка идеального квадрата - единственное, что делает ваша программа? Таблица поиска может хорошо выглядеть в микробенчмарке, который вызывает ее многократно в узком цикле, но в реальной программе, имеющей другие данные в своем рабочем наборе, это не хорошо.
    Peter Cordes 30.10.2018 22:13:02
    Растровое изображение из 0x1FFFFFE бит занимает 4 мега - байт , если хранится в виде упакованного растрового изображения. L3 кэш - хит на современном рабочем столе Intel имеет> 40 циклов задержки, и хуже на большой Xeon; длиннее аппаратного sqrt + мул латентность. Если хранится в виде байтовой карты с 1 байтом на значение, это около 32 МБ; больше, чем кэш-память третьего уровня, кроме многоядерного Xeon, где все ядро ​​разделяет один огромный кэш. Таким образом, если ваши входные данные имеют равномерное случайное распределение по достаточно большому диапазону входных данных, вы получите много пропусков кэша L2 даже в узком цикле. (частный L2 для каждого ядра на Intel составляет всего 256 КБ, с ~ 12 задержками цикла.)
    Peter Cordes 30.10.2018 22:18:05
    @SwissFrank: О, если все, что вы делаете, это проверка root, то есть потенциал для этого с битовой картой, чтобы получить попадания L3. Я смотрел на задержку, но много промахов может быть в полете одновременно, поэтому пропускная способность потенциально хорошая. OTOH, sqrtpsпропускная способность SIMD или даже sqrtpd(двойная точность) не так уж и плоха для Skylake, но не намного лучше, чем задержка на старых процессорах. В любом случае 7-cpu.com/cpu/Haswell.html имеет несколько хороших экспериментальных номеров и страниц для других процессоров. В справочнике по микроархам Agner Fog pdf приведены некоторые значения задержки кэша для Intel и AMD: agner.org/optimize
    Peter Cordes 31.10.2018 09:47:39
    Использование x86 SIMD из Java является проблемой, и к тому времени, когда вы добавите стоимость преобразования int-> fp и fp-> int, вполне вероятно, что растровое изображение может быть лучше. Вам нужна doubleточность, чтобы избежать округления некоторого целого числа вне диапазона + -2 ^ 24 (так что 32-разрядное целое число может быть вне этого), и sqrtpdоно медленнее, чем sqrtpsобработка только половины числа элементов на инструкцию (для вектора SIMD) ,
    Peter Cordes 31.10.2018 09:52:38

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

    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очень быстрый, поскольку он превращает JIT-ed в одну инструкцию i86.

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

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

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

    368
    15.02.2018 20:18:41
    Эта скрытая маскировка значения сдвига - это немного ... зло. У вас есть идея, почему это в спецификации Java?
    dfeuer 11.07.2014 01:04:04
    @ Dfeuer Я думаю, есть две причины: 1. Сдвиг на большее не имеет смысла. 2. Это похоже на то, что HW работает, и любой, кто использует побитовые операции, заинтересован в производительности, поэтому делать что-либо еще было бы неправильно. -goodMask тест это делает, но он делает это прежде , чем сдвиг вправо. Так что вам придется повторить это, но так проще и AFAIK чуть-чуть быстрее и одинаково хорошо.
    maaartinus 11.07.2014 14:55:13
    @dfeuer Для теста важно дать ответ КАК МОЖНО СКОРЕЕ, а сам конечный нулевой счет не дает ответа; это просто подготовительный шаг. i86 / amd64 делают это. Не имею понятия о небольших процессорах в мобильных устройствах, но в худшем случае Java должна сгенерировать для них инструкцию AND, которая, безусловно, проще, чем наоборот.
    maaartinus 11.07.2014 15:24:17
    @Sebastian Вероятно, лучший тест if ((x & (7 | Integer.MIN_VALUE)) != 1) return x == 0;.
    maaartinus 4.08.2016 16:59:05
    «Поскольку в double есть только 56- битная мантисса» -> я бы сказал, что она имеет 53-битную . Также
    chux - Reinstate Monica 23.03.2017 14:51:21

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

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

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

    11
    16.10.2013 10:18:53
    На самом деле время должно быть, по крайней мере, O((log n)^2)потому что умножение не является постоянным временем, но на самом деле имеет нижнюю границу O(log n), которая становится очевидной при работе с большими числами с множественной точностью. Но объем этой вики кажется 64-битным, так что, возможно, это nbd.
    user2975337 14.07.2015 02:05:18

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

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

    10
    13.07.2014 19:24:11
    Результаты здесь . Удаление первого теста плохо, так как в большинстве случаев оно решается довольно дешево. Источник в моем ответе (обновлено).
    maaartinus 16.07.2014 11:45:46

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

    public static boolean isRootWhole(double number) {
        return Math.sqrt(number) % 1 == 0;
    }

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

    На моем 3,6 ГГц процессоре Intel i7-4790 запуск этого алгоритма на 0–10 000 000 занял в среднем 35–37 наносекунд на расчёт. Я сделал 10 последовательных прогонов, напечатав среднее время, затраченное на каждый из десяти миллионов квадратных расчетов. Каждый полный прогон занимал чуть более 600 мсек.

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

    0
    5.12.2017 12:45:34
    Я думаю, что вы имеете в виду(long) Math.pow(roundedRoot, 2)
    Stefan Reich 4.12.2017 12:52:28
    Я обновил это решение / предложение, чтобы быть самым простым способом понять это. Интересно, как это будет сравниваться с точки зрения сравнения с некоторыми из пользовательских решений.
    Steve Storck 5.12.2017 11:03:23
    Ваш метод возвращает trueдля 10_000_000_000_000_000Lи 10_000_000_000_000_001Lэто доказывает , что it't неправильно.
    aventurin 13.10.2018 21:44:59

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

    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);
        }
    }
    -1
    26.09.2018 16:32:44
    К сожалению, это алгоритм O (N ^ .5), поэтому он очень плохо относится к скорости и длится вечно для 63-битных чисел, которые могут быть введены. Я изменил свое upvode на downvote. О чем я думал, когда проголосовал за это. По крайней мере, идея, стоящая за этим, верна, но я не проверял это.
    Albert van der Horst 27.12.2018 11:57:18