Frage Der schnellste Weg, um festzustellen, ob die Wurzel einer ganzen Zahl eine ganze Zahl ist


Ich bin auf der Suche nach dem schnellsten Weg, um festzustellen, ob long Wert ist ein perfektes Quadrat (d. h. seine Quadratwurzel ist eine andere ganze Zahl):

  1. Ich habe es einfach gemacht, indem ich die eingebaute Math.sqrt () benutzt habe Funktion, aber ich frage mich, ob es einen Weg gibt, es schneller zu machen Beschränken Sie sich auf Integer-Only-Domäne.
  2. Die Pflege einer Nachschlagetabelle ist unpraktisch (da es etwa 231.5 Ganzzahlen, deren Quadrat kleiner als 2 ist63).

Hier ist die sehr einfache und direkte 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;
}

Hinweise: Ich verwende diese Funktion in vielen Projekt Euler Probleme. Also wird niemand sonst diesen Code beibehalten 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 durchzuführen, und diese Funktion muss bei einigen Problemen millionenfach aufgerufen werden.


Eine neue Lösung von A. Rex hat sich als noch schneller erwiesen. Bei einem Durchlauf über die ersten 1 Milliarde Ganzzahlen benötigte die Lösung nur 34% der Zeit, die die ursprüngliche Lösung verwendete. Während der John Carmack Hack ein wenig besser ist für kleine Werte von nDer Vorteil gegenüber dieser Lösung ist ziemlich klein.

Hier ist die A. Rex-Lösung, die in Java konvertiert wurde:

private final static boolean isPerfectSquare(long n)
{
  // Quickfail
  if( n < 0 || ((n&2) != 0) || ((n & 7) == 5) || ((n & 11) == 8) )
    return false;
  if( n == 0 )
    return true;

  // Check mod 255 = 3 * 5 * 17, for fun
  long y = n;
  y = (y & 0xffffffffL) + (y >> 32);
  y = (y & 0xffffL) + (y >> 16);
  y = (y & 0xffL) + ((y >> 8) & 0xffL) + (y >> 16);
  if( bad255[(int)y] )
      return false;

  // Divide out powers of 4 using binary search
  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;

  if((n & 0x7L) != 1)
      return false;

  // Compute sqrt using something like Hensel's lemma
  long r, t, z;
  r = start[(int)((n >> 3) & 0x3ffL)];
  do {
    z = n - 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 <= (1L << 33) );
  return false;
}

private static boolean[] bad255 =
{
   false,false,true ,true ,false,true ,true ,true ,true ,false,true ,true ,true ,
   true ,true ,false,false,true ,true ,false,true ,false,true ,true ,true ,false,
   true ,true ,true ,true ,false,true ,true ,true ,false,true ,false,true ,true ,
   true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,false,true ,false,
   true ,true ,true ,false,true ,true ,true ,true ,false,true ,true ,true ,false,
   true ,false,true ,true ,false,false,true ,true ,true ,true ,true ,false,true ,
   true ,true ,true ,false,true ,true ,false,false,true ,true ,true ,true ,true ,
   true ,true ,true ,false,true ,true ,true ,true ,true ,false,true ,true ,true ,
   true ,true ,false,true ,true ,true ,true ,false,true ,true ,true ,false,true ,
   true ,true ,true ,false,false,true ,true ,true ,true ,true ,true ,true ,true ,
   true ,true ,true ,true ,true ,false,false,true ,true ,true ,true ,true ,true ,
   true ,false,false,true ,true ,true ,true ,true ,false,true ,true ,false,true ,
   true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,false,true ,true ,
   false,true ,false,true ,true ,false,true ,true ,true ,true ,true ,true ,true ,
   true ,true ,true ,true ,false,true ,true ,false,true ,true ,true ,true ,true ,
   false,false,true ,true ,true ,true ,true ,true ,true ,false,false,true ,true ,
   true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,false,false,
   true ,true ,true ,true ,false,true ,true ,true ,false,true ,true ,true ,true ,
   false,true ,true ,true ,true ,true ,false,true ,true ,true ,true ,true ,false,
   true ,true ,true ,true ,true ,true ,true ,true ,false,false,true ,true ,false,
   true ,true ,true ,true ,false,true ,true ,true ,true ,true ,false,false,true ,
   true ,false,true ,false,true ,true ,true ,false,true ,true ,true ,true ,false,
   true ,true ,true ,false,true ,false,true ,true ,true ,true ,true ,true ,true ,
   true ,true ,true ,true ,true ,false,true ,false,true ,true ,true ,false,true ,
   true ,true ,true ,false,true ,true ,true ,false,true ,false,true ,true ,false,
   false,true ,true ,true ,true ,true ,false,true ,true ,true ,true ,false,true ,
   true ,false,false,true ,true ,true ,true ,true ,true ,true ,true ,false,true ,
   true ,true ,true ,true ,false,true ,true ,true ,true ,true ,false,true ,true ,
   true ,true ,false,true ,true ,true ,false,true ,true ,true ,true ,false,false,
   true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,
   false,false,true ,true ,true ,true ,true ,true ,true ,false,false,true ,true ,
   true ,true ,true ,false,true ,true ,false,true ,true ,true ,true ,true ,true ,
   true ,true ,true ,true ,true ,false,true ,true ,false,true ,false,true ,true ,
   false,true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,false,
   true ,true ,false,true ,true ,true ,true ,true ,false,false,true ,true ,true ,
   true ,true ,true ,true ,false,false,true ,true ,true ,true ,true ,true ,true ,
   true ,true ,true ,true ,true ,true ,false,false,true ,true ,true ,true ,false,
   true ,true ,true ,false,true ,true ,true ,true ,false,true ,true ,true ,true ,
   true ,false,true ,true ,true ,true ,true ,false,true ,true ,true ,true ,true ,
   true ,true ,true ,false,false
};

