Szukam najszybszego sposobu ustalenia, czy longwartość jest idealnym kwadratem (tzn. Jej pierwiastek kwadratowy jest inną liczbą całkowitą):

1. Zrobiłem to w prosty sposób, korzystając z wbudowanej Math.sqrt() funkcji, ale zastanawiam się, czy istnieje sposób, aby to zrobić szybciej, ograniczając się do domeny zawierającej tylko liczby całkowite.
2. Utrzymywanie tabeli odnośników jest niepraktyczne (ponieważ istnieje około 2 ^31,5 liczb całkowitych, których kwadrat jest mniejszy niż 2 ⁶³ ).

Oto bardzo prosty i bezpośredni sposób, w jaki to teraz robię:

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

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

_{Uwaga: Używam tej funkcji w wielu problemach z Project Euler . Dlatego nikt inny nie będzie musiał utrzymywać tego kodu. Tego rodzaju mikrooptymalizacja może w rzeczywistości coś zmienić, ponieważ częścią wyzwania jest wykonanie każdego algorytmu w mniej niż minutę, a funkcja ta będzie musiała zostać wywołana miliony razy w przypadku niektórych problemów.}

Próbowałem różnych rozwiązań tego problemu:

• Po wyczerpujących testach odkryłem, że dodawanie 0.5do wyniku Math.sqrt () nie jest konieczne, przynajmniej nie na moim komputerze.
• Szybko odwrotność pierwiastka kwadratowego był szybszy, ale to dało nieprawidłowych wyników dla n> = 410881. Jednak, jak sugeruje BobbyShaftoe , możemy użyć hack FISR dla n <410881.
• Metoda Newtona była o wiele wolniejsza niż Math.sqrt(). Jest tak prawdopodobnie dlatego, że Math.sqrt()używa czegoś podobnego do metody Newtona, ale zaimplementowanej w sprzęcie, dzięki czemu jest znacznie szybsza niż w Javie. Ponadto Metoda Newtona nadal wymagała użycia podwójnych.
• Zmodyfikowana metoda Newtona, która wykorzystywała kilka sztuczek, aby zaangażować tylko matematykę całkowitą, wymagała kilku hacków, aby uniknąć przepełnienia (chcę, aby ta funkcja działała ze wszystkimi dodatnimi liczbami całkowitymi ze znakiem 64-bitowym), i nadal była wolniejsza niż Math.sqrt().
• Binarny kotlet był jeszcze wolniejszy. Ma to sens, ponieważ przecięcie binarne wymaga średnio 16 przejść, aby znaleźć pierwiastek kwadratowy liczby 64-bitowej.
• Według testów Johna używanie orinstrukcji w C ++ jest szybsze niż używanie a switch, ale w Javie i C # wydaje się, że nie ma różnicy między ori switch.
• Próbowałem także utworzyć tabelę odnośników (jako prywatną statyczną tablicę 64 wartości boolowskich). Następnie zamiast przełącznika lub orinstrukcji, powiedziałbym tylko if(lookup[(int)(n&0x3F)]) { test } else return false;. Ku mojemu zaskoczeniu było to (tylko nieco) wolniejsze. Wynika to z faktu, że granice tablic są sprawdzane w Javie .

Opracowałem metodę, która działa ~ 35% szybciej niż twój 6-bitowy kod + Carmack + kod sqrt, przynajmniej z moim procesorem (x86) i językiem programowania (C / C ++). Twoje wyniki mogą się różnić, szczególnie dlatego, że nie wiem, jak będzie się grał czynnik Java.

Moje podejście jest trojakie:

1. Najpierw odfiltruj oczywiste odpowiedzi. Obejmuje to liczby ujemne i patrząc na ostatnie 4 bity. (Odkryłem, że spojrzenie na ostatnie sześć nie pomogło.) Odpowiadam również na „tak” (czytając poniższy kod, zauważ, że moje dane wejściowe są int64 x).

   if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) )
       return false;
   if( x == 0 )
       return true;

