Schnellster Weg zu bestimmen, ob die Quadratwurzel einer ganzen Zahl eine ganze Zahl ist

Question

Ich suche nach dem schnellsten Weg, um festzustellen, ob ein long-Wert eine Quadratzahl ist (d. h., ob seine Quadratwurzel eine andere ganze Zahl ist):

1. Ich habe es auf einfache Weise gemacht, indem ich die integrierte Math.sqrt() Funktion verwendet habe, aber ich frage mich, ob es einen schnelleren Weg gibt, indem man sich auf den Bereich der Ganzzahlen beschränkt.
2. Das Führen einer Lookup-Tabelle ist unpraktisch (da es etwa 231,5 Ganzzahlen gibt, deren Quadrat kleiner als 263 ist).

Hier ist der sehr einfache und direkte Weg, den ich jetzt gehe:

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

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

_{Hinweis: Ich verwende diese Funktion in vielen <a href="http://projecteuler.net/" rel="noreferrer">Project Euler</a> Problemen. Also wird niemand anderer jemals diesen Code pflegen müssen. Und diese Art von Mikro-Optimierung könnte tatsächlich einen Unterschied machen, da ein Teil der Herausforderung darin besteht, jeden Algorithmus in weniger als einer Minute auszuführen, und diese Funktion in einigen Problemen Millionen von Malen aufgerufen werden muss.}

---

Ich habe die verschiedenen Lösungen für das Problem ausprobiert:

• Nach umfangreichen Tests habe ich festgestellt, dass das Hinzufügen von 0.5 zum Ergebnis von Math.sqrt() nicht notwendig ist, zumindest nicht auf meinem Computer.
• Der schnelle Kehrwert der Quadratwurzel war schneller, gab aber falsche Ergebnisse für n >= 410881. Jedoch, wie von BobbyShaftoe vorgeschlagen, können wir den FISR-Hack für n < 410881 verwenden.
• Newton's Methode war deutlich langsamer als Math.sqrt(). Das liegt wahrscheinlich daran, dass Math.sqrt() etwas Ähnliches wie Newton's Methode verwendet, aber in der Hardware implementiert ist, so dass sie viel schneller als in Java ist. Außerdem erforderte Newton's Methode immer noch die Verwendung von Doubles.
• Eine modifizierte Newton-Methode, die ein paar Tricks verwendete, so dass nur Ganzzahlenmathematik beteiligt war, erforderte einige Hacks, um Überlauf zu vermeiden (Ich möchte, dass diese Funktion mit allen positiven 64-Bit-Ganzzahlen funktioniert), und war immer noch langsamer als Math.sqrt().
• Die binäre Suche war noch langsamer. Das ergibt Sinn, da die binäre Suche im Durchschnitt 16 Durchläufe benötigen wird, um die Quadratwurzel einer 64-Bit-Zahl zu finden.
• Laut Johns Tests ist die Verwendung von or-Anweisungen in C++ schneller als die Verwendung eines switch, aber in Java und C# scheint es keinen Unterschied zwischen or und switch zu geben.
• Ich habe auch versucht, eine Lookup-Tabelle zu erstellen (als ein privates statisches Array von 64 booleschen Werten). Dann anstatt eines Switch- oder or-Statements würde ich einfach sagen if(lookup[(int)(n&0x3F)]) { test } else return false;. Zu meiner Überraschung war dies (nur leicht) langsamer. Das liegt daran, dass in Java Arraygrenzen überprüft werden.

Answer 1

Ich habe eine Methode gefunden, die ~35% schneller ist als Ihr 6bits+Carmack+sqrt Code, zumindest mit meiner CPU (x86) und Programmiersprache (C/C++). Ihre Ergebnisse können variieren, vor allem weil ich nicht weiß, wie sich der Java-Faktor auswirken wird.

Mein Ansatz ist dreiteilig:

1. Filtern Sie zunächst die offensichtlichen Antworten heraus. Dazu gehören negative Zahlen und die Betrachtung der letzten 4 Bits. (Ich habe festgestellt, dass die letzten sechs Bits nicht hilfreich sind.) Ich antworte auch bei 0 mit Ja. (Wenn Sie den Code unten lesen, beachten Sie, dass meine Eingabe lautet int64 x .)

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

2. Prüfen Sie dann, ob es ein Quadrat modulo 255 = 3 * 5 * 17 ist. Da dies ein Produkt aus drei verschiedenen Primzahlen ist, sind nur etwa 1/8 der Reste modulo 255 Quadrate. Meiner Erfahrung nach kostet der Aufruf des Modulo-Operators (%) jedoch mehr als der Nutzen, den man davon hat, also verwende ich Bittricks mit 255 = 2^8-1, um die Residuen zu berechnen. (Wohl oder übel verwende ich nicht den Trick, einzelne Bytes aus einem Wort auszulesen, sondern nur bitweise-und und Verschiebungen.)

   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.

   Um zu prüfen, ob der Rückstand ein Quadrat ist, suche ich die Antwort in einer vorberechneten Tabelle.

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

