long값이 완벽한 제곱 인지 여부를 결정하는 가장 빠른 방법을 찾고 있습니다 (즉, 제곱근이 다른 정수임).
- 내장
Math.sqrt()
함수 를 사용하여 쉬운 방법을 수행 했지만 정수 전용 도메인으로 제한하여 더 빨리 수행 할 수있는 방법이 있는지 궁금합니다. - 조회 테이블을 유지 관리하는 것은 실용적이지 않습니다 ( 제곱이 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;
}
참고 : 많은 Project Euler 문제 에서이 기능을 사용하고 있습니다. 따라서 아무도이 코드를 유지할 필요가 없습니다. 이런 종류의 마이크로 최적화는 실제로 차이를 만들 수 있습니다. 도전 과제의 일부는 모든 알고리즘을 1 분 이내에 수행하는 것이므로이 기능은 일부 문제에서 수백만 번 호출되어야합니다.
나는 문제에 대한 다른 해결책을 시도했다.
- 철저한 테스트
0.5결과, 적어도 내 컴퓨터에는 Math.sqrt () 결과 를 추가 할 필요가 없습니다. - 제곱근 역 고속은 빨리했지만, 그것은 잘못된 결과를 준 N> = 410881. 그러나,에 의해 제안 BobbyShaftoe , 우리는 N <410881에 대한 FISR 해킹을 사용할 수 있습니다.
- 뉴턴의 방법은보다 약간 느 렸습니다
Math.sqrt(). 아마도Math.sqrt()Newton의 Method와 비슷한 것을 사용 하기 때문일 수 있지만 하드웨어에서 구현되어 Java보다 훨씬 빠릅니다. 또한, 뉴턴의 방법은 여전히 복식을 사용해야했습니다. - 정수 수학 만 관련되도록 몇 가지 트릭을 사용하는 수정 된 뉴턴의 방법은 오버플로를 피하기 위해 일부 해킹이 필요했습니다 (이 함수는 모든 양의 64 비트 부호있는 정수와 함께 작동하기를 원합니다)
Math.sqrt(). - 이진 절단은 더 느렸다. 이진 절단은 64 비트 숫자의 제곱근을 찾기 위해 평균 16 번의 패스가 필요하기 때문에 이치에 맞습니다.
- 요한의 테스트에 따르면, 사용하는
or문은 빠른 C ++에서을 사용하는 것보다switch,하지만 자바와 C #의 사이에 차이가없는 것으로 나타납니다or하고switch. - 또한 조회 테이블 (64 부울 값의 개인 정적 배열)을 만들려고했습니다. 그런 다음 switch 나
orstatement 대신 그냥 말합니다if(lookup[(int)(n&0x3F)]) { test } else return false;. 놀랍게도, 이것은 (약간) 느려졌습니다. 배열 범위는 Java에서 확인 되기 때문 입니다.
답변
적어도 내 CPU (x86) 및 프로그래밍 언어 (C / C ++)에서 6 비트 + 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인지 확인하십시오. 이는 3 개의 고유 한 소수의 곱이므로 잔차 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 - 마지막으로 Hensel ‘s lemma 와 유사한 방법을 사용하여 제곱근을 계산하십시오 . (나는 그것이 직접 적용 할 수 없다고 생각하지만 약간의 수정으로 작동합니다.) 그렇게하기 전에 2의 모든 힘을 이진 검색으로 나눕니다.
if((x & 4294967295LL) == 0) x >>= 32; if((x & 65535) == 0) x >>= 16; if((x & 255) == 0) x >>= 8; if((x & 15) == 0) x >>= 4; if((x & 3) == 0) x >>= 2;이 시점에서 숫자가 정사각형이 되려면 1 mod 8이어야합니다.
if((x & 7) != 1) return false;헨젤의 기본 정리의 기본 구조는 다음과 같습니다. (참고 : 테스트되지 않은 코드. 작동하지 않으면 t = 2 또는 8을 시도하십시오.)
int64 t = 4, r = 1; t <<= 1; r += ((x - r * r) & t) >> 1; t <<= 1; r += ((x - r * r) & t) >> 1; t <<= 1; r += ((x - r * r) & t) >> 1; // Repeat until t is 2^33 or so. Use a loop if you want.각 반복마다 r에 하나의 비트, 즉 x의 “현재”제곱근을 추가하는 것이 좋습니다. 각 제곱근은 정확한 모듈로 2의 더 큰 거듭 제곱, 즉 t / 2입니다. 마지막에, r과 t / 2-r은 x 모듈로 t / 2의 제곱근이됩니다. (r이 x의 제곱근이면 -r도 마찬가지입니다.) 이것은 모듈로 수조차도 사실이지만 모듈로 일부 숫자를 조심하면 2 제곱근 이상을 가질 수 있습니다. 특히 2의 제곱을 포함합니다. ) 실제 제곱근이 2 ^ 32보다 작기 때문에 실제로 r 또는 t / 2-r이 실제 제곱근인지 확인할 수 있습니다. 실제 코드에서는 다음 수정 루프를 사용합니다.
int64 r, t, z; r = start[(x >> 3) & 1023]; do { z = x - r * r; if( z == 0 ) return true; if( z < 0 ) return false; t = z & (-z); r += (z & t) >> 1; if( r > (t >> 1) ) r = t - r; } while( t <= (1LL << 33) );여기에서 속도 향상은 세 가지 방법, 즉 사전 계산 된 시작 값 (루프의 ~ 10 반복과 동일), 루프의 초기 종료 및 일부 t 값을 건너 뛰는 방식으로 얻을 수 있습니다. 마지막 부분에서는를보고
z = r - x * xt를 비트 트릭으로 나누는 2의 최대 거듭 제곱으로 t를 설정했습니다. 이것은 어쨌든 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 개 항목으로 구성된 긴 테이블을 사용하므로 어레이 액세스 비용 (간접 및 범위 검사)이 없습니다. 균일하게 무작위 long인 경우 여기에서 끝날 확률은 81.25 %입니다.
두 번째 테스트는 인수 분해에서 홀수 2를 갖는 모든 숫자를 포착합니다. 방법Long.numberOfTrailingZeros 은 단일 i86 명령어로 JIT-ed되므로 매우 빠릅니다.
후행 0을 삭제 한 후 세 번째 테스트는 011, 101 또는 111로 끝나는 숫자를 이진수로 처리합니다. 이는 완전한 제곱이 아닙니다. 또한 음수를 고려하고 0도 처리합니다.
최종 테스트는 double산술로 돌아갑니다 . AS는 double단지 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 Source 코드에서 ‘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에 설명 된 Newton의 방법 : http://en.wikipedia.org/wiki/Newton%27s_method
작동 방식에 대한 자세한 설명을 보려면 링크를 따라갈 수 있지만, 신경 쓰지 않으면 블로그를 읽고 수치 분석 과정을 수강 할 때 대략적으로 기억합니다.
- 그만큼
* (long*) &y기본적으로 정수 연산이 생의 바이트에 적용 할 수 있도록 빠른 변환 – 투 – 긴 기능입니다. 0x5f3759df - (i >> 1);라인 근사 함수에 대한 미리 계산 된 시드 값이다.- 는
* (float*) &i값을 부동 소수점으로 다시 변환합니다. y = y * ( threehalfs - ( x2 * y * y ) )라인 bascially 다시 기능 이상 값으로 반복.
근사 함수는 결과에 대해 함수를 반복할수록 더 정확한 값을 제공합니다. Quake의 경우 하나의 반복이 “충분히”충분하지만 그렇지 않은 경우 필요한만큼 반복을 추가 할 수 있습니다.
순진한 제곱근에서 수행되는 나눗셈 연산의 수를 단순 나누기 2 (실제로 * 0.5F곱하기 연산) 로 줄이고 대신 고정 된 곱셈 연산으로 대체 하기 때문에 더 빠릅니다 .
답변
그것이 더 빠르거나 정확한지 확실하지 않지만 John Carmack의 Magical Square Root 알고리즘을 사용하여 제곱근을 더 빨리 풀 수 있습니다. 가능한 모든 32 비트 정수에 대해 이것을 쉽게 테스트하고 appoximation 일뿐이므로 실제로 올바른 결과를 얻었는지 확인할 수 있습니다. 그러나 이제는 더블을 사용하는 것도 근사치이므로 어떻게 작동하는지 잘 모르겠습니다.
답변
이진 절단을 수행하여 “올바른”제곱근을 찾으려면 얻은 값이 충분히 가까운 지 쉽게 알 수 있습니다.
(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의 거듭 제곱을 갖는 경우 런타임에 추가 할 수 있습니다.
아래 알고리즘은 다음과 같습니다.
- 인터넷 -킵의 답변 게시
- Durron- 원 패스 응답을 기본으로 사용하는 수정 된 답변
- DurronTwo- 약간의 수정을 거쳐 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 텍스트 10 진수로 저장되지만 최적은 아니지만 명확하게 개선 할 수는 없습니다 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