2. Następnie sprawdź, czy jest to moduł kwadratowy 255 = 3 * 5 * 17. Ponieważ jest to iloczyn trzech różnych liczb pierwszych, tylko około 1/8 reszt mod 255 to kwadraty. Jednak z mojego doświadczenia wynika, że ​​wywołanie operatora modulo (%) kosztuje więcej niż korzyść, którą się otrzymuje, więc używam sztuczek bitowych obejmujących 255 = 2 ^ 8-1 do obliczenia pozostałości. (Na lepsze lub gorsze, nie używam sztuczki polegającej na odczytywaniu poszczególnych bajtów ze słowa, tylko bitowe i zmiany).

   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.

   Aby faktycznie sprawdzić, czy pozostałość jest kwadratem, szukam odpowiedzi w obliczonej wcześniej tabeli.

   if( bad255[y] )
       return false;
   // However, I just use a table of size 512

3. Na koniec spróbuj obliczyć pierwiastek kwadratowy przy użyciu metody podobnej do lematu Hensela . (Nie sądzę, aby można go było zastosować bezpośrednio, ale działa z pewnymi modyfikacjami.) Przedtem dzielę wszystkie moce 2 za pomocą wyszukiwania binarnego:

   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;

   W tym momencie, aby nasza liczba była kwadratem, musi to być 1 mod 8.

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

   Podstawowa struktura lematu Hensela jest następująca. (Uwaga: nieprzetestowany kod; jeśli nie działa, spróbuj t = 2 lub 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.

   Chodzi o to, że przy każdej iteracji dodajesz jeden bit do r, „bieżący” pierwiastek kwadratowy z x; każdy pierwiastek kwadratowy jest dokładnym modułem o coraz większej potędze 2, mianowicie t / 2. Na końcu r i t / 2-r będą pierwiastkami kwadratowymi x modulo t / 2. (Zauważ, że jeśli r jest pierwiastkiem kwadratowym z x, to tak samo jest z -r. To prawda, nawet liczby modulo, ale uwaga, modulo niektóre liczby, rzeczy mogą mieć nawet więcej niż 2 pierwiastki kwadratowe; w szczególności obejmuje to potęgi 2. ) Ponieważ nasz rzeczywisty pierwiastek kwadratowy jest mniejszy niż 2 ^ 32, w tym momencie możemy faktycznie sprawdzić, czy r lub t / 2-r są rzeczywistymi pierwiastkami kwadratowymi. W moim aktualnym kodzie używam następującej zmodyfikowanej pętli:

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

   Przyspieszenie tutaj uzyskuje się na trzy sposoby: wstępnie obliczoną wartość początkową (równoważną ~ 10 iteracjom pętli), wcześniejsze wyjście z pętli i pominięcie niektórych wartości t. Na ostatnią część patrzę z = r - x * xi ustawiam t na największą potęgę 2 dzielących z odrobiną sztuczki. To pozwala mi pominąć wartości t, które i tak nie wpłynęłyby na wartość r. Wstępnie obliczona wartość początkowa w moim przypadku wybiera moduł „najmniejszego dodatniego” pierwiastka kwadratowego 8192.

Nawet jeśli ten kod nie działa szybciej dla Ciebie, mam nadzieję, że podoba Ci się niektóre zawarte w nim pomysły. Następuje pełny, przetestowany kod, w tym wstępnie obliczone tabele.

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

Jestem spóźniony na przyjęcie, ale mam nadzieję, że udzielę lepszej odpowiedzi; krótszy i (zakładając, że mój test jest poprawny) również znacznie szybszy .

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

Pierwszy test szybko wychwytuje większość elementów innych niż kwadraty. Używa 64-elementowej tabeli zapakowanej w długi, więc nie ma żadnych kosztów dostępu do tablicy (pośrednie i sprawdzanie granic). Dla równomiernie losowego longprawdopodobieństwo, że skończy się tutaj, wynosi 81,25%.

Drugi test wyłapuje wszystkie liczby o nieparzystej liczbie dwójkowej w rozkładzie na czynniki. Metoda Long.numberOfTrailingZerosjest bardzo szybka, ponieważ przekształca JIT w pojedynczą instrukcję i86.

Po usunięciu końcowych zer trzeci test obsługuje liczby kończące się na 011, 101 lub 111 w systemie binarnym, które nie są idealnymi kwadratami. Dba również o liczby ujemne, a także obsługuje 0.

Ostatni test powraca do doublearytmetyki. Podobnie jak doublema tylko 53 bity mantysy, konwersja z longna doubleobejmuje zaokrąglanie dużych wartości. Niemniej jednak test jest poprawny (chyba że dowód jest błędny).

Próba wprowadzenia pomysłu mod255 nie powiodła się.

Będziesz musiał przeprowadzić testy porównawcze. Najlepszy algorytm będzie zależeć od rozkładu twoich danych wejściowych.

Twój algorytm może być prawie optymalny, ale możesz zrobić szybkie sprawdzenie, aby wykluczyć pewne możliwości przed wywołaniem procedury pierwiastka kwadratowego. Na przykład spójrz na ostatnią cyfrę swojego numeru szesnastkowego, wykonując nieco „i”. Idealne kwadraty mogą kończyć się na 0, 1, 4 lub 9 na podstawie 16, więc dla 75% twoich danych wejściowych (zakładając, że są one równomiernie rozmieszczone) możesz uniknąć wezwania do pierwiastka kwadratowego w zamian za bardzo szybkie kręcenie bitów.

Kip przeprowadził analizę porównawczą następującego kodu implementującego sztuczkę szesnastkową. Podczas testowania liczb od 1 do 100 000 000 ten kod działał dwa razy szybciej niż oryginał.

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

Kiedy testowałem analogiczny kod w C ++, faktycznie działał wolniej niż oryginał. Kiedy jednak wyeliminowałem instrukcję switch, sztuczka szesnastkowa ponownie sprawia, że ​​kod jest dwa razy szybszy.

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

Wyeliminowanie instrukcji switch miało niewielki wpływ na kod C #.

Myślałem o okropnych czasach, które spędziłem na kursie analizy numerycznej.

A potem pamiętam, że ta funkcja krążyła po sieci z kodu źródłowego Quake:

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

Który zasadniczo oblicza pierwiastek kwadratowy, używając funkcji aproksymacji Newtona (nie pamiętam dokładnej nazwy).

Powinien być użyteczny, a może nawet szybszy, pochodzi z jednej z fenomenalnych gier oprogramowania id!

Jest napisany w C ++, ale nie powinno być zbyt trudne ponowne użycie tej samej techniki w Javie, gdy tylko wpadniesz na pomysł:

Pierwotnie znalazłem na: http://www.codemaestro.com/reviews/9

Metoda Newtona wyjaśniona na wikipedii: http://en.wikipedia.org/wiki/Newton%27s_method

Możesz skorzystać z linku, aby uzyskać więcej informacji o tym, jak to działa, ale jeśli nie przejmujesz się tym, to mniej więcej to pamiętam z czytania bloga i z kursu analizy numerycznej:

• * (long*) &yjest w zasadzie fast funkcja konwersji do operacji tak długo całkowita może być stosowany na surowych bajtów.
• 0x5f3759df - (i >> 1);jest to wartość nasion uprzednio obliczone przez funkcję aproksymacji.
• * (float*) &ikonwertuje wartość z powrotem do zmiennoprzecinkowych.
• y = y * ( threehalfs - ( x2 * y * y ) )linia bascially iteracje wartości ponad funkcję ponownie.

Funkcja aproksymacji podaje bardziej precyzyjne wartości, im bardziej iterujesz funkcję nad wynikiem. W przypadku Quake'a jedna iteracja jest „wystarczająco dobra”, ale jeśli to nie było dla ciebie ... to możesz dodać tyle iteracji, ile potrzebujesz.

Powinno to być szybsze, ponieważ zmniejsza liczbę operacji dzielenia wykonanych naiwnym kwadratowym rootowaniu do zwykłego dzielenia przez 2 (w rzeczywistości * 0.5Foperację mnożenia) i zastępuje ją kilkoma ustalonymi liczbami operacji mnożenia.

Nie jestem pewien, czy byłoby to szybsze, czy nawet dokładne, ale możesz użyć algorytmu Magical Square Root Johna Carmacka , aby szybciej rozwiązać pierwiastek kwadratowy. Prawdopodobnie mógłbyś łatwo przetestować to dla wszystkich możliwych 32-bitowych liczb całkowitych i sprawdzić, czy faktycznie masz poprawne wyniki, ponieważ jest to tylko przybliżenie. Jednak teraz, gdy o tym myślę, użycie podwójnych jest również przybliżone, więc nie jestem pewien, jak to by się stało.

Jeśli wykonasz dwójkę binarną, aby znaleźć „właściwy” pierwiastek kwadratowy, możesz dość łatwo wykryć, czy wartość, którą masz, jest wystarczająco bliska, aby powiedzieć:

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

Po obliczeniu n^2opcje są następujące:

• n^2 = target: gotowe, zwróć wartość true
• n^2 + 2n + 1 > target > n^2 : jesteś blisko, ale to nie jest idealne: zwróć false
• n^2 - 2n + 1 < target < n^2 : to samo
• target < n^2 - 2n + 1 : binarny kotlet na niższym poziomie n
• target > n^2 + 2n + 1 : dwójkowy na wyższym n

(Przepraszamy, ten parametr jest używany njako bieżące przypuszczenie i targetza parametr. Przepraszamy za zamieszanie!)

Nie wiem, czy to będzie szybsze, czy nie, ale warto spróbować.

EDYCJA: Binarny rąbek nie musi również przyjmować całego zakresu liczb całkowitych, (2^x)^2 = 2^(2x)więc gdy już znajdziesz bit najwyższego zestawu w swoim celu (można to zrobić za pomocą sztuczki polegającej na kręceniu się; zapominam dokładnie jak) możesz szybko uzyskać szereg potencjalnych odpowiedzi. Pamiętaj, że naiwny binarny kotlet nadal będzie wymagał tylko 31 lub 32 iteracji.

Przeprowadziłem własną analizę kilku algorytmów w tym wątku i opracowałem kilka nowych wyników. Możesz zobaczyć te stare wyniki w historii edycji tej odpowiedzi, ale nie są one dokładne, ponieważ popełniłem błąd i straciłem czas na analizę kilku algorytmów, które nie są blisko. Jednak wyciągając wnioski z kilku różnych odpowiedzi, mam teraz dwa algorytmy, które miażdżą „zwycięzcę” tego wątku. Oto podstawowa rzecz, którą robię inaczej niż wszyscy inni:

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

Jednak ten prosty wiersz, który przez większość czasu dodaje jedną lub dwie bardzo szybkie instrukcje, znacznie upraszcza switch-caseinstrukcję w jedną instrukcję if. Może jednak zwiększyć czas działania, jeśli wiele z testowanych liczb ma znaczącą moc dwóch czynników.

Poniższe algorytmy są następujące:

• Internet - opublikowana odpowiedź Kipa
• Durron - Moja zmodyfikowana odpowiedź przy użyciu odpowiedzi jednoprzebiegowej jako podstawy
• DurronTwo - Moja zmodyfikowana odpowiedź przy użyciu odpowiedzi dwuprzebiegowej (autor: @JohnnyHeggheim), z kilkoma drobnymi modyfikacjami.

Oto przykładowe środowisko wykonawcze, jeśli liczby są generowane przy użyciu 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

Oto przykładowe środowisko uruchomieniowe, jeśli działa tylko na pierwszych milionach długości:

 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

Jak widać, DurronTwolepiej sprawdza się w przypadku dużych nakładów, ponieważ bardzo często korzysta z magicznej sztuczki, ale staje się nieczytelny w porównaniu z pierwszym algorytmem i Math.sqrtponieważ liczby są znacznie mniejsze. Tymczasem prostsze Durronjest ogromnym zwycięzcą, ponieważ nigdy nie musi dzielić 4 razy wiele razy w pierwszym milionie liczb.

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

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

I moja uprząż porównawcza: (wymaga suwmiarki 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);
    }
}

