является - проверка на целое число java




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

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

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

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

Новое решение, опубликованное A. Rex , оказалось еще быстрее. При запуске первых 1 миллиарда целых чисел решение требовало только 34% времени, которое использовало исходное решение. В то время как взлом John Carmack немного лучше для небольших значений n , преимущество по сравнению с этим решением довольно мало.

Вот решение A. Rex, преобразованное в Java:

private final static boolean isPerfectSquare(long n)
{
  // Quickfail
  if( n < 0 || ((n&2) != 0) || ((n & 7) == 5) || ((n & 11) == 8) )
    return false;
  if( n == 0 )
    return true;

  // Check mod 255 = 3 * 5 * 17, for fun
  long y = n;
  y = (y & 0xffffffffL) + (y >> 32);
  y = (y & 0xffffL) + (y >> 16);
  y = (y & 0xffL) + ((y >> 8) & 0xffL) + (y >> 16);
  if( bad255[(int)y] )
      return false;

  // Divide out powers of 4 using binary search
  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;

  if((n & 0x7L) != 1)
      return false;

  // Compute sqrt using something like Hensel's lemma
  long r, t, z;
  r = start[(int)((n >> 3) & 0x3ffL)];
  do {
    z = n - 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 <= (1L << 33) );
  return false;
}

private static boolean[] bad255 =
{
   false,false,true ,true ,false,true ,true ,true ,true ,false,true ,true ,true ,
   true ,true ,false,false,true ,true ,false,true ,false,true ,true ,true ,false,
   true ,true ,true ,true ,false,true ,true ,true ,false,true ,false,true ,true ,
   true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,false,true ,false,
   true ,true ,true ,false,true ,true ,true ,true ,false,true ,true ,true ,false,
   true ,false,true ,true ,false,false,true ,true ,true ,true ,true ,false,true ,
   true ,true ,true ,false,true ,true ,false,false,true ,true ,true ,true ,true ,
   true ,true ,true ,false,true ,true ,true ,true ,true ,false,true ,true ,true ,
   true ,true ,false,true ,true ,true ,true ,false,true ,true ,true ,false,true ,
   true ,true ,true ,false,false,true ,true ,true ,true ,true ,true ,true ,true ,
   true ,true ,true ,true ,true ,false,false,true ,true ,true ,true ,true ,true ,
   true ,false,false,true ,true ,true ,true ,true ,false,true ,true ,false,true ,
   true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,false,true ,true ,
   false,true ,false,true ,true ,false,true ,true ,true ,true ,true ,true ,true ,
   true ,true ,true ,true ,false,true ,true ,false,true ,true ,true ,true ,true ,
   false,false,true ,true ,true ,true ,true ,true ,true ,false,false,true ,true ,
   true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,false,false,
   true ,true ,true ,true ,false,true ,true ,true ,false,true ,true ,true ,true ,
   false,true ,true ,true ,true ,true ,false,true ,true ,true ,true ,true ,false,
   true ,true ,true ,true ,true ,true ,true ,true ,false,false,true ,true ,false,
   true ,true ,true ,true ,false,true ,true ,true ,true ,true ,false,false,true ,
   true ,false,true ,false,true ,true ,true ,false,true ,true ,true ,true ,false,
   true ,true ,true ,false,true ,false,true ,true ,true ,true ,true ,true ,true ,
   true ,true ,true ,true ,true ,false,true ,false,true ,true ,true ,false,true ,
   true ,true ,true ,false,true ,true ,true ,false,true ,false,true ,true ,false,
   false,true ,true ,true ,true ,true ,false,true ,true ,true ,true ,false,true ,
   true ,false,false,true ,true ,true ,true ,true ,true ,true ,true ,false,true ,
   true ,true ,true ,true ,false,true ,true ,true ,true ,true ,false,true ,true ,
   true ,true ,false,true ,true ,true ,false,true ,true ,true ,true ,false,false,
   true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,
   false,false,true ,true ,true ,true ,true ,true ,true ,false,false,true ,true ,
   true ,true ,true ,false,true ,true ,false,true ,true ,true ,true ,true ,true ,
   true ,true ,true ,true ,true ,false,true ,true ,false,true ,false,true ,true ,
   false,true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,false,
   true ,true ,false,true ,true ,true ,true ,true ,false,false,true ,true ,true ,
   true ,true ,true ,true ,false,false,true ,true ,true ,true ,true ,true ,true ,
   true ,true ,true ,true ,true ,true ,false,false,true ,true ,true ,true ,false,
   true ,true ,true ,false,true ,true ,true ,true ,false,true ,true ,true ,true ,
   true ,false,true ,true ,true ,true ,true ,false,true ,true ,true ,true ,true ,
   true ,true ,true ,false,false
};