private static int[] start =
{
  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
};

Ich habe die verschiedenen unten aufgeführten Lösungen ausprobiert.

  • Nach erschöpfenden Tests fand ich das Hinzufügen 0.5 auf das Ergebnis von Math.sqrt () ist nicht notwendig, zumindest nicht auf meinem Rechner.
  • Das John Carmack Hack war schneller, aber es gab falsche Ergebnisse ab n = 410881. Wie jedoch von. Vorgeschlagen Bobby Shaftoekönnen wir den Carmack-Hack für n <410881 verwenden.
  • Newtons Methode war ein gutes Stück langsamer als Math.sqrt(). Das liegt wahrscheinlich daran Math.sqrt() verwendet etwas, das der Newton-Methode ähnelt, aber in der Hardware implementiert ist, so ist es viel schneller als in Java. Auch Newtons Methode erforderte immer noch die Verwendung von Doppelpunkten.
  • Eine modifizierte Newton-Methode, die einige Tricks verwendete, so dass nur Integer-Mathe 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 das binäre Chop im Durchschnitt 16 Durchläufe benötigt, um die Quadratwurzel einer 64-Bit-Zahl zu finden.

Der eine Vorschlag, der Verbesserungen zeigte, wurde von John D. Cook. Sie können beobachten, dass die letzte hexadezimale Ziffer (d. H. Die letzten 4 Bits) eines perfekten Quadrats 0, 1, 4 oder 9 sein muss. Dies bedeutet, dass 75% der Zahlen sofort als mögliche Quadrate eliminiert werden können. Die Implementierung dieser Lösung führte zu einer Reduzierung der Laufzeit um etwa 50%.

Ausgehend von Johns Vorschlag untersuchte ich Eigenschaften des Letzten n Bits eines perfekten Quadrats. Durch Analyse der letzten 6 Bits habe ich festgestellt, dass nur 12 von 64 Werten für die letzten 6 Bits möglich sind. Dies bedeutet, dass 81% der Werte eliminiert werden können, ohne irgendeine Mathematik zu verwenden. Durch die Implementierung dieser Lösung wurde die Laufzeit um weitere 8% reduziert (im Vergleich zu meinem ursprünglichen Algorithmus). Das Analysieren von mehr als 6 Bits führt zu einer Liste möglicher Endbits, die zu groß ist, um praktisch zu sein.