AKTUALIZACJA: Stworzyłem nowy algorytm, który jest szybszy w niektórych scenariuszach, wolniejszy w innych, otrzymałem różne testy porównawcze na podstawie różnych danych wejściowych. Obliczając modulo 0xFFFFFF = 3 x 3 x 5 x 7 x 13 x 17 x 241, możemy wyeliminować 97,82% liczb, które nie mogą być kwadratami. Można to zrobić (w pewnym sensie) w jednym wierszu za pomocą 5 operacji bitowych:

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

Otrzymany wskaźnik to albo 1) reszta, 2) reszta + 0xFFFFFF, albo 3) reszta + 0x1FFFFFE. Oczywiście musimy mieć tabelę przeglądową dla reszt modulo 0xFFFFFF, która ma rozmiar około 3 MB (w tym przypadku jest przechowywana jako liczby dziesiętne tekstu ascii, nie jest optymalna, ale można ją łatwo poprawić za pomocą ByteBuffera itd. Ale ponieważ jest to wstępne obliczenie , nie robi tego) to ważne. Możesz znaleźć plik tutaj (lub sam go wygenerować):

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

Ładuję go do booleantablicy takiej jak ta:

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

Przykładowe środowisko wykonawcze. Pokonał Durron(wersja pierwsza) w każdym badaniu, które prowadziłem.

 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

