1454

Ich suche nach dem schnellsten Weg, um festzustellen, ob ein longWert ein perfektes Quadrat ist (dh seine Quadratwurzel ist eine andere ganze Zahl):

Ich habe es auf einfache Weise mit der integrierten Math.sqrt() Funktion gemacht, aber ich frage mich, ob es eine Möglichkeit gibt, es schneller zu machen, indem Sie sich auf eine Nur-Ganzzahl-Domäne beschränken.
Das Verwalten einer Nachschlagetabelle ist unpraktisch (da es ungefähr 2 ^31,5 Ganzzahlen gibt, deren Quadrat kleiner als 2 ^{63 ist} ).

Hier ist die sehr einfache und unkomplizierte Art, wie ich es jetzt mache:

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 bei vielen Project Euler- Problemen. Niemand sonst wird diesen Code jemals pflegen müssen. Und diese Art der Mikrooptimierung 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 muss bei einigen Problemen millionenfach aufgerufen werden.}

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

Nach ausführlichen Tests stellte ich fest, dass das Hinzufügen 0.5zum Ergebnis von Math.sqrt () nicht erforderlich ist, zumindest nicht auf meinem Computer.
Die schnelle inverse Quadratwurzel war schneller, ergab jedoch falsche Ergebnisse für n> = 410881. Wie von BobbyShaftoe vorgeschlagen , können wir den FISR-Hack für n <410881 verwenden.
Newtons Methode war ein bisschen langsamer als Math.sqrt() . Das liegt wahrscheinlich daranMath.sqrt() etwas Ähnliches wie Newtons Methode verwendet wird, jedoch in der Hardware implementiert ist, sodass es viel schneller als in Java ist. Außerdem erforderte die Newtonsche Methode immer noch die Verwendung von Doppel.
Eine modifizierte Newton-Methode, bei der einige Tricks verwendet wurden, sodass nur ganzzahlige Mathematik beteiligt war, erforderte einige Hacks, um einen Überlauf zu vermeiden (ich möchte, dass diese Funktion mit allen positiven 64-Bit-Ganzzahlen mit Vorzeichen funktioniert), und sie war immer noch langsamer als Math.sqrt() .
Binary Chop war noch langsamer. Dies ist sinnvoll, da der binäre Chop durchschnittlich 16 Durchgänge benötigt, um die Quadratwurzel einer 64-Bit-Zahl zu finden.
Laut Johns Tests ist die Verwendung von orAnweisungen in C ++ schneller als die Verwendung von a switch, aber in Java und C # scheint es keinen Unterschied zwischen orund zu gebenswitch .
Ich habe auch versucht, eine Nachschlagetabelle zu erstellen (als privates statisches Array mit 64 booleschen Werten). Dann orwürde ich statt Schalter oder Anweisung einfach sagen if(lookup[(int)(n&0x3F)]) { test } else return false;. Zu meiner Überraschung war dies (nur geringfügig) langsamer. Dies liegt daran, dass Array-Grenzen in Java überprüft werden .

java math optimization perfect-square Kip
quelle

21

Dies ist Java-Code, wobei int == 32 Bit und long == 64 Bit und beide signiert sind.

Kip

14

@Shreevasta: Ich habe einige Tests mit großen Werten (größer als 2 ^ 53) durchgeführt, und Ihre Methode liefert einige falsch positive Ergebnisse. Das erste, das angetroffen wird, ist für n = 9007199326062755, was kein perfektes Quadrat ist, sondern als eins zurückgegeben wird.

Kip

37

Bitte nennen Sie es nicht den "John Carmack Hack". Er hat es sich nicht ausgedacht.

user9282

84

@ Mama - Vielleicht, aber es wird ihm zugeschrieben. Henry Ford hat das Auto nicht erfunden, die Wright Bros. haben das Flugzeug nicht erfunden, und Galleleo war nicht der erste, der herausgefunden hat, dass sich die Erde um die Sonne dreht ... die Welt besteht aus gestohlenen Erfindungen (und Liebe).

Robert Fraser

4

Sie könnten eine winzige Geschwindigkeitssteigerung im 'Quickfail' erzielen, wenn Sie so etwas verwenden ((1<<(n&15))|65004) != 0, anstatt drei separate Prüfungen durchzuführen .

Nabb

736

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

Mein Ansatz ist dreifach:

Filtern Sie zunächst offensichtliche Antworten heraus. Dies schließt negative Zahlen und das Betrachten der letzten 4 Bits ein. (Ich habe festgestellt, dass das Betrachten der letzten sechs nicht geholfen hat.) Ich antworte auch mit Ja für 0. (Beachten Sie beim Lesen des folgenden Codes, dass meine Eingabe lautet int64 x.)
```
if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) )
    return false;
if( x == 0 )
    return true;
```
Überprüfen Sie als nächstes, ob es sich um ein Quadrat Modulo 255 = 3 * 5 * 17 handelt. Da dies ein Produkt aus drei verschiedenen Primzahlen ist, sind nur etwa 1/8 der Reste Mod 255 Quadrate. Nach meiner Erfahrung kostet das Aufrufen des Modulo-Operators (%) jedoch mehr als der Nutzen, den man erhält. Daher verwende ich Bit-Tricks mit 255 = 2 ^ 8-1, um den Rest zu berechnen. (Zum Guten oder Schlechten verwende ich nicht den Trick, einzelne Bytes aus einem Wort zu lesen, sondern nur bitweise und und verschiebt sich.)
```
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 tatsächlich zu überprüfen, ob der Rest ein Quadrat ist, schlage ich die Antwort in einer vorberechneten Tabelle nach.
```
if( bad255[y] )
    return false;
// However, I just use a table of size 512
```
Versuchen Sie abschließend, die Quadratwurzel mit einer Methode zu berechnen, die Hensels Lemma ähnelt . (Ich denke nicht, dass es direkt anwendbar ist, aber es funktioniert mit einigen Modifikationen.) Bevor ich das mache, teile ich alle Zweierpotenzen mit einer binären Suche auf:
```
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;
```
Zu diesem Zeitpunkt muss unsere Zahl 1 Mod 8 sein, damit unsere Zahl ein Quadrat ist.
```
if((x & 7) != 1)
    return false;