Hier ist der Code, den ich verwendet habe, der in 42% der Zeit läuft, die vom ursprünglichen Algorithmus benötigt wird (basierend auf einem Durchlauf über die ersten 100 Millionen ganzen Zahlen). Für Werte von n weniger als 410881, läuft es in nur 29% der Zeit, die vom ursprünglichen Algorithmus benötigt wird.

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

  switch((int)(n & 0x3F))
  {
  case 0x00: case 0x01: case 0x04: case 0x09: case 0x10: case 0x11:
  case 0x19: case 0x21: case 0x24: case 0x29: case 0x31: case 0x39:
    long sqrt;
    if(n < 410881L)
    {
      //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);
      i  = 0x5f3759df - ( i >> 1 );
      y  = Float.intBitsToFloat(i);
      y  = y * ( 1.5F - ( x2 * y * y ) );

      sqrt = (long)(1.0F/y);
    }
    else
    {
      //Carmack hack gives incorrect answer for n >= 410881.
      sqrt = (long)Math.sqrt(n);
    }
    return sqrt*sqrt == n;

  default:
    return false;
  }
}

Anmerkungen:

  • Laut Johns Tests, mit or Anweisungen sind in C ++ schneller als mit a switch, aber in Java und C # scheint es keinen Unterschied zu geben or und switch.
  • Ich habe auch versucht, eine Nachschlagetabelle zu erstellen (als privates statisches Array mit 64 booleschen Werten). Dann anstatt entweder oder or Aussage würde ich nur sagen if(lookup[(int)(n&0x3F)]) { test } else return false;. Zu meiner Überraschung war dies (nur geringfügig) langsamer. Ich bin mir nicht sicher warum.  Das ist weil Array-Grenzen werden in Java überprüft.

1209


Ursprung


Antworten:


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

Mein Ansatz ist dreifach:

  1. Erstens, offensichtliche Antworten herausfiltern. Dies schließt negative Zahlen ein und betrachtet die letzten 4 Bits. (Ich fand, dass das Betrachten der letzten sechs nicht geholfen hat.) Ich antworte auch mit Ja für 0. (Wenn ich den Code unten lese, beachte, dass meine Eingabe ist int64 x.)
    if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) )
        return false;
    if( x == 0 )
        return true;
  2. Als nächstes prüfe, ob es ein Quadrat modulo 255 = 3 * 5 * 17 ist. Weil das ein Produkt von drei verschiedenen Primzahlen ist, sind nur etwa 1/8 der Reste mod 255 Quadrate. Meiner Erfahrung nach kostet der Aufruf des Modulo-Operators (%) mehr als der Nutzen, den man bekommt, also verwende ich Bit-Tricks, die 255 = 2 ^ 8-1 beinhalten, um den Rest zu berechnen. (Zum besseren oder schlechteren, verwende ich nicht den Trick, einzelne Bytes aus einem Wort zu lesen, nur bitweise - und verschiebt.)
    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.
    

602



Ich bin ziemlich spät zur Party, aber ich hoffe, eine bessere Antwort zu geben; kürzer und (angenommen meine Benchmark ist richtig) 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 Nicht-Quadrate schnell auf. Es verwendet eine 64-Item-Tabelle, die lange gepackt ist, so dass es keine Kosten für den Array-Zugriff gibt (Indirection- und Grenzen-Checks). Für eine gleichmäßig zufällige longgibt es 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.numberOfTrailingZeros ist sehr schnell, da es in eine einzige i86-Anweisung JIT-ed wird.

Nach dem Ablegen der abschließenden Nullen behandelt der dritte Test Zahlen, die mit 011, 101 oder 111 enden, binär, die keine perfekten Quadrate sind. Es kümmert sich auch um negative Zahlen und behandelt auch 0.

Der letzte Test fällt zurück auf double Arithmetik. Wie double hat nur 53 Bit Mantisse, die Umwandlung von long zu double schließt das Runden für große Werte ein. Trotzdem ist der Test korrekt (außer der Beweis ist falsch).

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


260



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

Ihr Algorithmus ist möglicherweise fast optimal, aber Sie sollten eine schnelle Überprüfung durchführen, um einige Möglichkeiten auszuschließen, bevor Sie Ihre Routine für die Quadratwurzel aufrufen. Schau dir zum Beispiel die letzte Ziffer deiner Zahl im Hex an, indem du ein bisschen "und" machst. Perfekte Quadrate können nur in 0, 1, 4 oder 9 in der 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-Twiddeln vermeiden.

Kip benchmarkte den folgenden Code, der den Hexentrick implementiert. Beim Testen der Zahlen 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 noch einmal 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 Entfernen der switch-Anweisung hatte wenig Auswirkung auf den C # -Code.


118



Ich dachte über die schrecklichen Zeiten nach, die ich in der Numerischen Analysis verbracht habe.