Zastosowanie metody Newtona powinno być znacznie szybsze , aby obliczyć pierwiastek kwadratowy z liczby całkowitej , a następnie wyprostować tę liczbę i sprawdzić, tak jak ma to miejsce w obecnym rozwiązaniu. Metoda Newtona jest podstawą rozwiązania Carmack wspomnianego w kilku innych odpowiedziach. Powinieneś być w stanie uzyskać szybszą odpowiedź, ponieważ interesuje Cię tylko całkowita liczba części root, co pozwala wcześniej zatrzymać algorytm aproksymacji.

Kolejna optymalizacja, którą możesz wypróbować: Jeśli pierwiastek cyfrowy liczby nie kończy się na 1, 4, 7 lub 9, liczba nie jest idealnym kwadratem. Można to wykorzystać jako szybki sposób na wyeliminowanie 60% danych wejściowych przed zastosowaniem algorytmu wolniejszego pierwiastka kwadratowego.

Chcę, aby ta funkcja działała ze wszystkimi dodatnimi liczbami całkowitymi ze znakiem 64-bitowym

Math.sqrt()działa z podwójnymi jako parametrami wejściowymi, więc nie uzyskasz dokładnych wyników dla liczb całkowitych większych niż 2 ^ 53 .

Dla przypomnienia, innym podejściem jest wykorzystanie pierwotnego rozkładu. Jeśli każdy czynnik rozkładu jest parzysty, liczba jest idealnym kwadratem. Chcecie więc sprawdzić, czy liczbę można rozłożyć na iloczyn kwadratów liczb pierwszych. Oczywiście nie trzeba uzyskiwać takiego rozkładu, aby sprawdzić, czy on istnieje.