3. Versuchen Sie schließlich, die Quadratwurzel mit einer ähnlichen Methode zu berechnen wie Henselsches Lemma . (Ich glaube nicht, dass es direkt anwendbar ist, aber es funktioniert mit einigen Änderungen). Bevor ich das tue, teile ich alle Potenzen von 2 mit einer binären Suche aus:

   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;

   An diesem Punkt muss unsere Zahl 1 mod 8 sein, damit sie ein Quadrat ist.

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

   Die Grundstruktur des Henselschen Lemmas ist die folgende. (Hinweis: Ungetesteter Code; wenn er nicht funktioniert, versuchen Sie t=2 oder 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.

   Die Idee ist, dass man bei jeder Iteration ein Bit zu r, der "aktuellen" Quadratwurzel von x, hinzufügt; jede Quadratwurzel ist genau modulo einer größeren und größeren Potenz von 2, nämlich t/2. Am Ende sind r und t/2-r Quadratwurzeln von x modulo t/2. (Beachten Sie, dass, wenn r eine Quadratwurzel von x ist, dann ist es auch -r. Das gilt sogar für Modulo-Zahlen, aber Vorsicht, modulo einiger Zahlen können Dinge sogar mehr als 2 Quadratwurzeln haben; dazu gehören insbesondere Potenzen von 2). Da unsere tatsächliche Quadratwurzel kleiner als 2^32 ist, können wir an diesem Punkt einfach prüfen, ob r oder t/2-r echte Quadratwurzeln sind. In meinem aktuellen Code verwende ich die folgende modifizierte Schleife:

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

   Die Beschleunigung wird hier auf drei Arten erreicht: vorberechneter Startwert (entspricht ~10 Iterationen der Schleife), früheres Beenden der Schleife und Überspringen einiger t-Werte. Für den letzten Teil betrachte ich z = r - x * x und setzen Sie t als die größte Potenz von 2, die z mit einem Bittrick teilt. Dadurch kann ich t-Werte überspringen, die den Wert von r ohnehin nicht beeinflusst hätten. Der vorberechnete Startwert wählt in meinem Fall die "kleinste positive" Quadratwurzel modulo 8192 aus.

Selbst wenn dieser Code für Sie nicht schneller funktioniert, hoffe ich, dass Ihnen einige der darin enthaltenen Ideen gefallen. Es folgt der vollständige, getestete Code, einschließlich der vorberechneten Tabellen.

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

Answer 2

Ich bin ziemlich spät dran, aber ich hoffe, eine bessere Antwort zu geben; kürzer und (vorausgesetzt, mein Benchmark ist korrekt) auch viel schneller.

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

public boolean isSquare(long x) {
    // Diese Methode testet, ob die 6 am wenigsten signifikanten Bits richtig sind.
    // Das Verschieben des zu testenden Bits in die höchste Position spart uns das Maskieren.
    if (goodMask << x >= 0) return false;
    final int numberOfTrailingZeros = Long.numberOfTrailingZeros(x);
    // Jedes Quadrat endet mit einer geraden Anzahl von Nullen.
    if ((numberOfTrailingZeros & 1) != 0) return false;
    x >>= numberOfTrailingZeros;
    // Nun ist x entweder 0 oder ungerade.
    // In binär endet jedes ungerade Quadrat mit 001.
    // Verschieben Sie den Vorzeichen-Test bis jetzt; behandeln Sie Null im Ast.
    if ((x&7) != 1 | x <= 0) return x == 0;
    // Machen Sie es auf die klassische Weise.
    // Die Korrektheit ist nicht trivial, da die Konvertierung von long in double Verluste verursacht!
    final long tst = (long) Math.sqrt(x);
    return tst * tst == x;
}

Der erste Test erfasst die meisten Nicht-Quadrate schnell. Er verwendet eine 64-Elemente-Tabelle, die in einem long gepackt ist, so dass keine Arrayzugriffskosten (Indirektion und Grenzüberprüfungen) anfallen. Für ein gleichmäßig zufälliges long besteht eine Wahrscheinlichkeit von 81,25%, hier zu enden.

Der zweite Test erfasst alle Zahlen, die eine ungerade Anzahl von Zweien in ihrer Faktorisierung haben. Die Methode Long.numberOfTrailingZeros ist sehr schnell, da sie in eine einzelne i86-Instruktion JIT-ed wird.

Nach dem Entfernen der Nachkommastellen handhabt der dritte Test Zahlen, die mit 011, 101 oder 111 in binär enden, welche keine perfekten Quadrate sind. Er kümmert sich auch um negative Zahlen und behandelt auch 0.

Der letzte Test greift auf double-Arithmetik zurück. Da double nur 53 Bits Mantisse hat, beinhaltet die Konvertierung von long zu double Rundungen für große Werte. Trotzdem ist der Test korrekt (außer wenn der Beweis falsch ist).

Der Versuch, die Idee von mod255 zu integrieren, war nicht erfolgreich.

Answer 3

Sie müssen einige Benchmarking durchführen. Der beste Algorithmus hängt von der Verteilung Ihrer Eingaben ab.

Ihr Algorithmus kann fast optimal sein, aber Sie möchten möglicherweise vor dem Aufrufen Ihrer Quadratwurzelroutine einige Möglichkeiten ausschließen. Sehen Sie sich z.B. die letzte Ziffer Ihrer Zahl im Hexadezimalsystem an, indem Sie ein bitweises "und" durchführen. Perfekte Quadrate können im Hexadezimalsystem nur mit 0, 1, 4 oder 9 enden. Daher können Sie für 75% Ihrer Eingaben (sofern sie gleichmäßig verteilt sind) einen Aufruf der Quadratwurzel gegen einige sehr schnelle Bit-Tricks austauschen.

Kip hat den folgenden Code benchmarked, der den Hex-Trick implementiert. Bei der Prüfung von Zahlen von 1 bis 100.000.000 lief dieser Code doppelt so schnell wie das Original.

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

Als ich den analogen Code in C++ getestet habe, lief er tatsächlich langsamer als das Original. Wenn ich jedoch die switch-Anweisung eliminierte, machte der Hex-Trick den Code noch einmal doppelt so schnell.

int isPerfectSquare(int n)
{
    int h = n & 0xF;  // h ist die letzte hexadezimale "Ziffer"
    if (h > 9)
        return 0;
    // Verwenden Sie 'faule Auswertung', um so schnell wie möglich aus der if-Anweisung auszusteigen
    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;
}

Die Eliminierung der switch-Anweisung hatte wenig Auswirkung auf den C#-Code.

Answer 4

Ich habe über die schrecklichen Zeiten nachgedacht, die ich im Numerical Analysis-Kurs verbracht habe.

Und dann erinnere ich mich daran, dass es diese Funktion gab, die im Quake-Quellcode herumgeisterte:

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

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;  // böses Hacking auf der Gleitkommabiterebene
  i  = 0x5f3759df - ( i >> 1 ); // wtf?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1. Iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2. Iteration, das kann entfernt werden

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

Was im Grunde eine Quadratwurzel berechnet, indem Newtons Annäherungsfunktion verwendet wird (ich kann mich nicht an den genauen Namen erinnern).

Es sollte verwendbar sein und möglicherweise schneller sein, es stammt aus einem der phänomenalen Spiele der id Software!

Es ist in C++ geschrieben, aber es sollte nicht zu schwer sein, dieselbe Technik in Java zu verwenden, sobald man die Idee verstanden hat:

Ursprünglich habe ich es hier gefunden: https://web.archive.org/web/20110708173806/https://www.codemaestro.com/reviews/9

Erklärung der Newton-Methode bei Wikipedia: http://en.wikipedia.org/wiki/Newton%27s_method

Sie können dem Link folgen, um mehr darüber zu erfahren, wie es funktioniert, aber wenn es Sie nicht interessiert, dann ist dies ungefähr das, woran ich mich vom Lesen des Blogs und vom Besuch des Numerical Analysis-Kurses erinnere:

• die * (long*) &y ist im Grunde eine schnelle Funktion zum Konvertieren in long, damit Ganzzahloperationen auf den rohen Bytes angewendet werden können.
• die Zeile 0x5f3759df - (i >> 1); ist ein vorberechneter Startwert für die Annäherungsfunktion.
• die * (float*) &i konvertiert den Wert zurück in Gleitkommazahl.
• die Zeile y = y * ( threehalfs - ( x2 * y * y ) ) iteriert im Grunde den Wert erneut über die Funktion.

Die Annäherungsfunktion liefert genauere Werte, je öfter man die Funktion über das Ergebnis iteriert. Im Fall von Quake reicht eine Iteration "aus", aber wenn es für Sie nicht ausreicht... dann könnten Sie so viele Iterationen hinzufügen, wie Sie benötigen.

Dies sollte schneller sein, weil es die Anzahl der Divisionen, die bei einfachem Quadratwurzeln gemacht werden, auf eine einfache Division durch 2 (eigentlich eine * 0.5F Multiplikationsoperation) reduziert und stattdessen durch einige festgelegte Anzahl von Multiplikationsoperationen ersetzt.

Answer 5

Ich bin mir nicht sicher, ob es schneller oder sogar genauer wäre, aber Sie könnten den John Carmack's Magical Square Root-Algorithmus verwenden, um die Quadratwurzel schneller zu lösen. Sie könnten dies wahrscheinlich leicht für alle möglichen 32-Bit-Integer testen und validieren, dass Sie tatsächlich korrekte Ergebnisse erhalten haben, da es nur eine Annäherung ist. Aber jetzt, wo ich darüber nachdenke, ist die Verwendung von Doubles auch eine Annäherung, also bin ich mir nicht sicher, wie sich das auswirken würde.