Und dann erinnere ich mich, da war diese Funktion um das Netz aus dem Quake Source Code:

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

Das berechnet im Grunde eine Quadratwurzel, mit Newtons Näherungsfunktion (kann mich nicht an den genauen Namen erinnern).

Es sollte benutzbar sein und könnte sogar schneller sein, es ist von einem der phänomenalen ID-Software-Spiel!

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

Ich habe es ursprünglich gefunden bei: http://www.codemaestro.com/reviews/9

Newtons Methode erklärt in 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 Sie sich nicht viel interessieren, dann ist das ungefähr, woran ich mich erinnere, wenn ich den Blog lese und den Numerical Analysis Kurs nehme:

  • das * (long*) &y ist im Grunde eine schnelle Convert-zu-Long-Funktion, so dass ganzzahlige Operationen auf die rohen Bytes angewendet werden können.
  • das 0x5f3759df - (i >> 1); line ist ein vorberechneter Startwert für die Approximationsfunktion.
  • das * (float*) &i wandelt den Wert zurück in Gleitkommazahl.
  • das y = y * ( threehalfs - ( x2 * y * y ) ) line iteriert den Wert über die Funktion erneut.

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

Dies sollte schneller sein, da es die Anzahl der Divisionsoperationen verringert, die bei der naiven Quadratwurzelung auf eine einfache Division durch 2 reduziert werden (tatsächlich a * 0.5F Operation multiplizieren) und ersetzen Sie sie stattdessen durch einige feste Multiplikationsoperationen.


41



Ich bin mir nicht sicher, ob es schneller oder sogar genau wäre, aber Sie könnten es benutzen John Carmacks magische Quadratwurzel, Algorithmus, um die Quadratwurzel schneller zu lösen. Sie könnten dies wahrscheinlich problemlos für alle möglichen 32-Bit-Ganzzahlen testen und bestätigen, dass Sie tatsächlich korrekte Ergebnisse erhalten haben, da es nur eine Angemessenheit ist. Aber jetzt, wo ich darüber nachdenke, nähert sich auch die Verwendung von Doubles, also bin ich mir nicht sicher, wie das ins Spiel kommen würde.


33



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

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

Also berechnet n^2, die Optionen sind:

  • n^2 = target: fertig, wahr zurück
  • n^2 + 2n + 1 > target > n^2 : du bist nah dran, aber es ist nicht perfekt: gib false zurück
  • n^2 - 2n + 1 < target < n^2 : Dito
  • target < n^2 - 2n + 1 : Binary Chop auf einem niedrigeren n
  • target > n^2 + 2n + 1 : Binary Chop auf einem höheren n

(Tut mir leid, das verwendet n wie deine derzeitige Vermutung und target für den Parameter. Entschuldige dich für die Verwirrung!)

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

EDIT: Der binäre Chop muss auch nicht den ganzen Bereich von ganzen Zahlen aufnehmen (2^x)^2 = 2^(2x)Wenn du also das Top-Set-Bit in deinem Ziel gefunden hast (was mit einem bisschen Twiddling-Trick getan werden kann, ich vergesse genau, wie), kannst du schnell eine Reihe von möglichen Antworten erhalten. Wohlgemerkt, ein naives Binär-Chop wird immer noch nur 31 oder 32 Iterationen benötigen.


30



Ich habe meine eigene Analyse einiger Algorithmen in diesem Thread durchgeführt und einige neue Ergebnisse gefunden. Sie können diese alten Ergebnisse im Bearbeitungsverlauf dieser Antwort sehen, aber sie sind nicht korrekt, da ich einen Fehler gemacht habe und Zeit verschwendet habe, um mehrere Algorithmen zu analysieren, die nicht in der Nähe sind. Allerdings habe ich jetzt zwei Algorithmen, die den "Gewinner" dieses Threads zerquetschen. 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 eine oder zwei sehr schnelle Anweisungen hinzufügt, vereinfacht jedoch die switch-case Anweisung in eine if-Anweisung. Es kann jedoch zur Laufzeit beitragen, wenn viele der getesteten Zahlen signifikante Zweierpotenz haben.

Die folgenden Algorithmen sind wie folgt:

  • Internet - Kip's Antwort
  • Durron - Meine modifizierte Antwort mit der One-Pass-Antwort als Basis
  • Durronzwei - Meine modifizierte Antwort mit der 2-Pass-Antwort (von @JohnnyHeggheim), mit einigen anderen leichten Modifikationen.