Najpierw zbuduj tabelę kwadratów liczb pierwszych, które są mniejsze niż 2 ^ 32. Jest to znacznie mniej niż tabela wszystkich liczb całkowitych do tego limitu.

Rozwiązanie byłoby wtedy takie:

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

Myślę, że to trochę tajemnicze. Na każdym kroku sprawdza, czy kwadrat liczby pierwszej dzieli liczbę wejściową. Jeśli tak, dzieli liczbę przez kwadrat tak długo, jak to możliwe, aby usunąć ten kwadrat z głównego rozkładu. Jeśli w wyniku tego procesu dojdziemy do 1, to liczbą wejściową był rozkład kwadratu liczb pierwszych. Jeśli kwadrat staje się większy niż sama liczba, to nie ma możliwości, aby ten kwadrat lub jakiekolwiek większe kwadraty mogły go podzielić, więc liczba nie może być rozkładem kwadratów liczb pierwszych.

Biorąc pod uwagę dzisiejszy sqrt wykonywany sprzętowo i potrzebę obliczenia liczb pierwszych tutaj, myślę, że to rozwiązanie jest znacznie wolniejsze. Ale powinno to dać lepsze wyniki niż rozwiązanie z sqrt, które nie będzie działać powyżej 2 ^ 54, jak mówi mrzl w swojej odpowiedzi.