```
Die Grundstruktur von Hensels Lemma ist die folgende. (Hinweis: ungetesteter Code; wenn er nicht funktioniert, versuchen Sie es mit 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 Sie bei jeder Iteration ein Bit zu r hinzufügen, der "aktuellen" Quadratwurzel von x; Jede Quadratwurzel ist genau modulo eine immer größere 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, dies auch -r ist. Dies gilt auch für Modulo-Zahlen, aber Vorsicht, Modulo einige Zahlen, Dinge können sogar mehr als 2 Quadratwurzeln haben, insbesondere schließt dies Potenzen von 2 ein. ) Da unsere tatsächliche Quadratwurzel kleiner als 2 ^ 32 ist, können wir an diesem Punkt tatsächlich nur überprüfen, ob r oder t / 2-r echte Quadratwurzeln sind. In meinem eigentlichen 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 erzielt: vorberechneter Startwert (entspricht ~ 10 Iterationen der Schleife), früheres Verlassen der Schleife und Überspringen einiger t-Werte. Für den letzten Teil schaue ich z = r - x * xund setze t mit einem kleinen Trick als die größte Potenz von 2, die z teilt. Dadurch kann ich t-Werte überspringen, die den Wert von r ohnehin nicht beeinflusst hätten. Der vorberechnete Startwert in meinem Fall wählt das "kleinste positive" Quadratwurzelmodulo 8192 aus.

Auch wenn dieser Code für Sie nicht schneller funktioniert, hoffe ich, dass Ihnen einige der darin enthaltenen Ideen gefallen. Es folgt ein vollständiger, getesteter 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;
}

A. Rex
quelle

5

Beeindruckend! Ich werde versuchen, dies in Java zu konvertieren und einen Vergleich sowie eine Genauigkeitsprüfung der Ergebnisse durchzuführen. Ich werde dich wissen lassen, was ich finde.

Kip

79

Wow, das ist wunderschön. Ich hatte Hensel schon einmal beim Heben gesehen (Berechnen der Wurzeln von Polynomen modulo a prime), aber ich hatte nicht einmal realisiert, dass das Lemma für die Berechnung der Quadratwurzeln von Zahlen sorgfältig abgesenkt werden konnte. das ist ... erhebend :)

ShreevatsaR

3

@nightcracker Das tut es nicht. 9 < 0 => false, 9&2 => 0, 9&7 == 5 => false, 9&11 == 8 => false.

Primo

53

Maartinus hat unten eine 2x schnellere (und viel kürzere) Lösung veröffentlicht , die etwas später nicht viel Liebe zu finden scheint.

Jason C

3

Es scheint, dass ein Großteil des Geschwindigkeitsvorteils in den verschiedenen Lösungen durch Herausfiltern der offensichtlichen Quadrate erzielt wird. Hat jemand die Situation bewertet, über die Maartinus-Lösung herauszufiltern und dann nur die sqrt-Funktion zu verwenden, da dies eine integrierte Funktion ist?

user1914292

377

Ich bin ziemlich spät zur Party, 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) {
    // 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;
}

Der erste Test fängt die meisten Nichtquadrate schnell ab. Es wird eine Tabelle mit 64 Elementen verwendet, die in einer langen Tabelle gepackt ist, sodass keine Kosten für den Arrayzugriff anfallen (Indirektion und Grenzüberprüfung). Für einen einheitlich zufälligen Zufall longbesteht eine Wahrscheinlichkeit von 81,25%, hier zu enden.

Der zweite Test erfasst alle Zahlen mit einer ungeraden Anzahl von Zweien in ihrer Faktorisierung. Die Methode Long.numberOfTrailingZerosist sehr schnell, da sie JIT-ed in einen einzelnen i86-Befehl umwandelt.

Nach dem Löschen der nachfolgenden Nullen behandelt der dritte Test Zahlen, die mit 011, 101 oder 111 in Binärform enden und keine perfekten Quadrate sind. Es kümmert sich auch um negative Zahlen und behandelt auch 0.

Der letzte Test fällt auf die doubleArithmetik zurück. Da doublenur 53-Bit-Mantisse vorhanden ist, umfasst die Konvertierung von longnach doubleeine Rundung für große Werte. Trotzdem ist der Test korrekt (es sei denn, der Beweis ist falsch).

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

Maaartinus
quelle

3

Diese implizite Maskierung des Verschiebungswerts ist ein bisschen ... böse. Haben Sie eine Idee, warum das in der Java-Spezifikation steht?

Feuer

6

@dfeuer Ich denke, es gibt zwei Gründe: 1. Um mehr zu verschieben macht keinen Sinn. 2. Es ist, als ob die HW funktioniert und jeder, der bitweise Operationen verwendet, an der Leistung interessiert ist. Alles andere wäre also falsch. - Der goodMaskTest macht es, aber er macht es vor der richtigen Schicht. Sie müssten es also wiederholen, aber auf diese Weise ist es einfacher und AFAIK ein kleines bisschen schneller und gleich gut.

Maaartinus

3

@dfeuer Für den Benchmark ist es wichtig, so schnell wie möglich eine Antwort zu geben, und die nachfolgende Nullzahl selbst gibt keine Antwort. Es ist nur ein vorbereitender Schritt. i86 / amd64 mach es. Keine Ahnung von den kleinen CPUs in Handys, aber im schlimmsten Fall muss Java einen UND-Befehl für sie generieren, was sicherlich einfacher ist als umgekehrt.

Maaartinus

2

@ Sebastian Ein wahrscheinlich besserer Test : if ((x & (7 | Integer.MIN_VALUE)) != 1) return x == 0;.

Maaartinus

4

"Da Double nur eine 56-Bit-Mantisse hat" -> Ich würde sagen, es hat eher eine 53-Bit- Mantisse . Also

chux

132

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

Ihr Algorithmus ist möglicherweise nahezu optimal, Sie sollten jedoch eine schnelle Überprüfung durchführen, um einige Möglichkeiten auszuschließen, bevor Sie Ihre Quadratwurzel-Routine aufrufen. Schauen Sie sich zum Beispiel die letzte Ziffer Ihrer Zahl in hexadezimaler Form an, indem Sie ein bisschen "und" eingeben. Perfekte Quadrate können nur mit 0, 1, 4 oder 9 in Basis 16 enden. Für 75% Ihrer Eingaben (vorausgesetzt, sie sind gleichmäßig verteilt) können Sie einen Aufruf der Quadratwurzel im Austausch für ein sehr schnelles Bit-Twiddling vermeiden.

Kip hat den folgenden Code mit dem Hex-Trick verglichen. Beim Testen der Nummern 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. Als ich jedoch die switch-Anweisung eliminierte, machte der Hex-Trick den Code erneut doppelt so schnell.

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

Das Eliminieren der switch-Anweisung hatte nur geringe Auswirkungen auf den C # -Code.

John D. Cook
quelle

das ist ziemlich klug ... hätte nicht daran gedacht

warren

Netter Punkt über die nachfolgenden Bits. Ich würde versuchen, diesen Test mit einigen anderen Bemerkungen hier zu kombinieren.

PeterAllenWebb

3

Hervorragende Lösung. Sie fragen sich, wie Sie darauf gekommen sind? Ist ein ziemlich etabliertes Prinzip oder nur etwas, das Sie herausgefunden haben? : D

Jeel Shah

3

@LarsH Es ist nicht erforderlich, 0,5 hinzuzufügen. In meiner Lösung finden Sie einen Link zum Beweis.

Maaartinus

2

@JerryGoyal Es hängt vom Compiler und den Werten der Fälle ab. In einem perfekten Compiler ist ein Switch immer mindestens so schnell wie if-else. Aber Compiler sind nicht perfekt, deshalb ist es am besten, sie auszuprobieren, wie es John getan hat.

fishinear

52

Ich dachte an die schrecklichen Zeiten, die ich im Kurs Numerische Analyse verbracht habe.

Und dann erinnere ich mich, dass diese Funktion aus dem Quake-Quellcode im Netz kreiste:

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

Was im Grunde genommen eine Quadratwurzel unter Verwendung der Newtonschen Approximationsfunktion berechnet (ich kann mich nicht an den genauen Namen erinnern).

Es sollte brauchbar sein und könnte sogar schneller sein, es stammt aus einem der phänomenalen ID-Software-Spiele!

Es ist in C ++ geschrieben, aber es sollte nicht zu schwierig sein, dieselbe Technik in Java wiederzuverwenden, sobald Sie die Idee haben:

Ich fand es ursprünglich unter: http://www.codemaestro.com/reviews/9

Newtons Methode wird auf Wikipedia erklärt: http://en.wikipedia.org/wiki/Newton%27s_method

Sie können dem Link folgen, um weitere Erklärungen zur Funktionsweise zu erhalten. Wenn Sie sich jedoch nicht viel darum kümmern, ist dies ungefähr das, woran ich mich beim Lesen des Blogs und beim Besuch des Kurses für numerische Analyse erinnere:

das * (long*) &y ist im Prinzip eine schnelle convert-to-Funktion so lange Ganzzahl - Operationen an den unformatierten Bytes angewendet werden kann.
Die 0x5f3759df - (i >> 1);Linie ist ein vorberechneter Startwert für die Approximationsfunktion.
das * (float*) &i konvertiert den Wert zurück in Gleitkomma.
Die y = y * ( threehalfs - ( x2 * y * y ) )Zeile iteriert den Wert erneut grundlegend über die Funktion.

Die Approximationsfunktion liefert genauere Werte, je mehr Sie die Funktion über das Ergebnis iterieren. In Quakes Fall ist eine Iteration "gut genug", aber wenn Sie nicht wären ... dann könnten Sie so viel Iteration hinzufügen, wie Sie benötigen.

Dies sollte schneller sein, da dadurch die Anzahl der Divisionsoperationen, die beim naiven Quadratwurzeln ausgeführt werden, auf eine einfache Division durch 2 reduziert wird (eigentlich eine * 0.5FMultiplikationsoperation) und stattdessen durch einige feste Multiplikationsoperationen ersetzt wird.

Chakrit
quelle

9

Es ist zu beachten, dass dies 1 / sqrt (Nummer) und nicht sqrt (Nummer) zurückgibt. Ich habe einige Tests durchgeführt, und dies schlägt ab n = 410881 fehl: Die John Carmack-Zauberformel gibt 642.00104 zurück, wenn die tatsächliche Quadratwurzel 641 ist.

Kip

11

Sie können sich Chris Lomonts Papier über schnelle inverse Quadratwurzeln ansehen : lomont.org/Math/Papers/2003/InvSqrt.pdf Es verwendet dieselbe Technik wie hier, jedoch mit einer anderen magischen Zahl. Das Papier erklärt, warum die magische Zahl gewählt wurde.

4

Auch beyond3d.com/content/articles/8 und beyond3d.com/content/articles/15 etwas Licht in Bezug auf die Ursprünge dieser Methode zu vergießen. Es wird oft John Carmack zugeschrieben, aber es scheint, dass der ursprüngliche Code (möglicherweise) von Gary Tarolli, Greg Walsh und wahrscheinlich anderen geschrieben wurde.

3

Außerdem können Sie Floats und Ints in Java nicht typepun.

Antimon

10

@ Antimon wer sagt? FloatToIntBits und IntToFloatBits gibt es seit Java 1.0.2.

CorsiKa

38

Ich bin mir nicht sicher, ob es schneller oder sogar genauer wäre, aber Sie könnten John Carmacks 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-Ganzzahlen testen und überprüfen, ob Sie tatsächlich korrekte Ergebnisse erhalten haben, da dies nur eine Annäherung ist. Jetzt, wo ich darüber nachdenke, ist die Verwendung von Doppel auch ungefähr, daher bin ich mir nicht sicher, wie das ins Spiel kommen würde.

Kibbee
quelle

10

Ich glaube, Carmacks Trick ist heutzutage ziemlich sinnlos. Die integrierte sqrt-Anweisung ist viel schneller als früher. Daher ist es möglicherweise besser, nur eine reguläre Quadratwurzel auszuführen und zu testen, ob das Ergebnis ein int ist. Wie immer Benchmarking.

Jalf

4

Dies bricht ab n = 410881, die Zauberformel von John Carmack gibt 642.00104 zurück, wenn die tatsächliche Quadratwurzel 641 ist.

Kip

11

Ich habe kürzlich Carmacks Trick in einem Java-Spiel verwendet und er war sehr effektiv und führte zu einer Beschleunigung von etwa 40%. Daher ist er zumindest in Java immer noch nützlich.

Finnw

3

@ Robert Fraser Ja + 40% in der Gesamtbildrate. Das Spiel hatte eine Teilchenphysik System , das nahezu alle verfügbaren CPU - Zyklen aufnahm, dominiert durch die Quadratwurzel - Funktion und der Rund-um-zu-nächst-Integer - Funktion (die ich auch ein ähnliches Bit twiddling Hack optimiert hatte verwenden.)

finnw

5

Die Verbindung ist unterbrochen.

Pixar

36

Wenn Sie einen binären Schnitt ausführen, um die "richtige" Quadratwurzel zu finden, können Sie ziemlich leicht feststellen, ob der Wert, den Sie haben, nahe genug ist, um Folgendes zu erkennen:

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

Nach der Berechnung n^2stehen folgende Optionen zur Verfügung:

n^2 = target: erledigt, return true
n^2 + 2n + 1 > target > n^2 : Sie sind nah dran, aber es ist nicht perfekt: Geben Sie false zurück
n^2 - 2n + 1 < target < n^2 : dito
target < n^2 - 2n + 1 : binärer Chop auf einem niedrigeren n
target > n^2 + 2n + 1 : binärer Chop auf einem höheren n

(Entschuldigung, dies wird nals Ihre aktuelle Vermutung und targetfür den Parameter verwendet. Entschuldigen Sie die Verwirrung!)

Ich weiß nicht, ob das schneller geht oder nicht, aber es ist einen Versuch wert.

BEARBEITEN: Der binäre Chop muss auch nicht den gesamten Bereich von ganzen Zahlen (2^x)^2 = 2^(2x)berücksichtigen. Wenn Sie also das oberste gesetzte Bit in Ihrem Ziel gefunden haben (was mit einem Trick gemacht werden kann; ich vergesse genau, wie) Sie können schnell eine Reihe möglicher Antworten erhalten. Wohlgemerkt, ein naiver binärer Chop dauert immer noch nur bis zu 31 oder 32 Iterationen.

Jon Skeet
quelle

Mein Geld ist für diese Art von Ansatz. Vermeiden Sie es, sqrt () aufzurufen, da es eine vollständige Quadratwurzel berechnet und Sie nur die ersten Ziffern benötigen.

PeterAllenWebb

3

Wenn der Gleitkomma-Wert jedoch in einer dedizierten FP-Einheit ausgeführt wird, werden möglicherweise alle Arten von unterhaltsamen Tricks verwendet. Ich würde nicht gerne ohne Benchmark darauf wetten :) (Ich kann es heute Abend in C # versuchen, nur um zu sehen ...)

Jon Skeet

8

Hardware-Skripte sind heutzutage eigentlich ziemlich schnell.

Adam Rosenfield

24

Ich habe meine eigene Analyse mehrerer Algorithmen in diesem Thread durchgeführt und einige neue Ergebnisse erzielt. Sie können diese alten Ergebnisse im Bearbeitungsverlauf dieser Antwort sehen, aber sie sind nicht korrekt, da ich einen Fehler gemacht habe und Zeit damit verschwendet habe, mehrere Algorithmen zu analysieren, die nicht in der Nähe sind. Da ich jedoch Lehren aus verschiedenen Antworten gezogen habe, habe ich jetzt zwei Algorithmen, die den "Gewinner" dieses Threads vernichten. Hier ist das Kernstück, das ich anders mache als alle anderen:

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

Diese einfache Zeile, die meistens ein oder zwei sehr schnelle Anweisungen hinzufügt, vereinfacht das jedoch erheblich switch-case Anweisung jedoch zu einer if-Anweisung. Es kann jedoch zur Laufzeit beitragen, wenn viele der getesteten Zahlen signifikante Zweierpotenzfaktoren aufweisen.

Die folgenden Algorithmen sind wie folgt:

Internet - Kips Antwort
Durron - Meine modifizierte Antwort unter Verwendung der One-Pass-Antwort als Basis
DurronTwo - Meine geänderte Antwort mit der Zwei-Pass-Antwort (von @JohnnyHeggheim), mit einigen anderen geringfügigen Änderungen.

Hier ist eine Beispiellaufzeit, wenn die Zahlen mit generiert werden 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

Und hier ist eine Beispiellaufzeit, wenn sie nur auf den ersten Millionen Longs ausgeführt wird:

 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

Wie Sie sehen können, DurronTwoeignet es sich besser für große Eingaben, da der Zaubertrick sehr oft verwendet wird, aber im Vergleich zum ersten Algorithmus überlastet wird und Math.sqrtdie Zahlen so viel kleiner sind. Inzwischen ist das einfacherDurron ein großer Gewinner, da er in den ersten Millionen Zahlen nie viele Male durch 4 dividieren muss.

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

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

Und mein Benchmark-Gurt: (Benötigt Google Caliper 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);
    }
}

UPDATE: Ich habe einen neuen Algorithmus entwickelt, der in einigen Szenarien schneller und in anderen langsamer ist. Ich habe unterschiedliche Benchmarks basierend auf unterschiedlichen Eingaben erhalten. Wenn wir Modulo berechnen 0xFFFFFF = 3 x 3 x 5 x 7 x 13 x 17 x 241, können wir 97,82% der Zahlen eliminieren, die keine Quadrate sein können. Dies kann (irgendwie) in einer Zeile mit 5 bitweisen Operationen erfolgen:

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

Der resultierende Index ist entweder 1) der Rückstand, 2) der Rückstand + 0xFFFFFFoder 3) der Rückstand + 0x1FFFFFE. Natürlich brauchen wir eine Nachschlagetabelle für Reste Modulo 0xFFFFFF, bei der es sich um eine 3-MB-Datei handelt (in diesem Fall als ASCII-Text-Dezimalzahlen gespeichert, nicht optimal, aber mit a ByteBufferund so weiter eindeutig verbesserbar . Aber da dies eine Vorberechnung ist, ist dies nicht der Fall.) Es ist nicht so wichtig. Sie können die Datei hier finden (oder selbst generieren):

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

Ich lade es in ein booleanArray wie folgt:

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

Beispiel Laufzeit. Es schlug Durron(Version eins) in jedem Versuch, den ich lief.

 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

durron597
quelle

3

Eine riesige Nachschlagetabelle scheint keine gute Idee zu sein. Ein Cache-Fehler ist langsamer (~ 100 bis 150 Zyklen) als der x86-Hardware-SQL-Befehl (~ 20 Zyklen). In Bezug auf den Durchsatz können Sie viele ausstehende Cache-Fehler aushalten, aber Sie entfernen immer noch andere nützliche Daten. Eine riesige Nachschlagetabelle wäre es nur wert, wenn sie viel schneller wäre als jede andere Option, und diese Funktion war der Hauptfaktor für die Leistung Ihres gesamten Programms.

Peter Cordes

1

@ SwissFrank: Ist Perfect-Square-Checking das einzige, was Ihr Programm macht? Eine Nachschlagetabelle kann in einem Mikrobenchmark gut aussehen, das sie wiederholt in einer engen Schleife aufruft, aber in einem echten Programm, das andere Daten in seinem Arbeitssatz enthält, ist es nicht gut.

Peter Cordes

1

Eine Bitmap von 0x1FFFFFE Bits dauert 4 Mega- Bytes , wenn als gepackte Bitmap gespeichert. Ein L3-Cache- Treffer auf einem modernen Intel-Desktop hat> 40 Latenzzyklen und auf einem großen Xeon noch schlimmer. länger als Hardware-SQL + Mul-Latenz. Wenn es als Byte- Map mit 1 Byte pro Wert gespeichert wird, sind es ungefähr 32 MB. Größer als der L3-Cache von etwas anderem als einem Xeon mit vielen Kernen, bei dem sich alle Kerne einen riesigen Cache teilen. Wenn Ihre Eingabedaten also eine gleichmäßige Zufallsverteilung über einen ausreichend großen Bereich von Eingaben aufweisen, treten selbst in einer engen Schleife viele L2-Cache-Fehler auf. (Private Per-Core-L2 auf Intel ist nur 256k, mit ~ 12 Zyklus Latenz.)

Peter Cordes

1

@ SwissFrank: Oh, wenn du nur Root-Checking machst, dann gibt es das Potenzial mit einer Bitmap, um L3-Treffer zu bekommen. Ich habe mir die Latenz angesehen, aber viele Fehler können gleichzeitig im Flug sein, sodass der Durchsatz möglicherweise gut ist. OTOH, SIMD- sqrtpsDurchsatz oder sogar sqrtpd(doppelte Genauigkeit) sind bei Skylake nicht schlecht, aber nicht viel besser als die Latenz bei alten CPUs. Wie auch immer, 7-cpu.com/cpu/Haswell.html hat einige nette experimentelle Zahlen und Seiten für andere CPUs. Agner Fogs Microarch

Peter Cordes

1

Die Verwendung von x86 SIMD aus Java ist ein Problem, und wenn Sie die Kosten für die Konvertierung von int-> fp und fp-> int hinzufügen, ist es plausibel, dass eine Bitmap besser sein könnte. Sie benötigen doublePräzision, um zu vermeiden, dass eine Ganzzahl außerhalb des Bereichs + -2 ^ 24 gerundet wird (eine 32-Bit-Ganzzahl kann also außerhalb dieses Bereichs liegen). Sie sqrtpdist langsamer als sqrtpsund verarbeitet nur halb so viele Elemente pro Befehl (pro SIMD-Vektor). .

Peter Cordes

18

Es sollte viel schneller sein, die Newtonsche Methode zur Berechnung der ganzzahligen Quadratwurzel zu verwenden, diese Zahl dann zu quadrieren und zu überprüfen, wie Sie es in Ihrer aktuellen Lösung tun. Die Newtonsche Methode ist die Grundlage für die in einigen anderen Antworten erwähnte Carmack-Lösung. Sie sollten in der Lage sein, eine schnellere Antwort zu erhalten, da Sie nur an dem ganzzahligen Teil der Wurzel interessiert sind, sodass Sie den Approximationsalgorithmus früher stoppen können.

Eine weitere Optimierung, die Sie ausprobieren können: Wenn die digitale Wurzel einer Zahl nicht mit 1, 4, 7 oder 9 endet, ist die Zahl kein perfektes Quadrat. Dies kann als schnelle Methode verwendet werden, um 60% Ihrer Eingaben zu eliminieren, bevor der langsamere Quadratwurzel-Algorithmus angewendet wird.

Bill die Eidechse
quelle

1

Die digitale Wurzel ist streng rechnerisch äquivalent zu Modulo und sollte daher zusammen mit anderen Modulo-Methoden wie Mod 16 und Mod 255

berücksichtigt werden.

1

Sind Sie sicher, dass die digitale Wurzel Modulo entspricht? Es scheint etwas ganz anderes zu sein, wie durch den Link erklärt. Beachten Sie, dass die Liste 1,4,7,9 und nicht 1,4,5,9 ist.

Fractaly

1

Die digitale Wurzel im Dezimalsystem entspricht der Verwendung von Modulo 9 (gut dr (n) = 1 + ((n-1) mod 9); also auch eine leichte Verschiebung). Die Zahlen 0,1,4,5,9 gelten für Modulo 16 und 0, 1, 4, 7 für Modulo 9 - entsprechend 1, 4, 7, 9 für Digital Root.

Hans Olsson

16

Ich möchte, dass diese Funktion mit allen positiven 64-Bit-Ganzzahlen mit Vorzeichen funktioniert

Math.sqrt()funktioniert mit doppelten Eingabeparametern, sodass Sie für Ganzzahlen größer als 2 ^ 53 keine genauen Ergebnisse erhalten .

mrzl
quelle

5

Ich habe die Antwort tatsächlich auf allen perfekten Quadraten getestet, die größer als 2 ^ 53 sind, sowie auf allen Zahlen von 5 unter jedem perfekten Quadrat bis 5 über jedem perfekten Quadrat, und ich erhalte das richtige Ergebnis. (Der Rundungsfehler wird korrigiert, wenn ich die sqrt-Antwort auf eine lange runde, dann diesen Wert quadriere und vergleiche)

Kip

2

@ Kip: Ich denke, ich habe bewiesen, dass es funktioniert .

Maaartinus

Die Ergebnisse sind nicht genau, aber genauer als Sie vielleicht denken. Wenn wir nach der Konvertierung in double und nach der Quadratwurzel mindestens 15 genaue Ziffern annehmen, ist das ausreichend, da wir für die 32-Bit-Quadratwurzel nicht mehr als 11: 10 Ziffern und für eine Dezimalstelle weniger als 1 benötigen, weil die +0,5 Runden zum nächsten.

mwfearnley

3

Math.sqrt () ist nicht ganz genau, muss es aber nicht. Im allerersten Beitrag ist tst eine ganze Zahl in der Nähe von sqrt (N). Wenn N kein Quadrat ist, dann ist tst * tst! = N, egal wie der Wert von tst ist. Wenn N ein perfektes Quadrat ist, dann ist sqrt (N) <2 ^ 32, und solange sqrt (N) mit einem Fehler <0,5 berechnet wird, sind wir in Ordnung.

gnasher729

13

Ein anderer Ansatz besteht darin, die Hauptzerlegung zu verwenden. Wenn jeder Faktor der Zerlegung gerade ist, ist die Zahl ein perfektes Quadrat. Sie möchten also sehen, ob eine Zahl als Produkt aus Quadraten von Primzahlen zerlegt werden kann. Natürlich müssen Sie eine solche Zerlegung nicht erhalten, nur um zu sehen, ob sie existiert.

Erstellen Sie zuerst eine Tabelle mit Quadraten von Primzahlen, die niedriger als 2 ^ 32 sind. Dies ist weitaus kleiner als eine Tabelle aller Ganzzahlen bis zu dieser Grenze.

Eine Lösung wäre dann:

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

Ich denke, es ist ein bisschen kryptisch. In jedem Schritt wird überprüft, ob das Quadrat einer Primzahl die eingegebene Zahl teilt. Wenn dies der Fall ist, wird die Zahl so lange wie möglich durch das Quadrat geteilt, um dieses Quadrat aus der Hauptzerlegung zu entfernen. Wenn wir durch diesen Prozess zu 1 kamen, war die eingegebene Zahl eine Zerlegung des Quadrats der Primzahlen. Wenn das Quadrat größer als die Zahl selbst wird, kann dieses Quadrat oder größere Quadrate es auf keinen Fall teilen, sodass die Zahl keine Zerlegung von Quadraten von Primzahlen sein kann.

Angesichts der heutigen Hardware und der Notwendigkeit, hier Primzahlen zu berechnen, ist diese Lösung wahrscheinlich viel langsamer. Aber es sollte bessere Ergebnisse liefern als eine Lösung mit sqrt, die über 2 ^ 54 nicht funktioniert, wie mrzl in seiner Antwort sagt.

Cyrille Ka
quelle

1

Die Ganzzahldivision ist auf der aktuellen Hardware langsamer als FP sqrt. Diese Idee hat keine Chance. >. <Selbst im Jahr 2008 beträgt der sqrtsdDurchsatz von Core2 eins pro 6-58c. Es idivist eins pro 12-36 Zyklen. (Latenzen ähnlich wie Durchsätze: Keine Einheit ist über eine Pipeline verbunden).

Peter Cordes

sqrt muss nicht genau sein. Aus diesem Grund überprüfen Sie das Ergebnis, indem Sie das Ergebnis ganzzahlig quadrieren und einen Ganzzahlvergleich durchführen, um zu entscheiden, ob die Eingabe-Ganzzahl ein genaues Ganzzahl-Quadrat hat.

Peter Cordes

11

Es wurde darauf hingewiesen, dass die letzten dZiffern eines perfekten Quadrats nur bestimmte Werte annehmen können. Die letzten dZiffern (in der Basis b) einer Zahl nsind die gleichen wie der Rest, wenn sie ndurch geteilt werden b^d, d. H. in C-Notation n % pow(b, d).

Dies kann auf jeden Modul verallgemeinert werden m, dh. n % mkann verwendet werden, um einen bestimmten Prozentsatz von Zahlen als perfekte Quadrate auszuschließen. Der Modul, den Sie derzeit verwenden, ist 64, was 12 erlaubt, dh. 19% der Reste als mögliche Quadrate. Mit ein wenig Codierung fand ich den Modul 110880, der nur 2016 erlaubt, dh. 1,8% der verbleibenden Quadrate. Abhängig von den Kosten einer Moduloperation (dh Division) und einer Tabellensuche im Vergleich zu einer Quadratwurzel auf Ihrem Computer ist die Verwendung dieses Moduls möglicherweise schneller.

Übrigens, wenn Java eine Möglichkeit hat, ein gepacktes Array von Bits für die Nachschlagetabelle zu speichern, verwenden Sie es nicht. 110880 32-Bit-Wörter sind heutzutage nicht viel RAM und das Abrufen eines Maschinenworts ist schneller als das Abrufen eines einzelnen Bits.

Hugh Allen
quelle

Nett. Haben Sie das algebraisch oder durch Ausprobieren herausgefunden? Ich kann sehen, warum es so effektiv ist - viele Kollisionen zwischen perfekten Quadraten, z. B. 333 ^ 2% 110880 == 3 ^ 2, 334 ^ 2% 110880 == 26 ^ 2, 338 ^ 2% 110880 == 58 ^ 2 .. .

Finnw

IIRC war es rohe Gewalt, aber beachten Sie, dass 110880 = 2 ^ 5 * 3 ^ 2 * 5 * 7 * 11, was 6 * 3 * 2 * 2 * 2 - 1 = 143 richtige Teiler ergibt.

Hugh Allen

Ich fand heraus, dass 44352 aufgrund der Einschränkungen der Suche mit einer Erfolgsquote von 2,6% besser funktioniert. Zumindest in meiner Implementierung.

Fractaly

1

Die idivKosten für Integer Division ( ) sind sqrtsdauf der aktuellen x86-Hardware gleich oder schlechter als bei FP sqrt ( ). Nicht einverstanden mit der Vermeidung von Bitfeldern. Die Cache-Trefferquote ist mit einem Bitfeld um ein Vielfaches besser, und das Testen eines Bits in einem Bitfeld ist nur ein oder zwei einfachere Anweisungen als das Testen eines ganzen Bytes. (Für winzige Tabellen, die auch als Nicht-Bitfelder in den Cache passen, ist ein Byte-Array am besten geeignet, nicht 32-Bit-Ints. X86 verfügt über einen Einzelbyte-Zugriff mit der gleichen Geschwindigkeit wie 32-Bit-Wörter.)

Peter Cordes

11

Ein ganzzahliges Problem verdient eine ganzzahlige Lösung. Somit

Führen Sie eine binäre Suche nach den (nicht negativen) Ganzzahlen durch, um die größte Ganzzahl t so zu finden, dass t**2 <= n. Dann testen Sie ob r**2 = ngenau. Dies dauert einige Zeit O (log n).

Wenn Sie nicht wissen, wie man die positiven ganzen Zahlen binär durchsucht, weil die Menge unbegrenzt ist, ist es einfach. Sie beginnen mit der Berechnung Ihrer zunehmenden Funktion f (oben f(t) = t**2 - n) auf Zweierpotenzen. Wenn Sie sehen, dass es positiv wird, haben Sie eine Obergrenze gefunden. Dann können Sie eine standardmäßige binäre Suche durchführen.

Colonel Panic
quelle

Tatsächlich wäre die Zeit zumindest deshalb so, O((log n)^2)weil die Multiplikation nicht zeitkonstant ist, sondern tatsächlich eine Untergrenze von hat O(log n), was bei der Arbeit mit großen Zahlen mit mehrfacher Genauigkeit deutlich wird. Aber der Umfang dieses Wikis scheint 64-Bit zu sein, also ist es vielleicht nbd.

10

Die folgende Vereinfachung der Lösung von maaartinus scheint die Laufzeit um einige Prozentpunkte zu verkürzen, aber ich bin nicht gut genug im Benchmarking, um einen Benchmark zu erstellen, dem ich vertrauen kann:

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

Es lohnt sich zu prüfen, wie der erste Test weggelassen wird.

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

würde die Leistung beeinträchtigen.

dfeuer
quelle

2

Die Ergebnisse sind hier . Das Entfernen des ersten Tests ist schlecht, da es die meisten Fälle ziemlich billig löst. Die Quelle ist in meiner Antwort (aktualisiert).

Maaartinus

9

Für die Leistung müssen Sie sehr oft einige Komprimierungen durchführen. Andere haben verschiedene Methoden ausgedrückt. Sie haben jedoch festgestellt, dass Carmacks Hack bis zu bestimmten Werten von N schneller war. Dann sollten Sie das "n" überprüfen. Wenn es kleiner als diese Zahl N ist, verwenden Sie Carmacks Hack, andernfalls verwenden Sie eine andere beschriebene Methode in den Antworten hier.

BobbyShaftoe
quelle

Ich habe Ihren Vorschlag auch in die Lösung aufgenommen. Auch schöner Griff. :)

Kip

8

Dies ist die schnellste Java-Implementierung, die ich mit einer Kombination von Techniken entwickeln konnte, die von anderen in diesem Thread vorgeschlagen wurden.

Mod-256 Test
Ungenauer Mod-3465-Test (vermeidet die Ganzzahldivision auf Kosten einiger falsch positiver Ergebnisse)
Gleitkomma-Quadratwurzel, runden und mit dem Eingabewert vergleichen

Ich habe auch mit diesen Modifikationen experimentiert, aber sie haben die Leistung nicht verbessert:

Zusätzlicher Mod-255-Test
Teilen des Eingabewerts durch Potenzen von 4
Schnelle inverse Quadratwurzel (um für hohe Werte von N zu arbeiten, sind 3 Iterationen erforderlich, genug, um sie langsamer als die Hardware-Quadratwurzelfunktion zu machen.)

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

}

finnw
quelle

7

Sie sollten den 2-Potenz-Teil von N von Anfang an loswerden.

2. Bearbeiten Der magische Ausdruck für m unten sollte sein

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

und nicht wie geschrieben

Ende der 2. Bearbeitung

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

1. Bearbeitung:

Kleinere Verbesserung:

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

Ende der 1. Bearbeitung

Fahren Sie nun wie gewohnt fort. Auf diese Weise haben Sie zu dem Zeitpunkt, an dem Sie zum Gleitkomma-Teil gelangen, bereits alle Zahlen entfernt, deren 2-Potenz-Teil ungerade ist (ungefähr die Hälfte), und dann berücksichtigen Sie nur noch 1/8 von dem, was übrig ist. Dh Sie führen den Gleitkommateil auf 6% der Zahlen aus.

David Lehavi
quelle

7

Project Euler wird in den Tags erwähnt und viele der darin enthaltenen Probleme erfordern die Überprüfung von Nummern >> 2^64. Die meisten der oben genannten Optimierungen funktionieren nicht einfach, wenn Sie mit einem 80-Byte-Puffer arbeiten.

Ich habe Java BigInteger und eine leicht modifizierte Version von Newtons Methode verwendet, die besser mit ganzen Zahlen funktioniert. Das Problem war, dass exakte Quadrate n^2konvergierten(n-1) statt zu nweiln^2-1 = (n-1)(n+1) und der endgültige Fehler nur einen Schritt unter dem endgültigen Teiler lag und der Algorithmus beendet wurde. Es war einfach zu beheben, indem man dem ursprünglichen Argument eins hinzufügte, bevor der Fehler berechnet wurde. (Fügen Sie zwei für Kubikwurzeln usw. hinzu.)

Ein schönes Attribut dieses Algorithmus ist, dass Sie sofort erkennen können, ob die Zahl ein perfektes Quadrat ist - der endgültige Fehler (keine Korrektur) in Newtons Methode ist Null. Mit einer einfachen Änderung können Sie auch schnell floor(sqrt(x))anstelle der nächsten Ganzzahl berechnen . Dies ist praktisch bei mehreren Euler-Problemen.

bgiles
quelle

1

Ich dachte das Gleiche über diese Algorithmen, die sich nicht gut in Puffer mit Mehrfachgenauigkeit übersetzen lassen. Also dachte ich, ich würde das hier festhalten ... Ich habe tatsächlich einen probabilistischen Quadraturtest mit besserer asymptotischer Komplexität für große Zahlen gefunden ... wo sich Anwendungen der Zahlentheorie nicht selten befinden. Nicht vertraut mit Project Euler ... sieht interessant aus.

6

Dies ist eine Überarbeitung des alten Marchant-Rechner-Algorithmus (sorry, ich habe keine Referenz) von dezimal nach binär in Ruby, die speziell für diese Frage angepasst wurde:

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

Hier ist eine Aufarbeitung von etwas Ähnlichem (bitte stimmen Sie mich nicht für Codierungsstil / Gerüche oder klobiges O / O ab - es ist der Algorithmus, der zählt, und C ++ ist nicht meine Muttersprache). In diesem Fall suchen wir nach Rest == 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;
};

Brent.Longborough
quelle

Die Anzahl der Iterationen sieht nach O (ln n) aus, wobei n die Bitlänge von v ist. Ich bezweifle, dass dies viel für größere v spart. Gleitkomma-Quadrat ist langsam, vielleicht 100-200 Zyklen, aber ganzzahlige Mathematik nicht kostenlos auch. Ein Dutzend Iterationen mit jeweils 15 Zyklen, und es wäre eine Wäsche. Trotzdem +1 für interessant zu sein.

Tadmas

Eigentlich glaube ich, dass die Additionen und Subtraktionen von XOR durchgeführt werden können.

Brent.Longborough

Das war ein dummer Kommentar - nur die Hinzufügung kann von einem XOR vorgenommen werden; Die Subtraktion ist arithmetisch.

Brent.Longborough

1

Gibt es überhaupt einen wesentlichen Unterschied zwischen der Laufzeit von XOR und der Addition?

Tadmas

1

@Tadmas: wahrscheinlich nicht genug, um die Regel "Später optimieren" zu brechen. (:-)

Brent.Longborough

6

Der sqrt-Aufruf ist, wie bereits erwähnt, nicht genau, aber es ist interessant und lehrreich, dass er die anderen Antworten in Bezug auf die Geschwindigkeit nicht wegbläst. Immerhin ist die Reihenfolge der Assembler-Anweisungen für ein sqrt winzig. Intel hat eine Hardware-Anweisung, die meines Erachtens nicht von Java verwendet wird, da sie nicht mit IEEE übereinstimmt.

Warum ist es langsam? Weil Java tatsächlich eine C-Routine über JNI aufruft und dies tatsächlich langsamer ist als das Aufrufen einer Java-Subroutine, die selbst langsamer ist als die Inline-Routine. Dies ist sehr ärgerlich, und Java hätte eine bessere Lösung finden sollen, dh bei Bedarf Gleitkomma-Bibliotheksaufrufe einzubauen. Naja.

Ich vermute, dass in C ++ alle komplexen Alternativen an Geschwindigkeit verlieren würden, aber ich habe sie nicht alle überprüft. Was ich getan habe und was Java-Leute nützlich finden werden, ist ein einfacher Hack, eine Erweiterung der von A. Rex vorgeschlagenen Sonderfalltests. Verwenden Sie einen einzelnen langen Wert als Bit-Array, dessen Grenzen nicht überprüft werden. Auf diese Weise haben Sie eine 64-Bit-Boolesche Suche.

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

Die Routine isPerfectSquare5 läuft auf meinem Core2-Duo-Computer in etwa 1/3 der Zeit. Ich vermute, dass weitere Optimierungen in der gleichen Richtung die Zeit im Durchschnitt weiter verkürzen könnten, aber jedes Mal, wenn Sie dies überprüfen, tauschen Sie mehr Tests gegen mehr Eliminierung aus, sodass Sie auf dieser Straße nicht zu weit gehen können.

Anstatt einen separaten Test auf Negativ durchzuführen, können Sie die hohen 6 Bits auf die gleiche Weise überprüfen.

Beachten Sie, dass ich nur mögliche Quadrate eliminiere, aber wenn ich einen potenziellen Fall habe, muss ich das ursprüngliche, inline eingefügte isPerfectSquare aufrufen.

Die Routine init2 wird einmal aufgerufen, um die statischen Werte von pp1 und pp2 zu initialisieren. Beachten Sie, dass ich in meiner Implementierung in C ++ Long Long ohne Vorzeichen verwende. Da Sie also signiert sind, müssen Sie den Operator >>> verwenden.

Es ist nicht unbedingt erforderlich, das Array zu überprüfen, aber Javas Optimierer muss dies ziemlich schnell herausfinden, deshalb beschuldige ich sie nicht dafür.

Hydrodog
quelle

3

Ich wette, du liegst zweimal falsch. 1. Intel sqrt entspricht IEEE. Die einzigen nicht konformen Anweisungen sind die goniometrischen Anweisungen für lange Argumente. 2. Java verwendet Intrinsics für Math.sqrt, kein JNI .

Maaartinus

1

Hast du nicht vergessen zu benutzen pp2? Ich verstehe, dass dies pp1zum Testen der sechs niedrigstwertigen Bits verwendet wird, aber ich glaube nicht, dass das Testen der nächsten sechs Bits Sinn macht.

Maaartinus

6

Ich mag die Idee, bei einigen Eingaben eine fast korrekte Methode zu verwenden. Hier ist eine Version mit einem höheren "Offset". Der Code scheint zu funktionieren und besteht meinen einfachen Testfall.

Ersetzen Sie einfach Ihre:

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

Code mit diesem:

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

Jonny Heggheim
quelle

6

In Anbetracht der allgemeinen Bitlänge (obwohl ich hier einen bestimmten Typ verwendet habe) habe ich versucht, ein vereinfachtes Algo wie folgt zu entwerfen. Zunächst ist eine einfache und offensichtliche Prüfung auf 0,1,2 oder <0 erforderlich. Das Folgende ist in dem Sinne einfach, dass es nicht versucht, vorhandene mathematische Funktionen zu verwenden. Die meisten Operatoren können durch bitweise Operatoren ersetzt werden. Ich habe jedoch keine Benchmark-Daten getestet. Ich bin weder Experte für Mathematik noch für das Design von Computeralgorithmen. Ich würde mich freuen, wenn Sie auf ein Problem hinweisen. Ich weiß, dass es dort viele Verbesserungschancen gibt.

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

Nabam Serbang
quelle

@Kip: Ein Problem mit meinem Browser.

Nabam Serbang

1

Sie brauchen ein Einrücken.

Steve Kuo

5

Ich habe alle möglichen Ergebnisse überprüft, wenn die letzten n Bits eines Quadrats beobachtet werden. Durch sukzessives Untersuchen von mehr Bits können bis zu 5/6 der Eingänge eliminiert werden. Ich habe dies tatsächlich entworfen, um den Faktorisierungsalgorithmus von Fermat zu implementieren, und es ist dort sehr schnell.

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

Das letzte Bit des Pseudocodes kann verwendet werden, um die Tests zu erweitern und mehr Werte zu eliminieren. Die obigen Tests gelten für k = 0, 1, 2, 3

a hat die Form (3 << 2k) - 1

b hat die Form (2 << 2k)

c hat die Form (2 << 2k + 2) - 1

d hat die Form (2 << 2k - 1) * 10

Es testet zuerst, ob es einen quadratischen Rest mit einem Potenzmodul von zwei hat, dann testet es basierend auf einem Endmodul und verwendet dann Math.sqrt, um einen Endtest durchzuführen. Ich kam auf die Idee vom obersten Beitrag und versuchte, sie zu erweitern. Ich freue mich über Kommentare oder Vorschläge.

Update: Unter Verwendung des Tests mit einem Modul (modSq) und einer Modulbasis von 44352 läuft mein Test in 96% der Zeit des Tests im OP-Update für Zahlen bis zu 1.000.000.000.

Fractaly
quelle

2

Hier ist eine Lösung zum Teilen und Erobern.

Wenn die Quadratwurzel einer natürlichen Zahl ( number) eine natürliche Zahl ( solution) ist, können Sie einen Bereich für solutionbasierend auf der Anzahl der Ziffern von number:

numberhat 1 Stelle: solutionim Bereich = 1 - 4
numberhat 2 Ziffern: solutionim Bereich = 3 - 10
numberhat 3 Ziffern: solutionim Bereich = 10 - 40
numberhat 4 Ziffern: solutionim Bereich = 30 - 100
numberhat 5 Ziffern: solutionim Bereich = 100 - 400

Beachten Sie die Wiederholung?

Sie können diesen Bereich in einem binären Suchansatz verwenden, um festzustellen, ob es einen gibt, solutionfür den:

number == solution * solution

Hier ist der Code

Hier ist meine Klasse 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;
    }

}

Und hier ist ein Beispiel, wie man es benutzt.

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"

MWB
quelle

2

Ich liebe das Konzept, möchte aber höflich auf einen großen Fehler hinweisen: Zahlen sind in der Basis 2 binär. Das Konvertieren von Basis 2 in Basis 10 über toStringist im Vergleich zu bitweisen Operatoren eine unglaublich teure Operation. Um das Ziel der Frage - Leistung - zu erfüllen, müssen Sie daher bitweise Operatoren anstelle von Zeichenfolgen der Basis 10 verwenden. Auch hier gefällt mir Ihr Konzept sehr gut. Ungeachtet dessen ist Ihre Implementierung (wie sie jetzt ist) bei weitem die langsamste aller möglichen Lösungen, die für die Frage veröffentlicht wurden.

Jack Giffin

1

Wenn es um Geschwindigkeit geht, können Sie die am häufigsten verwendeten Eingaben und ihre Werte in eine Nachschlagetabelle aufteilen und dann den optimierten magischen Algorithmus ausführen, den Sie für die Ausnahmefälle entwickelt haben.

Elijah
quelle

Das Problem ist, dass es keinen "häufig verwendeten Satz von Eingaben" gibt - normalerweise durchlaufe ich eine Liste, sodass ich nicht zweimal dieselben Eingaben verwende.

Kip

1

Es sollte möglich sein, das 'kann kein perfektes Quadrat sein, wenn die letzten X-Ziffern N sind' viel effizienter zu packen! Ich werde Java 32-Bit-Ints verwenden und genügend Daten erzeugen, um die letzten 16 Bits der Zahl zu überprüfen - das sind 2048 hexadezimale Int-Werte.

...

OK. Entweder bin ich auf eine Zahlentheorie gestoßen, die ein wenig über mich hinausgeht, oder es gibt einen Fehler in meinem Code. In jedem Fall ist hier der Code:

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

und hier sind die Ergebnisse:

(ed: elided für schlechte Leistung in prettify.js; Revisionsverlauf anzeigen, um zu sehen.)

Paulmurray
quelle

1

Newtonsche Methode mit ganzzahliger Arithmetik

Wenn Sie nicht ganzzahlige Operationen vermeiden möchten, können Sie die folgende Methode verwenden. Grundsätzlich wird die für die Ganzzahlarithmetik modifizierte Newtonsche Methode verwendet.

/**
 * Test if the given number is a perfect square.
 * @param n Must be greater than 0 and less
 *    than Long.MAX_VALUE.
 * @return <code>true</code> if n is a perfect
 *    square, or <code>false</code> otherwise.
 */
public static boolean isSquare(long n)
{
    long x1 = n;
    long x2 = 1L;

    while (x1 > x2)
    {
        x1 = (x1 + x2) / 2L;
        x2 = n / x1;
    }

    return x1 == x2 && n % x1 == 0L;
}

Diese Implementierung kann nicht mit verwendeten Lösungen konkurrieren Math.sqrt. Die Leistung kann jedoch durch Verwendung der in einigen anderen Beiträgen beschriebenen Filtermechanismen verbessert werden.

Aventurin
quelle

1

Die Berechnung der Quadratwurzeln nach Newtons Methode ist entsetzlich schnell ... vorausgesetzt, der Startwert ist angemessen. Es gibt jedoch keinen vernünftigen Startwert, und in der Praxis enden wir mit Halbierungs- und Protokollverhalten (2 ^ 64).
Um wirklich schnell zu sein, brauchen wir einen schnellen Weg, um zu einem vernünftigen Startwert zu gelangen, und das bedeutet, dass wir in die Maschinensprache absteigen müssen. Wenn ein Prozessor im Pentium einen Befehl wie POPCNT bereitstellt, der die führenden Nullen zählt, können wir diesen verwenden, um einen Startwert mit der Hälfte der signifikanten Bits zu erhalten. Mit Sorgfalt können wir eine feste Anzahl von Newton-Schritten finden, die immer ausreichen wird. (Somit entfällt die Notwendigkeit einer Schleife und einer sehr schnellen Ausführung.)

Eine zweite Lösung ist die Gleitkommafunktion, die eine schnelle SQL-Berechnung haben kann (wie der i87-Coprozessor). Selbst eine Exkursion über exp () und log () kann schneller sein als Newton, der zu einer binären Suche entartet ist. Dies hat einen kniffligen Aspekt: Eine prozessorabhängige Analyse dessen, was und ob eine weitere Verfeinerung erforderlich ist.

Eine dritte Lösung löst ein etwas anderes Problem, ist jedoch erwähnenswert, da die Situation in der Frage beschrieben wird. Wenn Sie sehr viele Quadratwurzeln für Zahlen berechnen möchten, die sich geringfügig unterscheiden, können Sie die Newton-Iteration verwenden, wenn Sie den Startwert nie neu initialisieren, sondern ihn einfach dort belassen, wo die vorherige Berechnung aufgehört hat. Ich habe dies mit Erfolg in mindestens einem Euler-Problem verwendet.

Albert van der Horst
quelle

Eine gute Schätzung zu bekommen ist nicht allzu schwer. Sie können die Anzahl der Ziffern der Zahl verwenden, um eine Unter- und Obergrenze für die Lösung zu schätzen. Siehe auch meine Antwort, in der ich eine Divide and Conquer-Lösung vorschlage.

MWB

Was ist der Unterschied zwischen POPCNT und dem Zählen der Ziffern? Nur dass Sie POPCNT in einer Nanosekunde durchführen können.

Albert van der Horst

1

Quadratwurzel einer Zahl, vorausgesetzt, die Zahl ist ein perfektes Quadrat.

Die Komplexität ist log (n)

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

public static int calculateSquareRoot(int number) {

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

Sajjad Ali Vayani
quelle

0

Wenn Sie Geschwindigkeit wünschen, da Ihre Ganzzahlen eine endliche Größe haben, besteht der schnellste Weg vermutlich darin, (a) die Parameter nach Größe zu partitionieren (z. B. nach größter Bitmenge in Kategorien) und dann den Wert anhand eines Arrays perfekter Quadrate zu überprüfen innerhalb dieses Bereichs.

Celestial M Weasel
quelle

2

Es gibt 2 ^ 32 perfekte Quadrate im Bereich eines langen. Dieser Tisch wäre riesig. Der Vorteil der Berechnung des Werts gegenüber einem Speicherzugriff kann ebenfalls enorm sein.

PeterAllenWebb

Oh nein gibt es nicht, es gibt 2 ^ 16. 2 ^ 32 ist 2 ^ 16 im Quadrat. Es gibt 2 ^ 16.

Celestial M Weasel

3

Ja, aber der Bereich eines Longs beträgt 64 Bit, nicht 32 Bit. sqrt (2 ^ 64) = 2 ^ 32. (Ich ignoriere das Vorzeichenbit, um die Mathematik ein wenig einfacher zu machen ... es gibt tatsächlich (lange) (2 ^ 31,5) = 3037000499 perfekte Quadrate)

Kip

0

In Bezug auf die Carmac-Methode scheint es ziemlich einfach zu sein, nur noch einmal zu iterieren, was die Anzahl der Genauigkeitsstellen verdoppeln sollte. Es ist immerhin eine extrem verkürzte iterative Methode - Newtons, mit einer sehr guten ersten Vermutung.

In Bezug auf Ihr aktuelles Bestes sehe ich zwei Mikrooptimierungen:

Verschiebe den Scheck gegen 0 nach dem Scheck mit mod255
Ordnen Sie die Teilungskräfte von vier neu an, um alle Überprüfungen für den üblichen Fall (75%) zu überspringen.

Dh:

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

Noch besser könnte ein einfacher sein

while ((n & 0x03L) == 0) n >>= 2;

Natürlich wäre es interessant zu wissen, wie viele Zahlen an jedem Kontrollpunkt ausgesondert werden - ich bezweifle eher, dass die Kontrollen wirklich unabhängig sind, was die Sache schwierig macht.

Ben
quelle

Der schnellste Weg, um festzustellen, ob die Quadratwurzel einer Ganzzahl eine Ganzzahl ist

Antworten:

Newtonsche Methode mit ganzzahliger Arithmetik