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

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

알 수 있는 long한 제곱 value는 다른 정수입니다.

1. 빌트인 기능을 사용하여 간단하게 했습니다만, 정수 전용의 도메인에 한정하는 것으로, 보다 빠르게 할 수 있는 방법이 없을까요.
2. 룩업 테이블을 유지하는 것은 비현실적입니다(제곱이 2보다 작은⁶³ 정수가 약^31.5 2개 있기 때문입니다).

다음은 매우 단순하고 간단한 방법입니다.

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

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

_{주의: 이 함수는 프로젝트 오일러 문제에서 많이 사용하고 있습니다.다른 누구도 이 코드를 유지할 필요가 없습니다.이러한 미세 최적화는 실제로 차이를 만들 수 있습니다. 왜냐하면 모든 알고리즘을 1분 이내에 실행하는 것이 과제 중 하나이기 때문입니다. 그리고 어떤 문제에서는 이 함수를 수백만 번 호출해야 합니다.}

---

이 문제에 대한 다양한 해결책을 시도해 보았습니다.

• 한 테스트 결과, ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★0.5Math.sqrt()로 지정합니다.최소한 제 머신에서는 필요 없습니다.
• 빠른 역제곱근은 더 빨랐지만, n > = 410881에 대해 잘못된 결과를 얻었다.그러나 BobbyShaftoe의 제안대로 n < 410881에 대해 FISR 해크를 사용할 수 있습니다.
• .Math.sqrt()은 아마 ★★★★★★★★★★★★★★★★★★★★★★★★★Math.sqrt()Newton's Method와 비슷한 것을 사용하지만 하드웨어에 구현되어 있기 때문에 Java보다 훨씬 빠릅니다.또한, 뉴턴의 방법은 여전히 이중의 사용을 요구했습니다.
• 되도록 몇 오버플로를 몇 이 함수는 모든 정수와 ).또, 까지는, 그 는, 보다 . 이치Math.sqrt().
• 바이너리 찹은 더 느렸다.64비트 숫자의 제곱근을 구하려면 평균 16개의 패스가 필요하기 때문에 이는 의미가 있습니다.
• , ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★.or에서는 C++를 이 더 .switch, 와 C C#의 차이는 없는 것으로 or ★★★★★★★★★★★★★★★★★」switch.
• 룩업 테이블(64 부울값의 프라이빗 스태틱 배열)도 작성했습니다.으로 스위치 또는 '''가 아닌or'이렇게 말할게요'라고 하면 요.if(lookup[(int)(n&0x3F)]) { test } else return false;놀랍게도, 이것은 (약간) 느렸다.이는 배열 한계가 Java에서 확인되기 때문입니다.

적어도 CPU(x86)와 프로그래밍 언어(C/C++)로 6bits+Carmack+sqrt 코드보다 최대 35% 빠르게 동작하는 방법을 알아냈습니다.결과가 달라질 수 있습니다. 특히 Java 요소가 어떻게 실행될지 모르기 때문입니다.

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

1. ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★6개를 안 요)(마지막 6개를 살펴봐도 도움이 되지 않았습니다.0에 때 은 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 3 3 3 、 255 = 3 * 5 、 17 인 확 확 확 확 。이 값은 세 개의 서로 다른 소수점들의 곱이므로 잔차 mod 255의 약 1/8만이 제곱입니다.그러나 제 경험상 모듈로 연산자(%)를 호출하는 것은 이득보다 비용이 더 많이 들기 때문에 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;

   18이어야 .

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

   않은 안t=2 또는 8을해 보세요. 't=2' '8' '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에 1비트를 더하는 것입니다. 즉, 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비트 트릭을 사용하여 2 나누기 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;
}

파티에 늦었지만, 더 나은 답변을 드리고 싶습니다. 짧고 (제 벤치마크가 맞다고 가정하면) 훨씬 더 빠릅니다.

long goodMask; // 0xC840C04048404040 computed below
{
    for (int i=0; i<64; ++i) goodMask |= Long.MIN_VALUE >>> (i*i);
}

public boolean isSquare(long x) {
    // This tests if the 6 least significant bits are right.
    // Moving the to be tested bit to the highest position saves us masking.
    if (goodMask << x >= 0) return false;
    final int numberOfTrailingZeros = Long.numberOfTrailingZeros(x);
    // Each square ends with an even number of zeros.
    if ((numberOfTrailingZeros & 1) != 0) return false;
    x >>= numberOfTrailingZeros;
    // Now x is either 0 or odd.
    // In binary each odd square ends with 001.
    // Postpone the sign test until now; handle zero in the branch.
    if ((x&7) != 1 | x <= 0) return x == 0;
    // Do it in the classical way.
    // The correctness is not trivial as the conversion from long to double is lossy!
    final long tst = (long) Math.sqrt(x);
    return tst * tst == x;
}

첫 번째 검정은 대부분의 비제곱을 빠르게 포착합니다.64개 항목의 테이블이 긴 패키지로 구성되어 있으므로 어레이 액세스 비용(인다이렉션 및 경계 검사)이 들지 않습니다. 랜덤의 경우long81.25%로 하다

두 번째 검정은 인수분해에서 홀수 2를 가진 모든 숫자를 포착합니다. 법Long.numberOfTrailingZeros하나의 i86 명령으로 JIT를 처리할 수 있기 때문에 매우 빠릅니다.

후행 0을 삭제한 후 세 번째 검정에서는 011, 101 또는 111로 끝나는 숫자를 2진법으로 처리합니다. 이 숫자는 완벽한 제곱이 아닙니다.또한 음수에도 신경을 쓰고 0도 처리합니다.

은 기말시험으로 된다.double~로~로.double밖에 없습니다.은 53비트로부터의 입니다.long로로 합니다.double에는 큰 값의 반올림이 포함됩니다.그럼에도 불구하고, 그 테스트는 정확하다(증명이 틀리지 않은 한).

mod255 아이디어를 도입하려고 했지만 성공하지 못했습니다.

벤치마킹을 좀 해야 할 것 같아요.최적의 알고리즘은 입력의 분포에 따라 달라집니다.

알고리즘이 거의 최적일 수 있지만 제곱근 루틴을 호출하기 전에 몇 가지 가능성을 배제하기 위해 빠른 체크를 수행하는 것이 좋습니다.예를 들어, 16진수의 마지막 자리수를 비트 단위로 "and"를 실행함으로써 확인합니다.완벽한 정사각형은 베이스 16에서는 0, 1, 4, 또는9로만 끝납니다.따라서 입력의 75%(일률적으로 분포되어 있다고 가정)에 대해서는 매우 빠른 비트아이돌링의 대가로 제곱근 호출을 회피할 수 있습니다.

Kip은 16진법을 구현하기 위해 다음 코드를 벤치마킹했습니다.숫자 1 ~ 100,000,000을 테스트했을 때 이 코드는 원래 코드보다 2배 빠르게 실행되었습니다.

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진법으로 인해 코드가 2배로 빨라집니다.

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

수치 분석 코스에서 보낸 끔찍한 시간들에 대해 생각하고 있었어요.

그리고 기억나는건, 지진 발생원 코드의 '넷'을 돌고 있는 기능이 있었다는 거야.

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

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

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

이는 기본적으로 뉴턴의 근사 함수를 사용하여 제곱근을 계산합니다(정확한 이름을 기억하십시오).

그것은 사용 가능하고 더 빠를지도 모른다. 그것은 경이로운 id 소프트웨어의 게임 중 하나에서 나온 것이다!

C++로 쓰여져 있습니다만, 일단 아이디어를 얻으면 Java에서 같은 기술을 재사용하는 것은 그다지 어렵지 않을 것입니다.

원래 http://www.codemaestro.com/reviews/9에서 찾을 수 있었습니다.

뉴턴의 방법은 위키피디아에서 설명된다: http://en.wikipedia.org/wiki/Newton%27s_method

이 링크에 접속하면, 그 기능에 대한 자세한 설명을 보실 수 있습니다.하지만 별로 신경 쓰지 않으신다면 블로그를 읽고 수치 분석 코스를 수강했을 때 대략 다음과 같이 기억합니다.

• * (long*) &y는 기본적으로 고속 롱 변환 함수이므로 정수 연산을 원시 바이트에 적용할 수 있습니다.
• 0x5f3759df - (i >> 1);line의 시드 값입니다.
• * (float*) &i값을 부동소수로 다시 변환합니다.
• y = y * ( threehalfs - ( x2 * y * y ) )다시 합니다.line은 함수에 대한 값을 반복합니다.

근사 함수는 결과에 대해 함수를 반복할수록 더 정확한 값을 제공합니다.퀘이크의 경우, 한 번 더 반복하면 충분합니다. 하지만 당신이 아니었다면...필요한 만큼 반복할 수 있습니다.

는 는 2의 나눗셈)으로 나눗셈 더 .* 0.5F곱셈 연산) 대신 몇 개의 고정된 곱셈 연산으로 대체합니다.

이게 더 빠를지 정확할지는 모르겠지만존 카맥의 매직 스퀘어 루트를 사용하면 제곱근을 더 빨리 풀 수 있어요가능한 모든 32비트 정수에 대해 쉽게 테스트하고 실제로 올바른 결과를 얻었는지를 확인할 수 있습니다. 이는 단지 추측일 뿐이기 때문입니다.그러나 지금 생각해 보면 더블도 대략적인 것이기 때문에 그것이 어떻게 기능할지는 잘 모르겠습니다.

바이너리 컷을 사용하여 "올바른" 제곱근을 구하면 다음과 같은 값을 얻을 수 있을 만큼 가까운지 여부를 쉽게 검출할 수 있습니다.

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

은 ★★★★★★★★★★★★★★★★★★★★★★★★★★」n^2을 사용하다

• n^2 = target, true: "done, true"
• n^2 + 2n + 1 > target > n^2하지 않다:: 반환 false: 반환 false.false.
• n^2 - 2n + 1 < target < n^2 : ditto (표준)
• target < n^2 - 2n + 1: 아래쪽에 바이너리 컷n
• target > n^2 + 2n + 1더찹 : : : : : 。n

만, 은 ( ( ( ) ), ( )를 사용합니다.ntarget파라미터를 지정합니다.★★★★★★★★★★★★★★★★★★★★★★★★★★★★」

이게 더 빠를지는 모르겠지만 시도해 볼 만해요.

은 정수 포함할 범위: 편 : : 이 : edit 、 edit 、 edit 、 edit 、 edit 、 edit 、 edit 、 edit 、 edit 、 edit 。(2^x)^2 = 2^(2x)따라서 목표의 상위 세트 비트를 찾으면(좀 비틀리는 기술로 할 수 있지만, 어떻게 해야 하는지 정확히 잊어버립니다) 다양한 잠재적 답을 빠르게 얻을 수 있습니다.순진한 바이너리 챕은 아직 31에서 32회밖에 반복되지 않습니다.

저는 이 스레드의 여러 알고리즘에 대한 자체 분석을 실시하여 몇 가지 새로운 결과를 도출했습니다.이 답변의 편집 이력에서 오래된 결과를 볼 수 있지만 정확하지 않습니다. 제가 실수를 했기 때문에 근접하지 않은 여러 알고리즘을 분석하느라 시간을 낭비했습니다.그러나, 몇개의 다른 대답으로부터 교훈을 얻어, 저는 이제 이 스레드의 "승자"를 분쇄하는 두 개의 알고리즘을 가지고 있습니다.다음은 제가 다른 사람들과 다르게 하는 핵심 사항입니다.

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

대부분의 매우 이에서는, 「1」의 「1」의 「2」의 「1」의 「2」의 「1」의 「1」의 「2」의 「1」의 「1」의 「2」의 「1」의 「1」의 「2」의 「2」의 「2」의 「1개의 명령어가 됩니다.switch-case스테이트먼트를 하나의 if 스테이트먼트로 합니다.계수를 있는 할 수 .

다음 알고리즘은 다음과 같습니다.

• 인터넷 - Kip이 올린 답변
• Durron - 원패스 답변을 기반으로 수정한 답변
• DurronTwo - 2패스 답변(@JohnnyHegheim)을 사용하여 수정한 답변입니다.또, 약간의 수정도 가미했습니다.

에서는, 이 가, 「다」를 사용해 .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

첫 번째 100만 Longs에서만 실행되는 경우의 런타임 예를 다음에 나타냅니다.

 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츠키노한 편, 플 meanwhile meanwhile meanwhileDurron첫 번째 백만 개의 숫자를 4로 여러 번 나눌 필요가 없기 때문에 큰 승자입니다.

있습니다Durron:

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

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

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

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

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

★★★★★★★★★★★★★★★★★.DurronTwo

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

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

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

벤치마크 하니스: (Google 캘리퍼 0.1-rc5 필요)

public class SquareRootBenchmark {
    public static class Benchmark1 extends SimpleBenchmark {
        private static final int ARRAY_SIZE = 10000;
        long[] trials = new long[ARRAY_SIZE];

        @Override
        protected void setUp() throws Exception {
            Random r = new Random();
            for (int i = 0; i < ARRAY_SIZE; i++) {
                trials[i] = Math.abs(r.nextLong());
            }
        }


        public int timeInternet(int reps) {
            int trues = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < ARRAY_SIZE; j++) {
                    if(SquareRootAlgs.isPerfectSquareInternet(trials[j])) trues++;
                }
            }

            return trues;   
        }

        public int timeDurron(int reps) {
            int trues = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < ARRAY_SIZE; j++) {
                    if(SquareRootAlgs.isPerfectSquareDurron(trials[j])) trues++;
                }
            }

            return trues;   
        }

        public int timeDurronTwo(int reps) {
            int trues = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < ARRAY_SIZE; j++) {
                    if(SquareRootAlgs.isPerfectSquareDurronTwo(trials[j])) trues++;
                }
            }

            return trues;   
        }
    }

    public static void main(String... args) {
        Runner.main(Benchmark1.class, args);
    }
}

업데이트: 시나리오에 따라서는 더 빠르고, 다른 시나리오에서는 더 느린 새로운 알고리즘을 개발했습니다.입력 내용에 따라 다른 벤치마크를 얻을 수 있습니다.모듈로를 계산하면0xFFFFFF = 3 x 3 x 5 x 7 x 13 x 17 x 241제곱할 수 없는 숫자의 97.82%를 제거할 수 있습니다.이것은 5비트 연산을 사용하여 한 줄로 실행할 수 있습니다.

if (!goodLookupSquares[(int) ((n & 0xFFFFFFl) + ((n >> 24) & 0xFFFFFFl) + (n >> 48))]) return false;

1), 2)잔기, 2)잔기 중 입니다.+ 0xFFFFFF, 3) (3) 잔류물+ 0x1FFFFFE0xFFFFFF 파일은 약 파일 3MB로 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();
}

실행 시 예시.은 it it다 it it it it 。Durron 1을 실행한 마다.

 0% Scenario{vm=java, trial=0, benchmark=Internet} 40665.77 ns; ?=566.71 ns @ 10 trials
33% Scenario{vm=java, trial=0, benchmark=Durron} 38397.60 ns; ?=784.30 ns @ 10 trials
67% Scenario{vm=java, trial=0, benchmark=DurronThree} 36171.46 ns; ?=693.02 ns @ 10 trials

  benchmark   us linear runtime
   Internet 40.7 ==============================
     Durron 38.4 ============================
DurronThree 36.2 ==========================

vm: java
trial: 0

현재 솔루션에서처럼 뉴턴의 방법을 사용하여 정수 제곱근을 계산하고 이 숫자를 제곱하여 확인하는 것이 훨씬 빠를 것입니다.뉴턴의 방법은 다른 답변에서 언급된 카맥 해법의 기초가 된다.루트의 정수 부분에만 관심이 있으므로 근사 알고리즘을 더 빨리 중지할 수 있으므로 더 빠른 답변을 얻을 수 있습니다.

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

이 함수는 모든 양의 64비트 부호 정수와 함께 작동하기를 원합니다.

Math.sqrt()입력 파라미터로서 double과 함께 동작하기 때문에 2^53보다 큰 정수에 대해서는 정확한 결과를 얻을 수 없습니다.

참고로, 또 다른 접근법은 일차 분해법을 사용하는 것입니다.분해의 모든 요인이 짝수이면 숫자는 완벽한 제곱입니다.그래서 여러분이 원하는 것은 어떤 숫자가 소수 제곱의 곱으로 분해될 수 있는지 보는 것입니다.물론 그런 분해는 필요 없습니다.그것이 존재하는지 확인하기 위해서입니다.

먼저 2^32보다 작은 소수들의 제곱 표를 만드세요.이는 이 제한까지의 모든 정수의 표보다 훨씬 작습니다.

솔루션은 다음과 같습니다.

boolean isPerfectSquare(long number)
{
    if (number < 0) return false;
    if (number < 2) return true;

    for (int i = 0; ; i++)
    {
        long square = squareTable[i];
        if (square > number) return false;
        while (number % square == 0)
        {
            number /= square;
        }
        if (number == 1) return true;
    }
}

좀 애매한 것 같아요.소수의 제곱이 입력수를 나누는 모든 단계를 체크하는 것입니다.이 경우 가능한 한 수를 제곱으로 나누어 소수 분해에서 이 제곱을 제거합니다.이 과정을 통해 1이 되면 입력된 숫자는 소수 제곱의 분해가 됩니다.정사각형이 숫자 자체보다 커지면 이 정사각형이나 더 큰 정사각형이 분할할 수 없기 때문에 소수 제곱의 분해가 될 수 없습니다.

오늘날 하드웨어로 처리되는 sqrt와 여기서 소수를 계산해야 하는 필요성을 감안할 때 이 솔루션은 훨씬 느리다고 생각합니다.그러나 mrzl씨가 답변에서 말한 것처럼 sqrt의 솔루션보다 더 나은 결과를 얻을 수 있을 것입니다.

정수 문제는 정수 해답을 얻을 가치가 있다.따라서

하여 (부정수가 아닌) .t**2 <= n해 보세요.r**2 = n이 걸리다. O가.O(log n)로 하다

집합에 제한이 없기 때문에 양의 정수를 이진수로 검색하는 방법을 모를 경우 간단합니다. f(위)부터합니다.f(t) = t**2 - n2인용바이너리 검색을 할 수.그런 다음 표준 이진 검색을 수행할 수 있습니다.

지적된 바에 의하면d완전한 정사각형의 자리수는 특정 값만 취할 수 있습니다. ★★★★d '')b의 숫자입니다.n.n.bd(예: C 표기법)n % pow(b, d).

은 어떤 할 수 .m 즉,n % m완전 제곱에서 숫자의 비율을 제외하는 데 사용할 수 있습니다.현재 사용하고 있는 계수는 64로, 12(예: 19%)의 잔량을 가능한 제곱으로 사용할 수 있습니다.약간의 코딩으로 계수 110880을 찾았는데, 이 계수 110880은 2016년, 즉 1.8%의 잔여량만 가능한 제곱으로 허용한다.따라서 계수 연산(즉, 나눗셈) 및 표 조회 대 제곱근의 비용에 따라 이 계수를 사용하는 것이 더 빠를 수 있습니다.

참고로 Java가 룩업 테이블에 비트 배열을 저장하는 방법을 가지고 있다면 사용하지 마십시오. 현재 110880 32비트 워드는 RAM이 많지 않습니다. 머신 워드를 가져오는 것이 단일 비트를 가져오는 것보다 빠를 것입니다.

다음과 같이 maartinus 솔루션을 단순화하면 실행 시간을 몇 % 단축할 수 있을 것 같지만 신뢰할 수 있는 벤치마크를 만들기에는 부족합니다.

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;

퍼포먼스에 영향을 줍니다.

퍼포먼스를 위해 타협이 필요한 경우가 많습니다.다른 사람들은 다양한 방법을 표현하고 있지만, 당신은 Carmack의 해킹이 N의 특정 값까지 더 빨랐다고 지적했습니다.그런 다음 "n"을 확인하고 N보다 작으면 Carmack의 해킹을 사용합니다.그렇지 않으면 여기 답변에 기재되어 있는 다른 방법을 사용합니다.

이 스레드에서 다른 사용자가 제안한 기술을 조합하여 Java를 구현하는 것이 가장 빠릅니다.

• Mod-256 테스트
• 부정확한 mod-3465 테스트(일부 잘못된 긍정을 희생하여 정수 나눗셈을 피함)
• 부동소수점 제곱근, 반올림 및 입력값과 비교

이러한 변경도 시험해 보았습니다만, 퍼포먼스에 도움이 되지 않았습니다.

• 추가 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;
        }
    }

}

N의 2승 부분은 처음부터 없애야 합니다.

두 번째 편집 아래 m에 대한 마법 표현은 다음과 같아야 합니다.

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

기재된 바와 같이

2차 편집 종료

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

첫 번째 편집:

약간의 개선:

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

첫 번째 편집 종료

이제 평소와 같이 계속합니다.이렇게 하면 부동소수점 부분에 도달했을 때 2승 부분이 홀수(약 절반)인 숫자는 이미 모두 제거되고 나머지 8분의 1만 고려됩니다.즉, 부동 소수점 부분은 숫자의 6%에 대해 작동합니다.

, 그 은 번호를 . >> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >>>2^6480바이트 버퍼를 사용하고 있는 경우, 상기의 최적화의 대부분은 간단하게 동작하지 않습니다.

자바 BigInteger와 뉴턴의 방법을 약간 수정한 것을 사용했는데, 이는 정수와 더 잘 어울린다.는 정사각형이 정확하다는 이었다.n^2 converged로 됩니다.(n-1)nn^2-1 = (n-1)(n+1)마지막 오차는 마지막 제수보다 한 단계 아래였고 알고리즘은 종료되었습니다.오류를 계산하기 전에 원래 인수에 1을 더하면 쉽게 수정할 수 있습니다. (입방근 등에 2를 더합니다.)

이 알고리즘의 좋은 특성 중 하나는 숫자가 완벽한 제곱인지 여부를 즉시 알 수 있다는 것입니다. 즉, 뉴턴 방법의 최종 오차(보정이 아님)는 0이 됩니다.으로 계산도 할 수 .floor(sqrt(x))★★★★★★★★★★★★★★★★★★★★★★★★★★★이것은 몇 가지 오일러 문제에 도움이 된다.

이것은 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

여기 비슷한 것이 있습니다(코드 스타일/냄새나 투박한 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;
};

sqrt 콜은 앞서 말한 것처럼 완전히 정확하지는 않지만, 속도 면에서 다른 답변을 날려버리지 않는 것은 흥미롭고 유익합니다.결국, sqrt에 대한 어셈블리 언어 명령의 시퀀스는 매우 작습니다.인텔은 하드웨어 명령을 가지고 있지만, Java에서는 사용되지 않습니다.IEEE에 준거하고 있지 않기 때문입니다.

그런데 왜 느려?Java는 실제로 JNI를 통해 C 루틴을 호출하고 있으며, 실제로 호출하는 것이 Java 서브루틴보다 느리므로, Java 서브루틴을 호출하는 것보다 느립니다.이것은 매우 귀찮은 일이며, Java는 더 나은 해결책을 생각해 냈어야 했습니다.즉, 필요에 따라서 부동소수점 라이브러리 콜을 빌드하는 것입니다.아, 그렇군요.

C++에서는 모든 복잡한 대안이 속도가 느려질 것으로 예상되지만, 모두 확인하지 못했습니다.내가 한 것과 자바 사람들이 유용하다고 생각하는 것은 A. Rex가 제안한 특수한 케이스 테스트의 연장선인 단순한 해킹이다.단일 긴 값을 비트 배열로 사용하라.한계는 체크되지 않는다.이렇게 하면 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;
}

루틴은 core2 duo 머신에서 1/3 정도의 시간이 걸립니다.같은 노선을 따라 더 많이 조정하면 평균적으로 시간이 더 단축될 수 있지만, 매번 확인할 때마다 더 많은 테스트와 더 많은 테스트를 교환하기 때문에 더 이상 많은 테스트를 수행할 수 없습니다.

물론 음성에 대해 별도의 테스트를 하는 것이 아니라 동일한 방법으로 상위 6비트를 확인할 수 있습니다.

가능한 정사각형을 삭제하는 것 뿐이지만, 가능성이 있는 경우는, 원래의 Inlined Square 를 Infect Square is Perfect Square 。

pp1과 pp2의 정적 값을 초기화하기 위해 init2 루틴이 한 번 호출됩니다.C++에서의 실장에서는, 서명되지 않은 롱을 사용하고 있기 때문에, 서명하고 있기 때문에, >>> 연산자를 사용할 필요가 있는 것에 주의해 주세요.

어레이의 경계를 체크할 필요는 없지만 Java의 옵티마이저는 이 문제를 매우 신속하게 해결해야 하기 때문에 저는 그들을 탓하지 않습니다.

일부 입력에 대해 거의 올바른 방법을 사용한다는 생각이 마음에 듭니다.다음은 "오프셋"이 더 높은 버전입니다.코드는 정상적으로 동작하고 있어, 간단한 테스트 케이스에 합격합니다.

다음 주소를 교체:

if(n < 410881L){...}

이 코드로 코드화:

if (n < 11043908100L) {
    //John Carmack hack, converted to Java.
    // See: http://www.codemaestro.com/reviews/9
    int i;
    float x2, y;

    x2 = n * 0.5F;
    y = n;
    i = Float.floatToRawIntBits(y);
    //using the magic number from 
    //http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf
    //since it more accurate
    i = 0x5f375a86 - (i >> 1);
    y = Float.intBitsToFloat(i);
    y = y * (1.5F - (x2 * y * y));
    y = y * (1.5F - (x2 * y * y)); //Newton iteration, more accurate

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

일반적인 비트 길이(여기에서는 특정 타입을 사용하고 있습니다만)를 고려하여 다음과 같이 심플한 algo를 설계하려고 했습니다.처음에는 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;  
}  

정사각형의 마지막 n비트가 관찰되었을 때 가능한 모든 결과를 확인했습니다.더 많은 비트를 순차적으로 검사함으로써 입력의 최대 5/6을 제거할 수 있습니다.저는 페르마의 인수분해 알고리즘을 구현하기 위해 이것을 디자인했습니다.그것은 매우 빠릅니다.

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

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

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

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

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

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

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

a는 (3 < 2k) - 1 형식입니다.

b는 (2 < 2k) 형식입니다.

c는 (2 < 2k + 2) - 1 형식입니다.

는 (< * (2 < 2k - 1) * 10d이다.

먼저 검정력이 2인 제곱 잔차가 있는지 여부를 테스트한 다음 최종 계수에 따라 테스트한 다음 Math.sqrt를 사용하여 최종 테스트를 수행합니다.나는 맨 위에서 아이디어를 떠올려 그것을 확장하려고 했다.어떤 의견이나 제안이라도 감사합니다.

업데이트: 모듈러스(modSq)와 모듈러스 베이스 44352에 의한 테스트를 사용하여 OP 업데이트 시간의 96%에서 최대 1,000,000까지 테스트가 실행됩니다.

정수 산술에 의한 뉴턴의 방법

정수 이외의 연산을 피하고 싶은 경우는, 다음의 방법을 사용할 수 있습니다.기본적으로 정수 산술에 대해 수정된 뉴턴의 방법을 사용합니다.

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

은 this음음음음음음음음음음 that that that that that that that that that that that that that that that that that that that that that that that that that that that that를 사용하는 할 수 .Math.sqrt다만, 그 퍼포먼스는, 다른 투고에 기재되어 있는 필터링 메카니즘에 의해서 향상할 수 있습니다.

여기 분할과 정복의 해결책이 있습니다.

( of연根)인 number )는solution의를 쉽게 할 수 .solution「자릿수」의해 주세요.number:

• number 숫자: 1자리 숫자:solution=~4µ = 1 ~4µ
• number숫자가 .solution= µ = 3 ~10 µ
• number숫자가 .solution= °C = 10 ~40 °C
• number숫자가 .solution= °C = 30 ~100 °C
• number에는 5자리 숫자가 .solution= °C = 100 ~400 °C

반복을 눈치채셨나요?

에서는, 이 범위를 하고, 「이러한 검색」이 할 수 .solution 유 for :

number == solution * solution

여기 코드가 있습니다.

여기 제 클래스 SquareRootChecker가 있습니다.

public class SquareRootChecker {

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

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

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

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

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

}

그리고 여기 그것의 사용 방법에 대한 예가 있습니다.

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

long notSquare = square + 1;
squareRootChecker = new SquareRootChecker(notSquare);
System.out.println(notSquare + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677490: false"

숫자의 제곱근(숫자가 완벽한 정사각형인 경우)

복잡도는 log(n)입니다.

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

public static int calculateSquareRoot(int number) {

    int sum=1;
    int count =1;
    int squareRoot=1;
    while(sum<number) {
        count+=2;
        sum+=count;
        squareRoot++;
    }
    return squareRoot;
}

속도가 문제가 된다면 가장 일반적으로 사용되는 입력과 그 값을 룩업 테이블로 분할한 후 예외적인 경우를 위해 최적화된 마법 알고리즘을 생각해 내는 것은 어떨까요?

"저는 긴 값이 완벽한 제곱(즉, 제곱근은 다른 정수)인지 여부를 판단하는 가장 빠른 방법을 찾고 있습니다."

답변은 인상적이지만 간단한 체크는 하지 못했습니다.

long 오른쪽에 있는 첫 번째 숫자가 집합의 멤버인지 확인합니다(0,1,4,5,6,9). 그렇지 않으면 '완벽한 정사각형'일 수 없습니다.

예:

4567 - 완전한 정사각형이 될 수 없습니다.

'마지막 X자리가 N이면 완벽한 정사각형일 수 없다'를 그것보다 훨씬 더 효율적으로 포장할 수 있을 것이다!Java 32비트 ints를 사용하여 숫자의 마지막 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.display의 퍼포먼스가 나빠서 삭제되었습니다.리비전 이력을 참조해 주세요.)

뉴턴법에 의한 제곱근 계산은 시작값이 합리적이라면 끔찍할 정도로 빠르다.그러나 합리적인 시작 값은 없으며, 실제로는 이등분 및 로그(2^64) 동작으로 끝납니다.
정말 빨리 하기 위해서는 합리적인 시작값을 얻을 수 있는 빠른 방법이 필요합니다. 즉, 기계어로 내려갈 필요가 있습니다.프로세서가 Pentium에서 POPCNT와 같은 명령어를 제공한다면 선행하는 0을 카운트하는 명령을 사용하여 유효 비트의 절반으로 시작하는 값을 가질 수 있습니다.주의를 기울이면 항상 충분할 고정된 수의 뉴턴 스텝을 찾을 수 있습니다(따라서 루프할 필요성과 실행 속도가 매우 빠릅니다).

두 번째 솔루션은 부동소수점 설비를 통과하는 것으로, 고속 sqrt 계산(i87 코프로세서 등)이 가능합니다.exp() 및 log()를 통한 Excursion도 Newton이 바이너리 검색으로 변환한 것보다 빠를 수 있습니다.여기에는 까다로운 측면이 있습니다.나중에 무엇을 개선할 필요가 있는지 프로세서에 의존한 분석이 필요합니다.

세 번째 솔루션은 약간 다른 문제를 해결하지만, 그 상황이 질문에 설명되어 있기 때문에 언급할 가치가 있습니다.약간 다른 숫자에 대해 다수의 제곱근을 계산하려면 시작 값을 다시 초기화하지 않고 이전 계산이 중단된 위치에 그대로 두면 Newton 반복을 사용할 수 있습니다.오일러 문제 중 적어도 한 문제에서 이것을 성공적으로 사용해 본 적이 있다.

이 문제에 가장 적합한 알고리즘은 고속 정수 제곱근 알고리즘입니다.https://stackoverflow.com/a/51585204/5191852

여기서 @Kde는 뉴턴 방법을 3회 반복하면 32비트 정수에 대해 ±1의 정확도에 충분하다고 주장한다.64비트 정수에는 6 또는 7의 반복이 더 필요할 수 있습니다.

언급URL : https://stackoverflow.com/questions/295579/fastest-way-to-determine-if-an-integers-square-root-is-an-integer