java - 확인 - 정수 제곱근 판별 c++




정수의 제곱근이 정수인지 확인하는 가장 빠른 방법 (20)

나는이 함수가 모든 긍정적 인 64 비트 부호있는 정수로 작업되기를 바란다.

Math.sqrt()입력 매개 변수로 double을 사용하므로 2 ^ 53 보다 큰 정수에 대해서는 정확한 결과를 얻지 못합니다 .

long 값이 완벽한 제곱인지 (즉 제곱근이 또 다른 정수인지)를 결정하는 가장 빠른 방법을 찾고있다.

  1. 내장 된 Math.sqrt () 함수를 사용하여 쉬운 방법을 시도했지만, 정수 전용 도메인으로 제한함으로써 더 빨리 수행 할 수있는 방법이 있는지 궁금합니다.
  2. 룩업 테이블을 유지 보수하는 것은 충격적이다 (정사각형이 2 63 미만인 2 31.5 정수가 있기 때문에).

여기 내가 지금하고있는 매우 간단하고 직접적인 방법이있다.

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

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

Notes : 많은 Project Euler 문제에서이 함수를 사용하고 있습니다. 따라서 아무도이 코드를 유지할 필요가 없습니다. 그리고 이런 종류의 마이크로 최적화는 실제로 효과를 낼 수 있습니다. 도전 과제의 일부는 1 분 안에 모든 알고리즘을 수행하는 것이므로이 기능은 몇 가지 문제에서 수백만 번 호출해야합니다.

A. Rex 가 게시 한 새로운 솔루션은 더욱 빨라졌습니다. 처음 10 억 개의 정수를 처리 할 때이 솔루션은 원래 솔루션이 사용한 시간의 34 % 만 필요했습니다. John Carmack 해킹은 n 값이 작을 때 조금 나아졌지만이 솔루션과 비교했을 때 이점은 매우 적습니다.

다음은 Java로 변환 된 A. Rex 솔루션입니다.

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

나는 아래에 제시된 다른 해결책을 시도했다.

  • 철저한 테스트를 거친 후 Math.sqrt () 결과에 0.5 를 더하는 것이 반드시 필요하지는 않습니다. 적어도 내 컴퓨터에는 없습니다.
  • John Carmack 해킹 은 더 빠르지 만 n = 410881에서 시작하여 잘못된 결과를 나타냅니다. 그러나 BobbyShaftoe 제안한대로 Carmack 해킹을 사용할 수 있습니다 (410881).
  • 뉴턴의 방법은 Math.sqrt() 보다 느린 속도였습니다. 이것은 Math.sqrt() 가 Newton 's Method와 비슷한 것을 사용하지만 하드웨어에 구현되어 Java보다 훨씬 빠르기 때문일 수 있습니다. 또한, 뉴턴의 방법은 여전히 ​​복식의 사용이 필요했습니다.
  • 정수 수학 만 포함되도록 몇 가지 트릭을 사용하는 수정 된 Newton의 방법은 오버플로를 피하기 위해 몇 가지 해킹이 필요했습니다. (이 함수가 모든 64 비트 부호있는 정수에서 작동하도록하고 싶습니다.) Math.sqrt() 보다 여전히 느립니다. Math.sqrt() .
  • 2 진 절단은 더 느렸다. 64 비트 숫자의 제곱근을 찾기 위해 평균적으로 16 패스가 필요하기 때문에이 의미가 있습니다.

개선을 보여준 한 가지 제안은 John D. Cook 이 만들었습니다. 완벽한 사각형의 마지막 16 진수 (즉, 마지막 4 비트)는 0, 1, 4 또는 9 여야합니다. 즉, 75 %의 숫자를 가능한 제곱으로 즉시 제거 할 수 있습니다. 이 솔루션을 구현하면 런타임이 약 50 % 단축되었습니다.

John의 제안에 따라 완벽한 사각형의 마지막 n 비트의 속성을 조사했습니다. 마지막 6 비트를 분석하여 64 비트 중 12 비트 만 마지막 6 비트에서 가능하다는 것을 알았습니다. 즉, 수학을 사용하지 않고도 81 %의 값을 제거 할 수 있습니다. 이 솔루션을 구현하면 원래 알고리즘과 비교하여 런타임이 8 % 감소합니다. 6 비트 이상을 분석하면 가능한 종료 비트 목록이 너무 커서 실용적이지 않습니다.