Hier ist eine Beispiellaufzeit, wenn die Nummern 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 der ersten Million läuft:

 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 du siehst, DurronTwo eignet sich besser für große Eingaben, weil es sehr oft den Zaubertrick verwendet, aber im Vergleich zum ersten Algorithmus und clobbered wird Math.sqrt weil die Zahlen so viel kleiner sind. Inzwischen ist das einfacher Durron ist ein riesiger Gewinner, weil er nie viele Male in der ersten Million Zahlen durch 4 teilen 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-Gurtzeug: (Erfordert 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);
    }
}

AKTUALISIEREN: Ich habe einen neuen Algorithmus entwickelt, der in einigen Szenarien schneller ist, in anderen langsamer. Ich habe verschiedene Benchmarks basierend auf verschiedenen Eingaben erhalten. Wenn wir modulo berechnen 0xFFFFFF = 3 x 3 x 5 x 7 x 13 x 17 x 241können wir 97,82% der Zahlen eliminieren, die keine Quadrate sein können. Dies kann (in einer Art) 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 Rest, 2) der Rest + 0xFFFFFFoder 3) der Rückstand + 0x1FFFFFE. Natürlich brauchen wir eine Nachschlagetabelle für Reste modulo 0xFFFFFF, das ist eine 3mb Datei (in diesem Fall als ASCII Text Dezimalzahlen gespeichert, nicht optimal, aber deutlich verbesserungsfähig mit a ByteBuffer und so weiter. Aber da dies eine Vorausberechnung ist, ist es nicht so wichtig. Sie können die Datei hier finden (oder erzeuge es selbst):

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

Beispiellaufzeit Es hat geschlagen Durron (Version eins) in jedem Versuch lief ich.

 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

21



Es sollte viel schneller zu benutzen sein Newtons Methode um zu berechnen Ganze Quadratwurzel, dann quadriere diese Zahl und überprüfe, wie du es in deiner aktuellen Lösung tust. Newtons 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, so dass Sie den Approximationsalgorithmus früher stoppen können.

Eine weitere Optimierung, die Sie ausprobieren können: Wenn die Digitale Wurzel einer Zahl endet nicht in 1, 4, 7 oder 9 ist die Nummer nicht ein perfektes Quadrat. Dies kann als eine schnelle Möglichkeit verwendet werden, 60% Ihrer Eingaben zu eliminieren, bevor der langsamere Quadratwurzelalgorithmus angewendet wird.


14



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

Math.sqrt() arbeitet mit Doppelpunkten als Eingabeparameter, so dass Sie keine genauen Ergebnisse für Ganzzahlen erhalten, die größer sind als 2 ^ 53.


12



Nur zur Erinnerung, ein anderer Ansatz besteht darin, die Primäre Dekomposition zu verwenden. Wenn jeder Faktor der Zerlegung gerade ist, dann ist die Zahl ein perfektes Quadrat. Was Sie also wollen, ist zu sehen, ob eine Zahl als ein Produkt von Quadraten von Primzahlen zerlegt werden kann. Natürlich müssen Sie eine solche Dekomposition nicht erhalten, nur um zu sehen, ob sie existiert.

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

Eine Lösung wäre dann so:

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 wenig kryptisch. Es überprüft in jedem Schritt, ob das Quadrat einer Primzahl die eingegebene Zahl teilt. Wenn dies der Fall ist, teilt es die Zahl so lange wie möglich durch das Quadrat, um dieses Quadrat aus der Hauptzerlegung zu entfernen. Wenn wir mit diesem Verfahren zu 1 kamen, dann war die Eingangszahl eine Zerlegung von Primzahlen. Wenn das Quadrat größer als die Zahl selbst wird, gibt es keine Möglichkeit, dieses Quadrat oder irgendwelche größeren Quadrate zu teilen, also kann die Zahl keine Zerlegung von Quadraten von Primzahlen sein.

Angesichts der Tatsache, dass heutzutage Hardware in der Hardware ausgeführt wird und Primzahlen hier berechnet werden müssen, denke ich, dass diese Lösung viel langsamer ist. Aber es sollte bessere Ergebnisse als Lösung mit sqrt geben, die über 2 ^ 54 nicht arbeiten wird, wie mrzl in seiner Antwort sagt.


11