private static int[] start =
{
  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
};

Я попробовал различные решения, представленные ниже.

  • После исчерпывающего тестирования я обнаружил, что добавление 0.5 к результату Math.sqrt () не требуется, по крайней мере, на моей машине.
  • Взлом Джона Кармака был быстрее, но он дал неверные результаты, начиная с n = 410881. Однако, как предложил BobbyShaftoe , мы можем использовать взлом Carmack для n <410881.
  • Метод Ньютона был немного медленнее, чем Math.sqrt() . Вероятно, это связано с Math.sqrt() что Math.sqrt() использует нечто похожее на метод Ньютона, но реализовано в аппаратном обеспечении, поэтому оно намного быстрее, чем в Java. Кроме того, метод Ньютона по-прежнему требует использования удвоений.
  • Модифицированный метод Ньютона, который использовал несколько трюков, чтобы задействовать только целую математику, потребовал некоторых хаков, чтобы избежать переполнения (я хочу, чтобы эта функция работала со всеми положительными 64-разрядными целыми Math.sqrt() ), и она все еще была медленнее, чем Math.sqrt() .
  • Двоичная отбивная была еще медленнее. Это имеет смысл, потому что бинарная отбивная в среднем потребует 16 проходов, чтобы найти квадратный корень из 64-битного числа.

Одно предложение, которое показало улучшения, было сделано Джоном Д. Куком . Вы можете заметить, что последняя шестнадцатеричная цифра (т. Е. Последние 4 бита) идеального квадрата должна быть 0, 1, 4 или 9. Это означает, что 75% чисел могут быть немедленно устранены как возможные квадраты. Внедрение этого решения привело к сокращению времени выполнения на 50%.

Работая по предложению Джона, я исследовал свойства последних n бит идеального квадрата. Анализируя последние 6 бит, я обнаружил, что только 12 из 64 значений возможны для последних 6 бит. Это означает, что 81% значений можно исключить без использования математики. Реализация этого решения дала дополнительное 8% -ное сокращение времени выполнения (по сравнению с моим первоначальным алгоритмом). Анализ более 6 бит приводит к списку возможных конечных бит, который слишком велик, чтобы быть практичным.

Вот код, который я использовал, который выполняется в 42% времени, требуемого исходным алгоритмом (на основе пробега по первым 100 миллионам целых чисел). При значениях n менее 410881 он работает только в 29% времени, требуемого исходным алгоритмом.

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

  switch((int)(n & 0x3F))
  {
  case 0x00: case 0x01: case 0x04: case 0x09: case 0x10: case 0x11:
  case 0x19: case 0x21: case 0x24: case 0x29: case 0x31: case 0x39:
    long sqrt;
    if(n < 410881L)
    {
      //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);
      i  = 0x5f3759df - ( i >> 1 );
      y  = Float.intBitsToFloat(i);
      y  = y * ( 1.5F - ( x2 * y * y ) );

      sqrt = (long)(1.0F/y);
    }
    else
    {
      //Carmack hack gives incorrect answer for n >= 410881.
      sqrt = (long)Math.sqrt(n);
    }
    return sqrt*sqrt == n;

  default:
    return false;
  }
}

Примечания :

  • Согласно испытаниям Джона, использование or инструкции быстрее на C ++, чем использование switch , но в Java и C #, по-видимому, нет разницы между or switch .
  • Я также попытался создать таблицу поиска (как частный статический массив из 64 булевых значений). Тогда вместо какого-либо переключателя или оператора я бы просто сказал if(lookup[(int)(n&0x3F)]) { test } else return false; , К моему удивлению, это было (чуть-чуть) медленнее. Я не знаю, почему. Это связано с тем, что границы массива отмечены на Java .

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

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

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


Я выяснил метод, который работает на 35% быстрее, чем ваш код 6bits + 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 остатков mod 255 являются квадратами. Однако, по моему опыту, вызов оператора modulo (%) стоит дороже, чем выигрыш, поэтому я использую битовые трюки с 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 как наибольшую степень 2, делящую z на бит трюк. Это позволяет мне пропускать значения t, которые не повлияли бы на значение r в любом случае. Предварительно вычисленное начальное значение в моем случае выбирает «наименьший положительный» квадратный корень по модулю 8192.

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