다음은 내가 사용한 코드입니다. 원래 알고리즘에 필요한 시간의 42 % (처음 1 억 개의 정수를 기반으로 실행)에 실행됩니다. 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;
  }
}

참고 사항 :

  • John의 테스트에 따르면 C or C ++에서는 switch 사용하는 것이 더 빠르지 만 Java 및 C #에서는 orswitch 사이에 차이가없는 것처럼 보입니다.
  • 또한 조회 테이블을 64 개의 부울 값으로 이루어진 개인 정적 배열로 만들려고했습니다. 다음 switch 또는 or 대신에 if(lookup[(int)(n&0x3F)]) { test } else return false; . 놀랍게도, 이것은 (단지 약간) 느려졌습니다. 이유가 확실하지 않습니다. 배열 경계가 Java에서 검사 되기 때문입니다.

정수 연산을 이용한 뉴턴의 방법

정수가 아닌 연산을 피하려면 아래 방법을 사용할 수 있습니다. 기본적으로 정수 연산을 위해 수정 된 Newton 's Method를 사용합니다.

/**
 * 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. 그러나 다른 게시물에 설명 된 필터링 메커니즘을 사용하여 성능을 향상시킬 수 있습니다.


나는 적어도 CPU (x86)와 프로그래밍 언어 (C / C ++)에서 ~ 6 % + Carmack + sqrt 코드보다 35 % 빠른 방법을 찾아 냈습니다. 귀하의 결과는 다를 수 있습니다. 특히 자바 요소가 어떻게 재생 될지 모르겠다.

내 접근 방식은 세 가지입니다.

  1. 먼저 명백한 답변을 필터링하십시오. 여기에는 음수가 포함되고 마지막 4 비트가 표시됩니다. (나는 마지막 6 개를 보는 것이 도움이되지 않는다는 것을 알았습니다.) 또한 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인지 확인하십시오. 3 개의 별개 소수의 결과이므로 잔여 모듈 255 개 중 1/8 만 정사각형입니다. 그러나, 제 경험상, 모듈러스 연산자 (%)를 호출하면 얻는 이익보다 비용이 많이 들기 때문에 255 = 2 ^ 8-1의 비트 트릭을 사용하여 나머지를 계산합니다. (더 좋든 나 나쁘 든간에, 나는 개별 바이트를 하나의 단어에서 읽는 트릭을 쓰지 않고 bitwise와 shift 만 사용한다.)
    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. 마지막으로 Hensel의 보조 정리 와 유사한 방법을 사용하여 제곱근을 계산합니다. (직접 적용 할 수는 없다고 생각하지만 약간의 수정으로 작동합니다.)이를 수행하기 전에 이진 검색을 사용하여 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.
    아이디어는 각 반복에서 x의 "현재"제곱근 인 r에 1 비트를 더하는 것입니다. 각 제곱근은 2의 크고 큰 힘, 즉 t / 2를 모듈로 (modulo)로 정확하게 나타냅니다. 결국, r과 t / 2-r은 x 모듈로 t / 2의 제곱근이 될 것입니다. (r이 x의 제곱근이라면 -r도 마찬가지이다. 이것은 모듈로 숫자 일지라도 몇 가지 숫자를 고려해야하며 두 가지 이상의 제곱근을 가질 수 있음을주의해야한다. 특히 이것은 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를 나눌 수있는 가장 큰 힘으로 설정합니다. 이것은 내가 어쨌든 r의 값에 영향을 미치지 않았던 t 값을 건너 뛸 수있게 해줍니다. 필자의 경우 사전 계산 된 시작 값은 모듈러스 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;
}

몇 가지 벤치마킹을해야 할 것입니다. 최상의 알고리즘은 입력 값의 분포에 따라 달라집니다.

알고리즘은 거의 최적 일 수 있지만, 제곱근 루틴을 호출하기 전에 몇 가지 가능성을 배제하기 위해 빠른 점검을하고 싶을 수도 있습니다. 예를 들어, 비트 단위의 "and"를 사용하여 16 진수의 마지막 숫자를 살펴보십시오. 완벽한 사각형은 기본 16에서 0, 1, 4 또는 9로 끝날 수 있습니다. 따라서 입력의 75 % (균등 분포라고 가정)에 대해 매우 빠른 비트 트위 더링 대신에 제곱근 호출을 피할 수 있습니다.

킵은 16 진수 트릭을 구현하는 다음 코드를 벤치 마크했습니다. 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 문을 제거하면 16 진수 트릭이 다시 한 번 코드를 두 배 빠르게 만듭니다.

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 # 코드에 거의 영향을 미치지 않습니다.


"올바른"제곱근을 찾기 위해 바이너리 ch핑을하면, 가지고있는 값이 충분히 알려 졌는지를 쉽게 알 수 있습니다 :

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

따라서 계산 n^2된 옵션은 다음과 같습니다.

  • n^2 = target : 완료, true를 반환합니다.
  • n^2 + 2n + 1 > target > n^2 : 당신은 가깝지만 완벽한 것은 아닙니다 : false를 반환합니다.
  • n^2 - 2n + 1 < target < n^2 : 상동
  • target < n^2 - 2n + 1 : 아래쪽에 바이너리 n
  • target > n^2 + 2n + 1 : 상위에 바이너리 n

죄송합니다. n현재 추측치와 target매개 변수로 사용됩니다. 혼란을 사과하십시오.

이것이 더 빨라질 지 알지 못하지만, 시도해 볼만한 가치가 있습니다.

편집 : 바이너리 does핑은 정수 범위 전체를 차지할 필요가 없으므로 (2^x)^2 = 2^(2x)대상에서 상위 세트 비트를 찾았 으면 (비트 트위 트릭 트릭을 통해 수행 할 수 있음, 정확하게 잊어 버림) 잠재적 인 답변 범위를 빠르게 얻을 수 있습니다. 당신이 생각하기에, 순진한 바이너리 찹은 여전히 ​​단지 31 또는 32 번의 반복을 택할 것입니다.


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;

성능에 영향을 미칩니다.


루비 (Ruby)에서 이전의 Marchant 계산기 알고리즘의 10 진수에서 2 진수로의 재 작업 (미안하지만 참고가 필요하지 않음)

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

다음은 유사한 스타일의 작업입니다 (코딩 스타일 / 냄새 또는 clunky 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 테스트
  • 정확하지 않은 mod-3465 테스트 (일부 오탐 (false positive)을 희생시키면서 정수 나눗셈을 피함)
  • 부동 소수점 제곱근, 반올림 및 입력 값 비교

또한 이러한 수정 작업을 실험했지만 성능에 도움이되지 않았습니다.

  • 추가 mod-255 테스트
  • 입력 값을 4의 제곱으로 나눕니다.
  • Fast Inverse Square Root (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;
        }
    }

}

정수 문제는 정수 해를 얻을 자격이 있습니다. 그러므로

가장 큰 정수 t를 찾기 위해 (음이 아닌) 정수에 대해 이진 탐색을 수행하십시오 t**2 <= n. 그런 다음 r**2 = n정확하게 테스트하십시오 . 이것은 O (log n) 시간이 걸립니다.

집합이 무제한이기 때문에 양의 정수를 이진 검색하는 방법을 모르는 경우 쉽습니다. 여러분은 증가하는 함수 f (위 f(t) = t**2 - n)를 2의 거듭 제곱 으로 계산함으로써 시작합니다 . 당신이 그것을 볼 때 긍정적 인 회전, 당신은 상한을 발견했습니다. 그런 다음 표준 바이너리 검색을 수행 할 수 있습니다.


Integer Square Root 를 계산 하기 위해 http://en.wikipedia.org/wiki/Newton%27s_method 을 사용하는 것이 훨씬 빠르며 , 현재의 솔루션에서와 같이이 숫자를 제곱하고 검사하십시오. 뉴튼의 방법은 몇 가지 다른 답변에서 언급 된 카락 솔루션의 기초입니다. 근사 알고리즘을 더 빨리 중지 할 수 있도록 루트의 정수 부분에만 관심이 있으 G로 더 빠른 응답을 얻을 수 있어야합니다.

시도 할 수있는 또 다른 최적화 : 숫자 의 디지털 루트 가 1, 4, 7 또는 9로 끝나지 않으면 숫자는 완전한 사각형 이 아닙니다 . 이것은 더 느린 제곱근 알고리즘을 적용하기 전에 입력의 60 %를 제거하는 빠른 방법으로 사용될 수 있습니다.


d완벽한 사각형 의 마지막 자릿수는 특정 값만 취할 수 있다는 것이 지적되었습니다 . d숫자 의 마지막 자리수 (기수 b) n는 나머지를 n나눈 값 과 동일합니다 b d. C 표기법 n % pow(b, d).

이것은 모든 계수로 일반화 될 수 있습니다 m. n % m몇 퍼센트의 숫자가 완전한 사각형이되는 것을 배제하는 데 사용할 수 있습니다. 현재 사용중인 모듈러스는 64이므로 12가 허용됩니다. 남은 자의 19 %, 가능한 사각형. 약간의 코딩으로 모듈 2010을 허용하는 모듈 110880을 발견했습니다. 나머지는 가능한 정사각형의 1.8 %. 따라서 모듈러스 연산 (즉, 나눗셈)과 테이블 룩업 대 머신의 제곱근의 비용에 따라이 모듈을 사용하는 것이 더 빠를 수도 있습니다.

그런데 자바가 룩업 테이블을위한 압축 된 비트 배열을 저장하는 방법을 사용한다면 그것을 사용하지 마십시오. 110880 32 비트 단어는 요즘 많은 RAM이 아니며 기계 단어를 가져 오는 것이 단일 비트를 가져 오는 것보다 빠르다.


그것이 더 빠르거나 정확할 지 확신 할 수는 없지만 http://www.codemaestro.com/reviews/9 알고리즘을 사용하면 제곱근을 더 빨리 해결할 수 있습니다. 당신은 아마 모든 가능한 32 비트 정수에 대해 이것을 쉽게 테스트 할 수 있으며, 단지 appoximation 일 뿐이므로 올바른 결과를 얻었음을 검증 할 수 있습니다. 그러나, 이제는 그것에 대해 생각하고, double을 사용하는 것은 근사치이므로, 그것이 어떻게 작용할 지 확신하지 못합니다.


나는 입력의 일부에 거의 정확한 방법을 사용하는 것을 좋아한다. 다음은 "오프셋"이 더 높은 버전입니다. 코드가 작동하고 간단한 테스트 케이스를 통과합니다.

그냥 당신을 대체하십시오 :

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

마지막 X 자릿수가 N보다 훨씬 더 효율적이라면 '완벽한 사각형이 될 수 없다'는 것을 포장 할 수 있어야합니다! java 32 비트 int를 사용하고 마지막 16 비트를 검사 할 수있는 충분한 데이터를 생성합니다. 이는 2048 개의 16 진수 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의 성능 저하 때문에 생략 됨, 업데이트 기록보기)


사각형의 마지막 n 비트가 관찰 될 때 가능한 모든 결과를 확인했습니다. 연속적으로 더 많은 비트를 검사함으로써 최대 5/6 입력을 제거 할 수 있습니다. 사실 Fermat의 Factorization 알고리즘을 구현하기 위해 이것을 설계했으며, 매우 빠릅니다.

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

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

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

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

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

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

의사 코드의 마지막 비트는 더 많은 값을 제거하기 위해 테스트를 확장하는 데 사용될 수 있습니다. 위의 테스트는 k = 0, 1, 2, 3에 대한 것입니다.

  • a는 (3 << 2k) - 1
  • b는 (2 << 2k)
  • c는 (2 << 2k + 2) - 1
  • d는 (2 << 2k-1) * 10

    먼저 2의 거듭 제곱을 가진 제곱 나머지가 있는지 여부를 테스트 한 다음 최종 모듈을 기준으로 테스트 한 다음 Math.sqrt를 사용하여 최종 테스트를 수행합니다. 나는 최고 지위에서 아이디어를 생각해 내고 그것을 확장하려고 시도했다. 나는 어떤 의견이나 제안을 주셔서 감사합니다.

    업데이트 : modulus (modSq) 및 modulus base가 44352 인 테스트를 사용하여 최대 1,000,000,000 개의 숫자에 대한 OP의 업데이트 시간 중 96 %에서 테스트가 실행됩니다.


  • 앞서 언급했듯이 sqrt 호출은 완벽하게 정확하지는 않지만 속도면에서 다른 답변을 날려 버리지는 않는다는 것은 흥미롭고 유익합니다. 결국, sqrt에 대한 어셈블리 언어 명령어 시퀀스는 아주 작습니다. 인텔은 자바에 의해 사용되지 않는 하드웨어 명령어를 가지고 있는데, 나는 그것이 IEEE에 부합하지 않기 때문에 믿는다.

    왜 그렇게 느린가요? Java는 실제로 JNI를 통해 C 루틴을 호출하기 때문에 Java 서브 루틴을 호출하는 것보다 속도가 느려지므로 Java 서브 루틴을 호출하는 것보다 속도가 느립니다. 이것은 매우 성가신 일이며 Java는 더 나은 솔루션, 즉 필요한 경우 부동 소수점 라이브러리 호출을 구축해야합니다. 오 잘.

    C ++에서는 모든 복잡한 대안이 속도면에서 손실 될 것이라고 생각하지만, 모두 체크하지는 않았습니다. 내가 한 일과 자바 사람들이 유용하다고 생각하는 것은 단순한 해킹이며 A. Rex가 제안한 특별한 사례 테스트의 연장입니다. 하나의 long 값을 비트 배열로 사용하십시오. 이는 바운드 검사되지 않습니다. 그렇게하면 64 비트 부울 검색이 생깁니다.

    typedef unsigned long long UVLONG
    UVLONG pp1,pp2;
    
    void init2() {
      for (int i = 0; i < 64; i++) {
        for (int j = 0; j < 64; j++)
          if (isPerfectSquare(i * 64 + j)) {
        pp1 |= (1 << j);
        pp2 |= (1 << i);
        break;
          }
       }
       cout << "pp1=" << pp1 << "," << pp2 << "\n";  
    }
    
    
    inline bool isPerfectSquare5(UVLONG x) {
      return pp1 & (1 << (x & 0x3F)) ? isPerfectSquare(x) : false;
    }
    

    일상적인 isPerfectSquare5는 내 core2 듀오 컴퓨터에서 약 1/3의 시간으로 실행됩니다. 나는 같은 라인을 따라 추가 조정을하면 평균적으로 시간을 줄일 수 있다고 생각하지만, 매번 확인을 할 때 더 많은 테스트를 수행하여 더 많은 제거 작업을 수행하므로 그 도로에서 너무 멀리 갈 수는 없습니다.

    확실히 네거티브에 대한 별도의 테스트를하는 것보다 동일한 방식으로 상위 6 비트를 검사 할 수 있습니다.

    내가하는 모든 일은 가능한 사각형을 제거하는 것이지만, 잠재적 인 경우에는 원래의 인라인 isPerfectSquare를 호출해야합니다.

    init2 루틴은 pp1 및 pp2의 정적 값을 초기화하기 위해 한 번 호출됩니다. C ++에서의 구현에서는 부호없는 long long을 사용하므로 서명을 했으므로 >>> 연산자를 사용해야합니다.

    바운드를 검사 할 본질적인 필요는 없습니다.하지만 Java의 최적화 프로그램은이 문제를 아주 빨리 파악해야하므로, 나는 그것을 비난하지 않습니다.


    여기에 가장 단순하고 간결한 방법이 있지만, CPU 사이클의 관점에서 비교하는 방법을 모르겠습니다. 루트가 정수인지 여부 만 알고 싶다면이 방법이 효과적입니다. 정수인지 정말로 신경 쓰면 알 수 있습니다. 다음은 간단한 (그리고 순수한) 함수입니다 :

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

    미세 최적화가 필요하지 않은 경우이 대답은 단순성과 유지 관리 측면에서 더 좋습니다. 음수를 얻으려면 number 인수에 Math.sqrt () 인수로 Math.abs ()를 사용하는 것이 좋습니다.

    내 3.6Ghz Intel i7-4790 CPU에서 0 - 10,000,000에이 알고리즘을 실행 한 결과 계산 당 평균 35 - 37 나노초 걸렸습니다. 10 천분의 1 sqrt 계산에 소요 된 평균 시간을 인쇄하여 10 순차 실행했습니다. 각각의 총 실행은 완료하는 데 단지 600 밀리 초가 걸렸습니다.

    더 적은 수의 계산을 수행하는 경우 이전 계산이 약간 더 오래 걸립니다.


    이것이 전에 언급되었는지는 모르겠습니다. 하지만 here 해결책을 찾았 here .

    int result = (int)(floor(sqrt(b)) - ceil(sqrt(a)) + 1);
    

    일반적인 비트 길이 (여기에 특정 유형을 사용 했음에도 불구하고)를 고려해 볼 때, 다음과 같이 단순한 알고리즘을 설계하려고했습니다. 처음에는 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;  
    }  
    




    perfect-square