정수의 제곱근이 정수인지 확인하는 가장 빠른 방법
https://stackoverflow.com/questions/295579
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는 어떤 것인지 판단하는 가장 빠른 방법을 찾고 있습니다. long 값은 완전제곱수입니다(예:제곱근은 또 다른 정수입니다):
- 내장된 기능을 사용하여 쉽게 해냈습니다.
Math.sqrt()기능이지만 정수 전용 도메인으로 자신을 제한하여 더 빨리 수행 할 수있는 방법이 있는지 궁금합니다. - 조회 테이블을 유지하는 것은 비현실적입니다 (약 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;
}
메모:저는 이 기능을 많이 사용하고 있어요 프로젝트 오일러 문제.따라서 누구도 이 코드를 유지 관리할 필요가 없습니다.그리고 이러한 종류의 미세 최적화는 실제로 차이를 만들 수 있습니다. 왜냐하면 문제의 일부는 모든 알고리즘을 1분 이내에 수행하는 것이고 일부 문제에서는 이 함수를 수백만 번 호출해야 하기 때문입니다.
나는 문제에 대해 다양한 해결책을 시도했습니다.
- 철저한 테스트를 거친 후 다음을 추가하는 것으로 나타났습니다.
0.5적어도 내 컴퓨터에서는 Math.sqrt()의 결과가 필요하지 않습니다. - 그만큼 빠른 역제곱근 더 빠르지만 n >= 410881에 대해 잘못된 결과를 제공했습니다.그러나 제안한대로 바비샤프토, n < 410881에 대해 FISR 해킹을 사용할 수 있습니다.
- 뉴턴의 방법은 그보다 약간 느렸습니다.
Math.sqrt().아마도 이런 이유 때문일 것이다Math.sqrt()Newton의 방법과 유사한 것을 사용하지만 하드웨어에서 구현되므로 Java보다 훨씬 빠릅니다.또한 뉴턴의 방법은 여전히 복식을 사용해야 했습니다. - 몇 가지 트릭을 사용하여 정수 수학만 포함하는 수정된 뉴턴 방법은 오버플로를 방지하기 위해 몇 가지 해킹이 필요했으며(나는 이 함수가 모든 양의 64비트 부호 있는 정수에서 작동하기를 원합니다) 여전히 뉴턴 방법보다 느렸습니다.
Math.sqrt(). - 바이너리 절단은 훨씬 더 느렸습니다.이는 바이너리 절단이 64비트 숫자의 제곱근을 찾기 위해 평균 16번의 패스를 필요로 하기 때문에 의미가 있습니다.
- John의 테스트에 따르면
or문을 사용하는 것보다 C++에서 더 빠릅니다.switch, 그러나 Java와 C#에서는 사이에 차이가 없는 것 같습니다.or그리고switch. - 또한 조회 테이블(64개 부울 값의 개인 정적 배열)을 만들어 보았습니다.그런 다음 스위치 또는
or성명서, 나는 단지 말할 것입니다if(lookup[(int)(n&0x3F)]) { test } else return false;.놀랍게도 이 속도는 (약간) 느렸습니다.이 때문입니다 배열 경계는 Java에서 확인됩니다..
해결책
나는 적어도 내 CPU(x86)와 프로그래밍 언어(C/C++)를 사용하여 6bits+Carmack+sqrt 코드보다 ~35% 더 빠르게 작동하는 방법을 알아냈습니다.특히 Java 요소가 어떻게 작용할지 모르기 때문에 결과가 다를 수 있습니다.
내 접근 방식은 세 가지입니다.
- 먼저, 뻔한 답변을 필터링하세요.여기에는 음수와 마지막 4비트가 포함됩니다.(마지막 6개를 보는 것이 도움이 되지 않는다는 것을 알았습니다.) 또한 0에 대해서는 '예'라고 대답합니다.(아래 코드를 읽을 때 제가 입력한 내용은 다음과 같습니다.
int64 x.)if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) ) return false; if( x == 0 ) return true; - 다음으로, 모듈로 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 - 마지막으로, 다음과 유사한 방법을 사용하여 제곱근을 계산해 보십시오. 헨젤의 정리.(직접 적용할 수는 없을 것 같지만 약간 수정하면 작동합니다.) 그 전에 이진 검색을 통해 2의 거듭제곱을 모두 나눕니다.
이 시점에서 숫자가 정사각형이 되려면 1 mod 8이어야 합니다.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;
Hensel의 보조정리의 기본 구조는 다음과 같습니다.(메모:테스트되지 않은 코드;작동하지 않으면 t=2 또는 8을 시도해 보세요.)if((x & 7) != 1) return false;
아이디어는 각 반복마다 x의 "현재" 제곱근인 r에 1비트를 추가한다는 것입니다.각 제곱근은 점점 더 커지는 2의 거듭제곱, 즉 t/2의 모듈로로 정확합니다.결국 r과 t/2-r은 x 모듈로 t/2의 제곱근이 됩니다.(r이 x의 제곱근이면 -r도 마찬가지입니다.이는 모듈로 숫자에도 해당됩니다. 그러나 일부 숫자의 모듈로에서는 2제곱근보다 더 많은 값을 가질 수 있다는 점에 유의하십시오.특히 여기에는 2의 거듭제곱이 포함됩니다.) 실제 제곱근은 2^32보다 작기 때문에 이 시점에서 실제로 r 또는 t/2-r이 실제 제곱근인지 확인할 수 있습니다.실제 코드에서는 다음과 같은 수정된 루프를 사용합니다.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.
여기서 속도 향상은 세 가지 방법으로 얻습니다.미리 계산된 시작 값(루프의 ~10회 반복과 동일), 루프의 조기 종료 및 일부 t 값 건너뛰기.마지막 부분을 보면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) );z = r - x * x, 비트 트릭을 사용하여 t를 z를 나누는 2의 가장 큰 거듭제곱으로 설정합니다.이를 통해 어쨌든 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;
}
첫 번째 테스트에서는 정사각형이 아닌 대부분의 문자를 빠르게 포착합니다.Long으로 압축된 64개 항목 테이블을 사용하므로 배열 액세스 비용(간접 및 경계 확인)이 없습니다.균등 무작위의 경우 long, 여기서 끝날 확률은 81.25%입니다.
두 번째 테스트에서는 인수분해에서 홀수의 2를 갖는 모든 숫자를 포착합니다.방법 Long.numberOfTrailingZeros 단일 i86 명령어로 JIT 처리되므로 매우 빠릅니다.
후행 0을 삭제한 후 세 번째 테스트에서는 이진수로 끝나는 011, 101 또는 111(완전한 정사각형이 아닌) 숫자를 처리합니다.또한 음수에도 관심을 갖고 0도 처리합니다.
최종 테스트는 다음으로 돌아갑니다. double 산수.처럼 double Mantissa는 53 비트에 불과합니다 long 에게 double 큰 값에 대한 반올림이 포함됩니다.그럼에도 불구하고 테스트는 정확합니다( 증거 틀렸습니다).
mod255 아이디어를 통합하려는 시도는 성공하지 못했습니다.
벤치마킹을 좀 해봐야 할 것 같습니다.최상의 알고리즘은 입력 분포에 따라 달라집니다.
알고리즘이 거의 최적일 수 있지만 제곱근 루틴을 호출하기 전에 몇 가지 가능성을 배제하기 위해 빠른 검사를 수행할 수 있습니다.예를 들어, 약간의 "and"를 통해 16 진수의 마지막 숫자를 살펴보십시오. 완벽한 사각형은 16베이스에서 0, 1, 4 또는 9로만 끝날 수 있으므로 입력의 75% (균일하게 분포되어 있다고 가정)에 대해서는 매우 빠른 비트 트위 링을 대가로 제곱 루트에 대한 호출을 피할 수 있습니다.
Kip은 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# 코드에는 거의 영향이 없습니다.
나는 수치 분석 과정에서 보낸 끔찍한 시간에 대해 생각하고 있었습니다.
그리고 Quake 소스 코드의 'net' 주위를 돌고 있는 다음 함수가 있다는 것을 기억합니다.
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
뉴턴의 방법은 Wikipedia에 설명되어 있습니다. http://en.wikipedia.org/wiki/Newton%27s_method
작동 방식에 대한 자세한 설명을 보려면 링크를 따라갈 수 있지만 크게 신경 쓰지 않는다면 블로그를 읽고 수치 분석 과정을 수강하면서 기억나는 내용은 대략 다음과 같습니다.
- 그만큼
* (long*) &y기본적으로 빠른 변환 함수이므로 원시 바이트에 정수 연산을 적용할 수 있습니다. - 그만큼
0x5f3759df - (i >> 1);선은 근사 함수에 대해 미리 계산된 시드 값입니다. - 그만큼
* (float*) &i값을 다시 부동 소수점으로 변환합니다. - 그만큼
y = y * ( threehalfs - ( x2 * y * y ) )line은 기본적으로 함수에 대한 값을 다시 반복합니다.
근사 함수는 결과에 대해 함수를 더 많이 반복할수록 더 정확한 값을 제공합니다.Quake의 경우 한 번의 반복이면 "충분"하지만 그렇지 않다면...그러면 필요한 만큼 반복을 추가할 수 있습니다.
이것은 순진한 제곱근에서 수행되는 나눗셈 연산의 수를 간단한 2로 나누는 작업(실제로는 * 0.5F 곱셈 연산) 대신 몇 가지 고정된 수의 곱셈 연산으로 대체합니다.
더 빠르거나 정확할지 확실하지 않지만 다음을 사용할 수 있습니다. 존 카맥의 마법의 제곱근, 제곱근을 더 빨리 푸는 알고리즘입니다.가능한 모든 32비트 정수에 대해 이를 쉽게 테스트하고 근사치일 뿐이므로 실제로 올바른 결과를 얻었는지 확인할 수 있습니다.그러나 지금 생각해보면 복식을 사용하는 것도 근사치이므로 그것이 어떻게 작용할지는 잘 모르겠습니다.
"올바른" 제곱근을 찾기 위해 이진 절단을 수행하면 얻은 값이 다음을 알 수 있을 만큼 가까운지 매우 쉽게 감지할 수 있습니다.
(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:거의 비슷하지만 완벽하지는 않습니다.거짓을 반환하다n^2 - 2n + 1 < target < n^2:같게target < n^2 - 2n + 1:아래쪽에 바이너리 찹ntarget > n^2 + 2n + 1:더 높은 곳에 있는 바이너리 찹n
(죄송합니다. n 현재 추측대로 target 매개변수의 경우.혼란을 드려 죄송합니다!)
이것이 더 빠를지 아닐지는 모르겠지만 시도해 볼 가치가 있습니다.
편집하다:바이너리 찹은 정수의 전체 범위를 취할 필요도 없습니다. (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;
그러나 대부분의 경우 하나 또는 두 개의 매우 빠른 명령을 추가하는 이 간단한 라인은 switch-case 문을 하나의 if 문으로 만듭니다.그러나 테스트된 숫자 중 다수에 상당한 2의 거듭제곱 요소가 있는 경우 런타임이 추가될 수 있습니다.
아래 알고리즘은 다음과 같습니다.
- 인터넷 - Kip이 게시한 답변
- 듀론 - 원패스 답변을 기반으로 수정된 답변
- 듀론투 - 2단계 답변(@JohnnyHeggheim 작성)을 사용하여 수정된 답변과 기타 약간의 수정 사항이 있습니다.
숫자가 다음을 사용하여 생성된 경우 샘플 런타임은 다음과 같습니다. Math.abs(java.util.Random.nextLong())
0% Scenario{vm=java, trial=0, benchmark=Internet} 39673.40 ns; ?=378.78 ns @ 3 trials
33% Scenario{vm=java, trial=0, benchmark=Durron} 37785.75 ns; ?=478.86 ns @ 10 trials
67% Scenario{vm=java, trial=0, benchmark=DurronTwo} 35978.10 ns; ?=734.10 ns @ 10 trials
benchmark us linear runtime
Internet 39.7 ==============================
Durron 37.8 ============================
DurronTwo 36.0 ===========================
vm: java
trial: 0
다음은 처음 백만 번만 실행되는 경우의 샘플 런타임입니다.
0% Scenario{vm=java, trial=0, benchmark=Internet} 2933380.84 ns; ?=56939.84 ns @ 10 trials
33% Scenario{vm=java, trial=0, benchmark=Durron} 2243266.81 ns; ?=50537.62 ns @ 10 trials
67% Scenario{vm=java, trial=0, benchmark=DurronTwo} 3159227.68 ns; ?=10766.22 ns @ 3 trials
benchmark ms linear runtime
Internet 2.93 ===========================
Durron 2.24 =====================
DurronTwo 3.16 ==============================
vm: java
trial: 0
보시다시피, DurronTwo 마술을 매우 자주 사용하기 때문에 큰 입력에 더 적합하지만 첫 번째 알고리즘과 비교하면 문제가 발생합니다. Math.sqrt 숫자가 훨씬 작기 때문이죠.그 사이에, 더 간단한 Durron 처음 백만 개의 숫자에서 4로 여러 번 나눌 필요가 없기 때문에 큰 승리자입니다.
여기 Durron:
public final static boolean isPerfectSquareDurron(long n) {
if(n < 0) return false;
if(n == 0) return true;
long x = n;
// This is faster because a number is divisible by 16 only 6% of the time
// and more than that a vanishingly small percentage.
while((x & 0x3) == 0) x >>= 2;
// This is effectively the same as the switch-case statement used in the original
// answer.
if((x & 0x7) == 1) {
long sqrt;
if(x < 410881L)
{
int i;
float x2, y;
x2 = x * 0.5F;
y = x;
i = Float.floatToRawIntBits(y);
i = 0x5f3759df - ( i >> 1 );
y = Float.intBitsToFloat(i);
y = y * ( 1.5F - ( x2 * y * y ) );
sqrt = (long)(1.0F/y);
} else {
sqrt = (long) Math.sqrt(x);
}
return sqrt*sqrt == x;
}
return false;
}
그리고 DurronTwo
public final static boolean isPerfectSquareDurronTwo(long n) {
if(n < 0) return false;
// Needed to prevent infinite loop
if(n == 0) return true;
long x = n;
while((x & 0x3) == 0) x >>= 2;
if((x & 0x7) == 1) {
long sqrt;
if (x < 41529141369L) {
int i;
float x2, y;
x2 = x * 0.5F;
y = x;
i = Float.floatToRawIntBits(y);
//using the magic number from
//http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf
//since it more accurate
i = 0x5f375a86 - (i >> 1);
y = Float.intBitsToFloat(i);
y = y * (1.5F - (x2 * y * y));
y = y * (1.5F - (x2 * y * y)); //Newton iteration, more accurate
sqrt = (long) ((1.0F/y) + 0.2);
} else {
//Carmack hack gives incorrect answer for n >= 41529141369.
sqrt = (long) Math.sqrt(x);
}
return sqrt*sqrt == x;
}
return false;
}
내 벤치마크 하네스는 다음과 같습니다.(Google 캘리퍼 0.1-rc5 필요)
public class SquareRootBenchmark {
public static class Benchmark1 extends SimpleBenchmark {
private static final int ARRAY_SIZE = 10000;
long[] trials = new long[ARRAY_SIZE];
@Override
protected void setUp() throws Exception {
Random r = new Random();
for (int i = 0; i < ARRAY_SIZE; i++) {
trials[i] = Math.abs(r.nextLong());
}
}
public int timeInternet(int reps) {
int trues = 0;
for(int i = 0; i < reps; i++) {
for(int j = 0; j < ARRAY_SIZE; j++) {
if(SquareRootAlgs.isPerfectSquareInternet(trials[j])) trues++;
}
}
return trues;
}
public int timeDurron(int reps) {
int trues = 0;
for(int i = 0; i < reps; i++) {
for(int j = 0; j < ARRAY_SIZE; j++) {
if(SquareRootAlgs.isPerfectSquareDurron(trials[j])) trues++;
}
}
return trues;
}
public int timeDurronTwo(int reps) {
int trues = 0;
for(int i = 0; i < reps; i++) {
for(int j = 0; j < ARRAY_SIZE; j++) {
if(SquareRootAlgs.isPerfectSquareDurronTwo(trials[j])) trues++;
}
}
return trues;
}
}
public static void main(String... args) {
Runner.main(Benchmark1.class, args);
}
}
업데이트: 저는 어떤 시나리오에서는 더 빠르고 다른 시나리오에서는 더 느린 새로운 알고리즘을 만들었습니다. 다양한 입력을 기반으로 다양한 벤치마크를 얻었습니다.모듈로 계산하면 0xFFFFFF = 3 x 3 x 5 x 7 x 13 x 17 x 241, 제곱이 될 수 없는 숫자의 97.82%를 제거할 수 있습니다.이는 5가지 비트 연산을 사용하여 한 줄로 수행할 수 있습니다.
if (!goodLookupSquares[(int) ((n & 0xFFFFFFl) + ((n >> 24) & 0xFFFFFFl) + (n >> 48))]) return false;
결과 지수는 1) 잔기, 2) 잔기 중 하나입니다. + 0xFFFFFF, 또는 3) 잔여물 + 0x1FFFFFE.물론, 우리는 잔여물 모듈로에 대한 조회 테이블이 필요합니다. 0xFFFFFF, 이는 약 3MB 파일입니다(이 경우 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 (버전 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
사용하는 것이 훨씬 빨라야합니다 뉴턴의 방법 계산하기 위해 정수 제곱근, 그런 다음 현재 솔루션에서와 마찬가지로 이 숫자를 제곱하고 확인합니다.Newton의 방법은 다른 답변에서 언급된 Carmack 솔루션의 기초입니다.근의 정수 부분에만 관심이 있으므로 더 빠른 답변을 얻을 수 있어 근사 알고리즘을 더 빨리 중지할 수 있습니다.
시도해 볼 수 있는 또 다른 최적화:만약 디지털 루트 숫자 중 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이 말했듯이 2^54 이상에서는 작동하지 않는 sqrt를 사용한 솔루션보다 더 나은 결과를 제공해야 합니다.
정수 문제에는 정수 솔루션이 필요합니다.따라서
(음수가 아닌) 정수에 대해 이진 검색을 수행하여 다음과 같은 가장 큰 정수 t를 찾습니다. t**2 <= n.그런 다음 여부를 테스트 r**2 = n 정확히.이는 O(log n)의 시간이 걸립니다.
세트가 무한하기 때문에 양의 정수를 이진 검색하는 방법을 모른다면 쉽습니다.증가 함수 f(위)를 계산하는 것부터 시작합니다. f(t) = t**2 - n) 2의 거듭제곱입니다.양수로 바뀌면 상한선을 찾은 것입니다.그런 다음 표준 이진 검색을 수행할 수 있습니다.
마지막이라는 사실이 지적됐다. d 완전제곱수의 숫자는 특정 값만 가질 수 있습니다.마지막 d 숫자(기본 b) 숫자의 n 때 나머지와 동일 n 로 나누어진다 bd, 즉.C 표기법으로 n % pow(b, d).
이는 모든 모듈러스로 일반화될 수 있습니다. m, 즉. n % m 는 숫자의 일부 비율이 완전제곱수가 되는 것을 배제하는 데 사용될 수 있습니다.현재 사용하고 있는 모듈러스는 64이며, 이는 12를 허용합니다.나머지 19%는 가능한 정사각형입니다.약간의 코딩을 통해 2016만 허용하는 모듈러스 110880을 찾았습니다.나머지 1.8%는 가능한 제곱입니다.따라서 모듈러스 연산 비용에 따라(예:나눗셈) 및 컴퓨터의 제곱근에 대한 테이블 조회를 수행하는 경우 이 모듈러스를 사용하는 것이 더 빠를 수 있습니다.
그런데 Java에 조회 테이블에 대한 압축된 비트 배열을 저장하는 방법이 있는 경우 이를 사용하지 마십시오.110880 요즘 32비트 단어는 RAM이 많지 않으며 기계 단어를 가져오는 것이 단일 비트를 가져오는 것보다 빠릅니다.
성능을 위해서는 몇 가지 타협을 해야 하는 경우가 많습니다.다른 사람들은 다양한 방법을 표현했지만 Carmack의 해킹이 특정 N 값까지 더 빠르다는 점을 지적하셨습니다.그런 다음 "n"을 확인하고 해당 숫자 N보다 작으면 Carmack의 해킹을 사용하고, 그렇지 않으면 여기 답변에 설명된 다른 방법을 사용하십시오.
이것은 이 스레드에서 다른 사람들이 제안한 기술의 조합을 사용하여 제가 생각해 낼 수 있는 가장 빠른 Java 구현입니다.
- Mod-256 테스트
- 부정확한 mod-3465 테스트(일부 거짓 긍정을 희생하여 정수 나누기를 방지함)
- 부동 소수점 제곱근, 반올림 및 입력 값과 비교
또한 이러한 수정 사항을 실험했지만 성능에 도움이 되지 않았습니다.
- 추가 mod-255 테스트
- 입력 값을 4의 거듭제곱으로 나누기
- 빠른 역 제곱근(N의 높은 값에 대해 작동하려면 3번의 반복이 필요하므로 하드웨어 제곱근 함수보다 느려집니다.)
public class SquareTester {
public static boolean isPerfectSquare(long n) {
if (n < 0) {
return false;
} else {
switch ((byte) n) {
case -128: case -127: case -124: case -119: case -112:
case -111: case -103: case -95: case -92: case -87:
case -79: case -71: case -64: case -63: case -60:
case -55: case -47: case -39: case -31: case -28:
case -23: case -15: case -7: case 0: case 1:
case 4: case 9: case 16: case 17: case 25:
case 33: case 36: case 41: case 49: case 57:
case 64: case 65: case 68: case 73: case 81:
case 89: case 97: case 100: case 105: case 113:
case 121:
long i = (n * INV3465) >>> 52;
if (! good3465[(int) i]) {
return false;
} else {
long r = round(Math.sqrt(n));
return r*r == n;
}
default:
return false;
}
}
}
private static int round(double x) {
return (int) Double.doubleToRawLongBits(x + (double) (1L << 52));
}
/** 3465<sup>-1</sup> modulo 2<sup>64</sup> */
private static final long INV3465 = 0x8ffed161732e78b9L;
private static final boolean[] good3465 =
new boolean[0x1000];
static {
for (int r = 0; r < 3465; ++ r) {
int i = (int) ((r * r * INV3465) >>> 52);
good3465[i] = good3465[i+1] = true;
}
}
}
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;
성능에 영향을 미칠 것입니다.
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;
1차 편집 끝
이제 평소대로 계속하세요.이렇게 하면 부동 소수점 부분에 도달할 때쯤에는 2제곱 부분이 홀수(약 절반)인 모든 숫자를 이미 제거한 다음 남은 것의 1/8만 고려하게 됩니다.즉.숫자의 6%에 대해 부동 소수점 부분을 실행합니다.
이것은 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에 대한 어셈블리 언어 명령어 시퀀스는 매우 작습니다.Intel에는 IEEE를 준수하지 않기 때문에 Java에서 사용되지 않는 하드웨어 명령이 있습니다.
그럼 왜 느린 걸까요?Java는 실제로 JNI를 통해 C 루틴을 호출하고 실제로 인라인으로 수행하는 것보다 느린 Java 서브루틴을 호출하는 것보다 더 느리기 때문입니다.이는 매우 짜증나는 일이며 Java는 더 나은 솔루션, 즉 필요한 경우 부동 소수점 라이브러리 호출을 구축해야 합니다.아 글쎄.
C++에서는 모든 복잡한 대안이 속도를 잃을 것이라고 생각하지만 모두 확인하지는 않았습니다.내가 한 일, 그리고 Java 사람들이 유용하다고 생각할 것은 A가 제안한 특수 사례 테스트의 확장인 간단한 해킹입니다.렉스.단일 긴 값을 경계가 확인되지 않은 비트 배열로 사용합니다.이렇게 하면 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 duo 머신에서 실행되는 시간의 약 1/3만에 실행됩니다.동일한 라인을 따라 추가로 조정하면 평균적으로 시간이 더 단축될 수 있다고 생각하지만 확인할 때마다 더 많은 제거를 위해 더 많은 테스트를 포기하게 되므로 그 길에서 너무 멀리 갈 수는 없습니다.
물론 별도의 음성 테스트를 하는 것보다는 같은 방식으로 상위 6비트를 확인할 수 있습니다.
제가 하고 있는 일은 가능한 사각형을 제거하는 것뿐입니다. 그러나 잠재적인 경우가 있을 경우 원래의 인라인된 isPerfectSquare를 호출해야 합니다.
init2 루틴은 pp1 및 pp2의 정적 값을 초기화하기 위해 한 번 호출됩니다.C++ 구현에서는 unsigned long long을 사용하므로 서명되었으므로 >>> 연산자를 사용해야 합니다.
배열의 경계를 검사할 본질적인 필요는 없지만 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);
}
프로젝트 오일러(Project Euler)가 태그에 언급되어 있으며 그 안의 많은 문제에는 숫자 확인이 필요합니다 >> 2^64.위에서 언급한 대부분의 최적화는 80바이트 버퍼로 작업할 때 쉽게 작동하지 않습니다.
나는 Java BigInteger와 Newton의 방법을 약간 수정한 버전을 사용했는데, 이는 정수에서 더 잘 작동합니다.문제는 정확한 제곱이었습니다. n^2 수렴 (n-1) 대신에 n 왜냐하면 n^2-1 = (n-1)(n+1) 최종 오류는 최종 제수보다 한 단계 아래에 있었고 알고리즘은 종료되었습니다.오류를 계산하기 전에 원래 인수에 하나를 추가하면 쉽게 수정할 수 있습니다.(세제곱근의 경우 2개 추가 등)
이 알고리즘의 좋은 특성 중 하나는 숫자가 완전제곱수인지 즉시 알 수 있다는 것입니다. 즉, 뉴턴 방법의 최종 오류(수정 아님)는 0이 됩니다.간단한 수정으로 빠르게 계산할 수도 있습니다. floor(sqrt(x)) 가장 가까운 정수 대신.이는 여러 오일러 문제에 유용합니다.
정사각형의 마지막 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에 대한 것입니다.
먼저 모듈러스가 2인 제곱 잔차가 있는지 테스트한 다음 최종 모듈러스를 기준으로 테스트한 다음 Math.sqrt를 사용하여 최종 테스트를 수행합니다.나는 맨 위 포스트에서 아이디어를 생각해냈고, 이를 확장하려고 시도했습니다.어떤 의견이나 제안에도 감사드립니다.
업데이트: 모듈러스(modSq) 및 모듈러스 베이스 44352에 의한 테스트를 사용하여 내 테스트는 최대 1,000,000,000의 숫자에 대해 OP 업데이트 시간의 96%에서 실행됩니다.
일반적인 비트 길이를 고려하여(여기서는 특정 유형을 사용했지만) 아래와 같이 단순한 알고리즘을 디자인하려고 했습니다.처음에는 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;
}
이것이 이전에 언급되었는지 모르겠습니다.그런데 해결책을 찾았어요 여기:
int result = (int)(floor(sqrt(b)) - ceil(sqrt(a)) + 1);
속도가 문제라면 가장 일반적으로 사용되는 입력 세트와 해당 값을 조회 테이블로 분할한 다음 예외적인 경우에 대해 생각해낸 최적화된 매직 알고리즘을 수행하는 것은 어떨까요?
'마지막 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("};");
}
결과는 다음과 같습니다.
(편집:prettify.js의 성능 저하로 인해 제외되었습니다.보려면 개정 내역을 확인하세요.)
CPU 사이클 측면에서 어떻게 비교되는지는 모르겠지만 가장 간단하고 간결한 방법은 다음과 같습니다.근이 정수인지 알고 싶은 경우에만 유용합니다.그것이 정수인지 정말로 관심이 있다면 그것을 알아낼 수도 있습니다.다음은 간단한 (그리고 순수한) 함수입니다:
public static boolean isRootWhole(double number) {
return Math.sqrt(number) % 1 == 0;
}
미세 최적화가 필요하지 않은 경우 단순성과 유지 관리 측면에서 이 답변이 더 좋습니다.음수를 얻으려면 숫자 인수에 Math.abs()를 Math.sqrt() 인수로 사용하는 것이 좋습니다.
내 3.6Ghz Intel i7-4790 CPU에서 이 알고리즘을 0~10,000,000에서 실행하는 데 계산당 평균 35~37나노초가 걸렸습니다.10번의 순차적 실행을 수행하여 천만 평방미터 계산 각각에 소요된 평균 시간을 인쇄했습니다.각 총 실행을 완료하는 데 600ms가 조금 넘었습니다.
더 적은 수의 계산을 수행하는 경우 이전 계산에 시간이 조금 더 걸립니다.
다음은 분할 및 정복 솔루션입니다.
자연수의 제곱근(number)는 자연수(solution), 당신은 쉽게 범위를 결정할 수 있습니다 solution 자릿수를 기준으로 number:
number숫자는 1개입니다:solution범위 = 1 - 4number2자리 숫자가 있습니다:solution범위 = 3 - 10number3자리 숫자가 있습니다:solution범위 = 10 - 40number4자리 숫자가 있습니다:solution범위 = 30 - 100number5자리 숫자가 있습니다:solution범위 = 100 - 400
반복을 알아차리셨나요?
이진 검색 접근 방식에서 이 범위를 사용하여 다음이 있는지 확인할 수 있습니다. solution 그 목적:
number == solution * solution
코드는 다음과 같습니다.
여기 내 수업 SquareRootChecker가 있습니다.
public class SquareRootChecker {
private long number;
private long initialLow;
private long initialHigh;
public SquareRootChecker(long number) {
this.number = number;
initialLow = 1;
initialHigh = 4;
if (Long.toString(number).length() % 2 == 0) {
initialLow = 3;
initialHigh = 10;
}
for (long i = 0; i < Long.toString(number).length() / 2; i++) {
initialLow *= 10;
initialHigh *= 10;
}
if (Long.toString(number).length() % 2 == 0) {
initialLow /= 10;
initialHigh /=10;
}
}
public boolean checkSquareRoot() {
return findSquareRoot(initialLow, initialHigh, number);
}
private boolean findSquareRoot(long low, long high, long number) {
long check = low + (high - low) / 2;
if (high >= low) {
if (number == check * check) {
return true;
}
else if (number < check * check) {
high = check - 1;
return findSquareRoot(low, high, number);
}
else {
low = check + 1;
return findSquareRoot(low, high, number);
}
}
return false;
}
}
그리고 이를 사용하는 방법에 대한 예는 다음과 같습니다.
long number = 1234567;
long square = number * number;
SquareRootChecker squareRootChecker = new SquareRootChecker(square);
System.out.println(square + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677489: true"
long notSquare = square + 1;
squareRootChecker = new SquareRootChecker(notSquare);
System.out.println(notSquare + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677490: false"
속도를 원한다면 정수의 크기가 유한하다는 점을 고려하여 가장 빠른 방법은 (a) 매개변수를 크기별로 분할하는 것입니다(예:가장 큰 비트 세트별로 카테고리로 분류한 다음 해당 범위 내의 완전 정사각형 배열과 비교하여 값을 확인합니다.
Carmac 방법에 관해서는 한 번 더 반복하면 매우 쉬울 것 같으며, 정확도 자릿수가 두 배로 늘어납니다.결국 그것은 매우 좋은 첫 번째 추측을 가진 뉴턴의 반복 방법인 매우 잘린 반복 방법입니다.
현재 최고 기록과 관련하여 두 가지 미세 최적화가 있습니다.
- 수표를 옮기다 vs.mod255를 사용하여 확인한 후 0
- 일반적인(75%) 경우에 대한 모든 검사를 건너뛰도록 4의 분할 거듭제곱을 재정렬합니다.
즉:
// Divide out powers of 4 using binary search
if((n & 0x3L) == 0) {
n >>=2;
if((n & 0xffffffffL) == 0)
n >>= 32;
if((n & 0xffffL) == 0)
n >>= 16;
if((n & 0xffL) == 0)
n >>= 8;
if((n & 0xfL) == 0)
n >>= 4;
if((n & 0x3L) == 0)
n >>= 2;
}
더 나은 방법은 간단할 수도 있습니다.
while ((n & 0x03L) == 0) n >>= 2;
분명히, 각 체크포인트에서 얼마나 많은 숫자가 추려지는지 아는 것은 흥미로울 것입니다. 오히려 체크가 진정으로 독립적인지 의심스럽기 때문에 일이 까다로워집니다.
"저는 긴 값이 완전제곱수인지 확인하는 가장 빠른 방법을 찾고 있습니다(예:그 제곱근은 또 다른 정수입니다.)
답변은 인상적이지만 간단한 확인을 보지 못했습니다.
긴 오른쪽의 첫 번째 숫자가 집합 (0,1,4,5,6,9)의 구성원인지 확인하세요.그렇지 않다면 '완전한 정사각형'이 될 수 없습니다.
예.
4567 - 완전제곱수가 될 수 없습니다.