typedef signed long long int int64;

int start[1024] =
{1,3,1769,5,1937,1741,7,1451,479,157,9,91,945,659,1817,11,
1983,707,1321,1211,1071,13,1479,405,415,1501,1609,741,15,339,1703,203,
129,1411,873,1669,17,1715,1145,1835,351,1251,887,1573,975,19,1127,395,
1855,1981,425,453,1105,653,327,21,287,93,713,1691,1935,301,551,587,
257,1277,23,763,1903,1075,1799,1877,223,1437,1783,859,1201,621,25,779,
1727,573,471,1979,815,1293,825,363,159,1315,183,27,241,941,601,971,
385,131,919,901,273,435,647,1493,95,29,1417,805,719,1261,1177,1163,
1599,835,1367,315,1361,1933,1977,747,31,1373,1079,1637,1679,1581,1753,1355,
513,1539,1815,1531,1647,205,505,1109,33,1379,521,1627,1457,1901,1767,1547,
1471,1853,1833,1349,559,1523,967,1131,97,35,1975,795,497,1875,1191,1739,
641,1149,1385,133,529,845,1657,725,161,1309,375,37,463,1555,615,1931,
1343,445,937,1083,1617,883,185,1515,225,1443,1225,869,1423,1235,39,1973,
769,259,489,1797,1391,1485,1287,341,289,99,1271,1701,1713,915,537,1781,
1215,963,41,581,303,243,1337,1899,353,1245,329,1563,753,595,1113,1589,
897,1667,407,635,785,1971,135,43,417,1507,1929,731,207,275,1689,1397,
1087,1725,855,1851,1873,397,1607,1813,481,163,567,101,1167,45,1831,1205,
1025,1021,1303,1029,1135,1331,1017,427,545,1181,1033,933,1969,365,1255,1013,
959,317,1751,187,47,1037,455,1429,609,1571,1463,1765,1009,685,679,821,
1153,387,1897,1403,1041,691,1927,811,673,227,137,1499,49,1005,103,629,
831,1091,1449,1477,1967,1677,697,1045,737,1117,1737,667,911,1325,473,437,
1281,1795,1001,261,879,51,775,1195,801,1635,759,165,1871,1645,1049,245,
703,1597,553,955,209,1779,1849,661,865,291,841,997,1265,1965,1625,53,
1409,893,105,1925,1297,589,377,1579,929,1053,1655,1829,305,1811,1895,139,
575,189,343,709,1711,1139,1095,277,993,1699,55,1435,655,1491,1319,331,
1537,515,791,507,623,1229,1529,1963,1057,355,1545,603,1615,1171,743,523,
447,1219,1239,1723,465,499,57,107,1121,989,951,229,1521,851,167,715,
1665,1923,1687,1157,1553,1869,1415,1749,1185,1763,649,1061,561,531,409,907,
319,1469,1961,59,1455,141,1209,491,1249,419,1847,1893,399,211,985,1099,
1793,765,1513,1275,367,1587,263,1365,1313,925,247,1371,1359,109,1561,1291,
191,61,1065,1605,721,781,1735,875,1377,1827,1353,539,1777,429,1959,1483,
1921,643,617,389,1809,947,889,981,1441,483,1143,293,817,749,1383,1675,
63,1347,169,827,1199,1421,583,1259,1505,861,457,1125,143,1069,807,1867,
2047,2045,279,2043,111,307,2041,597,1569,1891,2039,1957,1103,1389,231,2037,
65,1341,727,837,977,2035,569,1643,1633,547,439,1307,2033,1709,345,1845,
1919,637,1175,379,2031,333,903,213,1697,797,1161,475,1073,2029,921,1653,
193,67,1623,1595,943,1395,1721,2027,1761,1955,1335,357,113,1747,1497,1461,
1791,771,2025,1285,145,973,249,171,1825,611,265,1189,847,1427,2023,1269,
321,1475,1577,69,1233,755,1223,1685,1889,733,1865,2021,1807,1107,1447,1077,
1663,1917,1129,1147,1775,1613,1401,555,1953,2019,631,1243,1329,787,871,885,
449,1213,681,1733,687,115,71,1301,2017,675,969,411,369,467,295,693,
1535,509,233,517,401,1843,1543,939,2015,669,1527,421,591,147,281,501,
577,195,215,699,1489,525,1081,917,1951,2013,73,1253,1551,173,857,309,
1407,899,663,1915,1519,1203,391,1323,1887,739,1673,2011,1585,493,1433,117,
705,1603,1111,965,431,1165,1863,533,1823,605,823,1179,625,813,2009,75,
1279,1789,1559,251,657,563,761,1707,1759,1949,777,347,335,1133,1511,267,
833,1085,2007,1467,1745,1805,711,149,1695,803,1719,485,1295,1453,935,459,
1151,381,1641,1413,1263,77,1913,2005,1631,541,119,1317,1841,1773,359,651,
961,323,1193,197,175,1651,441,235,1567,1885,1481,1947,881,2003,217,843,
1023,1027,745,1019,913,717,1031,1621,1503,867,1015,1115,79,1683,793,1035,
1089,1731,297,1861,2001,1011,1593,619,1439,477,585,283,1039,1363,1369,1227,
895,1661,151,645,1007,1357,121,1237,1375,1821,1911,549,1999,1043,1945,1419,
1217,957,599,571,81,371,1351,1003,1311,931,311,1381,1137,723,1575,1611,
767,253,1047,1787,1169,1997,1273,853,1247,413,1289,1883,177,403,999,1803,
1345,451,1495,1093,1839,269,199,1387,1183,1757,1207,1051,783,83,423,1995,
639,1155,1943,123,751,1459,1671,469,1119,995,393,219,1743,237,153,1909,
1473,1859,1705,1339,337,909,953,1771,1055,349,1993,613,1393,557,729,1717,
511,1533,1257,1541,1425,819,519,85,991,1693,503,1445,433,877,1305,1525,
1601,829,809,325,1583,1549,1991,1941,927,1059,1097,1819,527,1197,1881,1333,
383,125,361,891,495,179,633,299,863,285,1399,987,1487,1517,1639,1141,
1729,579,87,1989,593,1907,839,1557,799,1629,201,155,1649,1837,1063,949,
255,1283,535,773,1681,461,1785,683,735,1123,1801,677,689,1939,487,757,
1857,1987,983,443,1327,1267,313,1173,671,221,695,1509,271,1619,89,565,
127,1405,1431,1659,239,1101,1159,1067,607,1565,905,1755,1231,1299,665,373,
1985,701,1879,1221,849,627,1465,789,543,1187,1591,923,1905,979,1241,181};