Wskazano, że ostatnie dcyfry idealnego kwadratu mogą przyjmować tylko określone wartości. Ostatnie dcyfry (w bazie b) liczby nsą takie same jak reszta, gdy njest podzielona przez bd, tj. w notacji C n % pow(b, d).

Można to uogólnić na dowolny moduł m, tj. n % mmożna użyć, aby wykluczyć pewien procent liczb z idealnych kwadratów. Moduł, którego obecnie używasz, wynosi 64, co pozwala na 12, tj. 19% pozostałych, jak to możliwe kwadratów. Przy odrobinie kodowania znalazłem moduł 110880, który pozwala tylko 2016, tj. 1,8% pozostałych jako możliwe kwadraty. Tak więc w zależności od kosztu operacji modułu (tj. Podziału) i wyszukiwania tabeli względem pierwiastka kwadratowego na komputerze, użycie tego modułu może być szybsze.

Nawiasem mówiąc, jeśli Java ma sposób na przechowywanie spakowanej tablicy bitów dla tabeli odnośników, nie używaj jej. 110880 32-bitowe słowa w dzisiejszych czasach to niewiele pamięci RAM, a pobranie słowa maszynowego będzie szybsze niż pobranie jednego bitu.

Problem liczb całkowitych zasługuje na rozwiązanie liczb całkowitych. A zatem

Wykonaj wyszukiwanie binarne na (nieujemnych) liczbach całkowitych, aby znaleźć największą liczbę całkowitą taką, że t**2 <= n. Następnie sprawdź, czy r**2 = ndokładnie. To zajmuje czas O (log n).

Jeśli nie wiesz, jak przeszukiwać binarnie liczby całkowite dodatnie, ponieważ zestaw jest nieograniczony, jest to łatwe. Zaczynasz od obliczenia rosnącej funkcji f (powyżej f(t) = t**2 - n) na potęgach dwóch. Kiedy zobaczysz, że zmienia się na dodatnią, znalazłeś górną granicę. Następnie możesz wykonać standardowe wyszukiwanie binarne.

Następujące uproszczenie rozwiązania maaartinus wydaje się zmniejszać o kilka punktów procentowych czas działania, ale nie jestem wystarczająco dobry w testowaniu porównawczym, aby stworzyć benchmark, któremu mogę zaufać:

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

Warto sprawdzić, jak pominąć pierwszy test,

if (goodMask << x >= 0) return false;

wpłynie na wydajność.

Aby uzyskać wydajność, bardzo często trzeba iść na kompromisy. Inni wyrażali różne metody, jednak zauważyłeś, że hack Carmacka był szybszy do pewnych wartości N. Następnie powinieneś sprawdzić „n”, a jeśli jest on mniejszy niż liczba N, użyj hacka Carmacka, w przeciwnym razie użyj innej opisanej metody w odpowiedziach tutaj.

Jest to najszybsza implementacja Java, jaką mogłem wymyślić, wykorzystując kombinację technik sugerowanych przez innych w tym wątku.

• Test Mod-256
• Niedokładny test mod-3465 (pozwala uniknąć dzielenia liczb całkowitych kosztem niektórych fałszywych trafień)
• Pierwiastek kwadratowy zmiennoprzecinkowy, zaokrąglić i porównać z wartością wejściową

Eksperymentowałem również z tymi modyfikacjami, ale nie pomogły one w wydajności:

• Dodatkowy test mod-255
• Dzielenie wartości wejściowej przez potęgi 4
• Szybki odwrotny pierwiastek kwadratowy (aby pracować dla wysokich wartości N, potrzebuje 3 iteracji, co wystarcza, aby był wolniejszy niż sprzętowa funkcja pierwiastka kwadratowego).

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

}