bool bad255[512] =
{0,0,1,1,0,1,1,1,1,0,1,1,1,1,1,0,0,1,1,0,1,0,1,1,1,0,1,1,1,1,0,1,
 1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,0,1,1,1,
 0,1,0,1,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1,1,0,0,1,1,1,1,1,1,1,1,0,1,
 1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,1,1,0,1,1,1,1,0,0,1,1,1,1,1,1,
 1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,0,1,1,0,1,1,1,1,1,
 1,1,1,1,1,1,0,1,1,0,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,1,
 1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,
 1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,
 0,0,1,1,0,1,1,1,1,0,1,1,1,1,1,0,0,1,1,0,1,0,1,1,1,0,1,1,1,1,0,1,
 1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,0,1,1,1,
 0,1,0,1,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1,1,0,0,1,1,1,1,1,1,1,1,0,1,
 1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,1,1,0,1,1,1,1,0,0,1,1,1,1,1,1,
 1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,0,1,1,0,1,1,1,1,1,
 1,1,1,1,1,1,0,1,1,0,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,1,
 1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,
 1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,
 0,0};

inline bool square( int64 x ) {
    // Quickfail
    if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) )
        return false;
    if( x == 0 )
        return true;

    // Check mod 255 = 3 * 5 * 17, for fun
    int64 y = x;
    y = (y & 4294967295LL) + (y >> 32);
    y = (y & 65535) + (y >> 16);
    y = (y & 255) + ((y >> 8) & 255) + (y >> 16);
    if( bad255[y] )
        return false;

    // Divide out powers of 4 using binary search
    if((x & 4294967295LL) == 0)
        x >>= 32;
    if((x & 65535) == 0)
        x >>= 16;
    if((x & 255) == 0)
        x >>= 8;
    if((x & 15) == 0)
        x >>= 4;
    if((x & 3) == 0)
        x >>= 2;

    if((x & 7) != 1)
        return false;

    // Compute sqrt using something like Hensel's lemma
    int64 r, t, z;
    r = start[(x >> 3) & 1023];
    do {
        z = x - r * r;
        if( z == 0 )
            return true;
        if( z < 0 )
            return false;
        t = z & (-z);
        r += (z & t) >> 1;
        if( r > (t  >> 1) )
            r = t - r;
    } while( t <= (1LL << 33) );

    return false;
}

Я думал о страшных временах, которые я провел в курсе «Численный анализ».

И затем я помню, что эта функция вращалась вокруг «сети» из кода Quake Source:

float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;  // evil floating point bit level hacking
  i  = 0x5f3759df - ( i >> 1 ); // wtf?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

  #ifndef Q3_VM
  #ifdef __linux__
    assert( !isnan(y) ); // bk010122 - FPE?
  #endif
  #endif
  return y;
}

Который в основном вычисляет квадратный корень, используя функцию аппроксимации Ньютона (не помню точное имя).

Он должен быть полезен и может быть даже быстрее, это от одной из игр феноменального идентификационного программного обеспечения!

Он написан на C ++, но не следует слишком сложно повторно использовать ту же технику на Java, как только вы получите идею:

Я изначально нашел его по адресу: http://www.codemaestro.com/reviews/9

Метод Ньютона объясняется в Википедии: http://en.wikipedia.org/wiki/Newton%27s_method

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

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

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

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


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

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

Таким образом, вычисленные n^2варианты:

  • n^2 = target : done, return true
  • n^2 + 2n + 1 > target > n^2 : вы близки, но это не идеально: return false
  • n^2 - 2n + 1 < target < n^2 : то же самое
  • target < n^2 - 2n + 1 : бинарная отбивная на нижней n
  • target > n^2 + 2n + 1 : бинарная отбивная на более высокой n

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

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

EDIT: бинарная отбивная не должна принимать во всем диапазоне целых чисел, (2^x)^2 = 2^(2x)так что, как только вы найдете верхний бит в своей цели (что может быть сделано с помощью трюка с битой, я забываю, как именно) вы можете быстро получить ряд потенциальных ответов. Имейте в виду, что наивная бинарная отбивная по-прежнему будет занимать до 31 или 32 итераций.


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


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

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

m = N - (N & (N-1));

а не как написано

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

m = N & (N-1); // the lawest bit of N
N /= m;
byte = N & 0x0F;
if ((m % 2) || (byte !=1 && byte !=9))
  return false;

1st Edit:

Незначительное улучшение:

m = N & (N-1); // the lawest bit of N
N /= m;
if ((m % 2) || (N & 0x07 != 1))
  return false;

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

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


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

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


Это переделка из десятичного в двоичный файл старого алгоритма калькулятора Marchant (извините, у меня нет ссылки), в 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;
};

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

  • Тест Mod-256
  • Неточный тест мод-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;
        }
    }

}

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

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

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


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

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

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


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

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


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


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

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

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);
}

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

Это должно быть возможно, чтобы упаковать «не может быть идеальным квадратом, если последние X цифры N» намного эффективнее этого! Я буду использовать 32-битные int 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, просмотрите историю изменений, чтобы увидеть.)


Это должно быть намного быстрее, чтобы использовать http://en.wikipedia.org/wiki/Newton%27s_method для вычисления Целочисленного квадратного корня , затем квадрат этого числа и проверку, как и в текущем решении. Метод Ньютона является основой решения Кармака, упомянутого в некоторых других ответах. Вы должны иметь возможность получить более быстрый ответ, так как вас интересует только целочисленная часть корня, что позволяет вам быстрее остановить алгоритм аппроксимации.

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


Я не уверен, будет ли это быстрее или даже точно, но вы можете использовать http://www.codemaestro.com/reviews/9 , алгоритм для более быстрого решения квадратного корня. Вероятно, вы можете легко протестировать это для всех возможных 32-битных целых чисел и проверить, что вы действительно получили правильные результаты, поскольку это всего лишь аппроксимация. Однако теперь, когда я думаю об этом, использование удвоений также приближается, поэтому я не уверен, как это вступает в игру.


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

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

Однако эта простая строка, которая в большинстве случаев добавляет одну или две очень быстрые инструкции, значительно упрощает switch-caseутверждение в один оператор if. Тем не менее, это может добавить к времени выполнения, если многие из тестируемых номеров имеют значительную силу двух факторов.

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

  • Интернет - ответ Кипа
  • Durron - Мой измененный ответ, используя однопроходный ответ в качестве базы
  • DurronTwo - Мой измененный ответ, используя двухпроходный ответ (by @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, но не является оптимальным, но явно улучшенным с а 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






perfect-square