Schnellste Weg, um zu bestimmen, ob ein Quadratwurzel der ganzen Zahl eine ganze Zahl ist
https://stackoverflow.com/questions/295579
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich bin für die schnellste Weg, um zu bestimmen, ob ein long Wert ein perfektes Quadrat ist (das heißt seine Quadratwurzel ist eine andere ganze Zahl ist):
- Ich habe es den einfachen Weg gemacht, durch das eingebaute in
Math.sqrt()mit Funktion, aber ich frage mich, ob es einen Weg gibt, es zu tun schneller durch Beschränken Sie sich Domäne nicht nur Integer-. - eine Lookup-Tabelle zu erhalten ist unpraktisch (seit etwa gibt es 2 31.5 ganze Zahlen, deren Quadrat kleiner als 2 63 ).
Hier ist die sehr einfache und unkomplizierte Art, wie ich es jetzt tue:
public final static boolean isPerfectSquare(long n)
{
if (n < 0)
return false;
long tst = (long)(Math.sqrt(n) + 0.5);
return tst*tst == n;
}
Hinweis: Ich verwende diese Funktion in vielen Projekt Euler Probleme. So sonst niemand wird jemals diesen Code zu halten haben. Und diese Art von Mikro-Optimierung könnte tatsächlich einen Unterschied machen, da ein Teil der Herausforderung jeden Algorithmus, der in weniger als einer Minute zu tun ist, und diese Funktion müssen millionenfach in einigen Problemen aufgerufen werden.
Ich habe versucht, die verschiedenen Lösungen für das Problem:
- Nach ausgiebigen Tests, fand ich, dass das Hinzufügen
0.5das Ergebnis der Math.sqrt () nicht erforderlich ist, zumindest nicht auf meinem Rechner. - Die schnelle inverse Quadratwurzel war schneller, aber es gab falsche Ergebnisse für n> = 410881 Allerdings., vorgeschlagen, wie durch BobbyShaftoe , können wir die FISR hack für n <410.881 verwenden.
- Newton-Verfahren war ein gutes Stück langsamer als
Math.sqrt(). Dies ist wahrscheinlich, weilMath.sqrt()etwas ähnliches wie Newton-Verfahren verwendet, aber in der Hardware implementiert, so ist es viel schneller als in Java. Auch Newton-Verfahren noch die Verwendung von Doppel erforderlich. - Ein modifizierte Newton-Verfahren, das ein paar Tricks verwendet, so dass nur ganzzahlige Mathematik beteiligt war, erforderlich, um einige Hacks Überlauf zu vermeiden (ich diese Funktion will mit allen positiven 64-Bit-Integer mit Vorzeichen arbeiten), und es war immer noch langsamer als
Math.sqrt(). - Binary Chop war noch langsamer. Dies macht Sinn, da die binären hacken wird durchschnittlich 16 Pässe benötigen die Quadratwurzel aus einer 64-Bit-Zahl zu finden.
- Nach Johns Tests
or-Anweisungen ist schneller in C ++ als einswitchverwenden, aber in Java und C # scheint es kein Unterschied zwischenorundswitchzu sein. - Ich habe auch versucht, eine Lookup-Tabelle zu machen (als privates statisches Array von 64 Boolesche Werte). Dann, anstatt entweder Schalter oder
orAussage, würde ich nurif(lookup[(int)(n&0x3F)]) { test } else return false;sagen. Zu meiner Überraschung war dies (nur leicht) langsamer. Dies liegt daran, Array-Grenzen werden in Java geprüft.
Lösung
Ich dachte, ein Verfahren aus, die ~ 35% schneller als Ihr 6bits + Carmack + sqrt Code funktioniert, zumindest mit meiner CPU (x86) und Programmiersprache (C / C ++). Ihre Ergebnisse können variieren, vor allem, weil ich weiß nicht, wie der Java-Faktor abspielen wird.
Mein Ansatz ist dreifach:
- Zuerst herauszufiltern offensichtliche Antworten. Dazu gehören negative Zahlen und Blick auf die letzten 4 Bits. (Ich fand Blick auf die letzten sechs half nicht.) Ich auch ja beantworten für 0. (In den nachfolgenden Code zu lesen, beachten Sie, dass meine Eingabe
int64 xist.)if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) ) return false; if( x == 0 ) return true; - Als nächstes prüfen, ob es ein Quadrat modulo 255 = 3 * 5 * 17. Denn, dass ein Produkt von drei verschiedenen Primzahlen ist, nur etwa 1/8 der Reste mod 255 Quadrate sind. Doch meiner Erfahrung, kostet den Modulo-Operator (%) ruft mehr als der Nutzen bekommt man, so verwende ich Bit Tricks 255 = 2 ^ 8-1 Einbeziehung der Rest zu berechnen. (Für besser oder schlechter, ich bin nicht mit dem Trick des Lesens einzelnen Bytes aus einem Wort, nur bitweise und und Verschiebungen.)
Um tatsächlich zu prüfen, ob der Rest ein Quadrat ist, sehe ich die Antwort in einem vorberechneten Tisch.int64 y = x; y = (y & 4294967295LL) + (y >> 32); y = (y & 65535) + (y >> 16); y = (y & 255) + ((y >> 8) & 255) + (y >> 16); // At this point, y is between 0 and 511. More code can reduce it farther.if( bad255[y] ) return false; // However, I just use a table of size 512 - Schließlich versuchen die Quadratwurzel unter Verwendung eines Verfahrens ähnlich zu berechnen href="http://en.wikipedia.org/wiki/Hensel%27s_lemma" rel="noreferrer"> Hensel Lemma
if((x & 4294967295LL) == 0) x >>= 32; if((x & 65535) == 0) x >>= 16; if((x & 255) == 0) x >>= 8; if((x & 15) == 0) x >>= 4; if((x & 3) == 0) x >>= 2;An diesem Punkt für unsere Nummer einen Platz zu sein, muss es 1 mod 8 sein.
Die Grundstruktur des Hensel Lemma ist die folgende. (Anmerkung: nicht getesteten Code, wenn es nicht funktioniert, versuchen t = 2 oder 8)if((x & 7) != 1) return false;
Die Idee ist, bei jeder Iteration, dass man ein Bit auf r, die „aktuelle“ Quadratwurzel von x hinzuzufügen; jede Quadratwurzel korrekt eine größere und größere Potenz von 2 modulo, nämlich / 2 t ist. Am Ende, r und t / 2-r werden Quadratwurzeln von x modulo t / 2. (Beachten Sie, dass, wenn r eine Quadratwurzel von x ist, dann so -r Dies gilt auch Modulo-Zahlen ist, aber Vorsicht, Modulo einiger Zahlen, können die Dinge noch mehr als 2 Quadratwurzeln;. Insbesondere umfasst diese Potenzen von 2. an diesem Punkt) Da unsere tatsächliche Quadratwurzel weniger als 2 ^ 32 ist, können wir überprüfen, eigentlich nur, wenn r oder t / 2-r echte Quadratwurzeln sind. In meinem eigentlichen Code verwende ich die folgende modifizierte Schleife: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 Beschleunigungs hier auf drei Arten erreicht: vorberechneten Startwert (äquivalent zu ~ 10 Iterationen der Schleife), frühe Ausgang der Schleife, und einigen T-Wert übersprungen wird. Für den letzten Teil, sehe ichint64 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) );z = r - x * xund setzen t die größte Potenz von 2 sein Dividieren z mit etwas Trick. Dies ermöglicht es mir t-Werte zu überspringen, die nicht den Wert von r ohnehin betroffen hätten. Die vorberechneten Startwert in meinem Fall nimmt sich die „kleinste positive“ Quadratwurzel Modulo 8192.
Auch wenn dieser Code nicht schneller für Sie arbeiten, ich hoffe, dass Sie einige der Ideen, genießen es enthält. Complete, getesteten Code folgt, 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;
}Andere Tipps
Ich bin ziemlich spät zur Party, aber ich hoffe, eine bessere Antwort zu geben; und kürzer (vorausgesetzt, meine 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;
}
Die ersten Testfänge die meisten Nicht-Quadrate schnell. Es verwendet eine 64-Punkt-Tabelle in einem langen verpackt, so dass es keine Array-Zugriffskosten (indirection begrenze Kontrollen). Für einen gleichmäßig zufälligen long, gibt es eine 81,25% ige Wahrscheinlichkeit, hier zu beenden.
Der zweite Test fängt alle Zahlen eine ungerade Anzahl von Zweien in ihre Faktorisierung mit. Das Verfahren Long.numberOfTrailingZeros ist sehr schnell, wie es JIT-ed in einen einzigen i86 Befehl bekommt.
Nachdem die nachgestellten Nullen Zutropfen der dritte Test verarbeitet Nummern mit 011, 101 enden, oder 111 in binären, die keine perfekten Quadrate sind. Es kümmert sich auch um negative Zahlen und übernimmt auch 0.
Der letzte Test fällt zurück Arithmetik double. Als double nur 53 Bit Mantisse hat,
Die Umstellung von long zu double umfasst für große Werte gerundet wird. Dennoch ist der Test korrekt ist (es sei denn, die Beweis ist falsch).
Der Versuch, die mod255 Idee war nicht erfolgreich zu integrieren.
Du musst etwas tun Benchmarking. Der beste Algorithmus wird auf die Verteilung Ihrer Eingaben ab.
Ihr Algorithmus kann nahezu optimal sein, aber Sie könnten einige Möglichkeiten eine schnelle Überprüfung, um auszuschließen, vor dem Aufruf Ihre Quadratwurzel Routine tun mögen. Zum Beispiel sehen Sie die letzte Ziffer Ihrer Nummer in hex durch eine bitweise tun „und.“ Perfekte Quadrate können nur am Ende in 0, 1, 4 oder 9 in der Basis 16, also für 75% Ihrer Eingaben (vorausgesetzt, sie gleichmäßig verteilt sind) Sie einen Anruf mit der Quadratwurzel im Austausch für einige sehr schnell bisschen Fummel vermeiden.
Kip gebenchmarkt den folgenden Code zur Durchführung des Hex-Trick. Wenn die Nummern 1 bis 100 Millionen Testen dieser Code doppelt so schnell wie das Original lief.
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;
}
}
Wenn ich den analogen Code in C ++ getestet, es lief eigentlich langsamer als das Original. Allerdings, wenn ich die Switch-Anweisung eliminiert, sobald der Hex-Trick wieder den Code machen 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;
}
Die Beseitigung der switch-Anweisung nur geringe Auswirkungen auf den C # -Code hatte.
Ich dachte über die schrecklichen Zeiten, die ich in Numerical Analysis Kurs ausgegeben haben.
Und dann erinnere ich mich, da war diese Funktion um das ‚Netz aus dem Quake Quellcode kreisen:
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;
}
, die im Grunde eine Quadratwurzel berechnet, unter Verwendung von Newtons Näherungsfunktion (kann nicht den genauen Namen erinnern).
Es nutzbar sein sollte und könnte sogar noch schneller sein, es ist von einem des phänomenalen id-Software-Spiel!
Es ist in C ++ geschrieben, aber es soll nicht zu schwer sein, die gleiche Technik in Java erneut zu verwenden, wenn Sie auf die Idee:
Ich fand es ursprünglich unter: http://www.codemaestro.com/reviews/9
Newton-Verfahren erklärt bei wikipedia: http://en.wikipedia.org/wiki/Newton% 27s_method
Sie können den Link für weitere Erklärung folgen, wie es funktioniert, aber wenn man nicht viel kümmern, dann ist das in etwa, was mich beim Lesen des Blog erinnern und von dem numerischen Analysis Kurs unter:
- die
* (long*) &yist im Grunde ein schnelle umwandeln zu lange Funktion so Integer-Operationen auf dem rohen Bytes angewandt werden können. - die
0x5f3759df - (i >> 1);Linie ist ein vorausberechnete Startwert für die Approximationsfunktion. - wandelt die
* (float*) &iden Wert wieder auf Gleitkomma-. - die
y = y * ( threehalfs - ( x2 * y * y ) )Linie iteriert bascially den Wert über die Funktion wieder.
Die Näherungsfunktion gibt genauere Werte je mehr Sie die Funktion über das Ergebnis iterieren. In Quake Fall ist eine Iteration „gut genug“, aber wenn es nicht für Sie ... dann könnte man so viel Iteration hinzufügen, wie Sie benötigen.
Dies sollte schneller sein, weil es die Zahl der Divisionsoperationen durchgeführt in naivem Quadrat reduziert auf eine einfache divide Verwurzelung um 2 (eigentlich eine * 0.5F Multiplikationsoperation) und ersetzen Sie es mit einem paar festen Anzahl von Multiplikationsoperationen statt.
Ich bin mir nicht sicher, ob es schneller sein würde, oder sogar genau, aber man konnte a href verwenden <= "https://web.archive.org/web/20081106174735/http://www.codemaestro.com / Bewertungen / 9" rel = "nofollow noreferrer"> Magische Quadratwurzel John Carmack, Algorithmus, um die Quadratwurzel schneller zu lösen. Sie könnten wahrscheinlich dies leicht testen für alle möglichen 32-Bit-Integer, und bestätigen Sie, dass Sie korrekte Ergebnisse tatsächlich bekam, da es nur ein appoximation ist. Aber jetzt, dass ich darüber nachdenke, verdoppelt mit ebenfalls angenähert, so dass ich bin mir nicht sicher, wie das ins Spiel kommen würde.
Wenn Sie eine binäre hacken tun, um zu versuchen, die „richtige“ Quadratwurzel zu finden, können Sie ziemlich leicht erkennen, wenn der Wert, den Sie haben nahe genug ist, zu sagen:
(n+1)^2 = n^2 + 2n + 1
(n-1)^2 = n^2 - 2n + 1
So berechnet n^2 hat, sind die Optionen:
-
n^2 = target: done, return true -
n^2 + 2n + 1 > target > n^2: Sie sind in der Nähe, aber es ist nicht perfekt: return false -
n^2 - 2n + 1 < target < n^2: dito -
target < n^2 - 2n + 1: binary chop auf einem unterenn -
target > n^2 + 2n + 1: binary chop auf einer höherenn
(Sorry, das verwendet n als Ihre aktuelle Vermutung, und target für den Parameter. Entschuldigen uns für die Verwirrung!)
Ich weiß nicht, ob dies schneller sein wird oder nicht, aber es ist ein Versuch wert.
EDIT: Die binäre hacken nicht im gesamten Bereich der ganzen Zahlen zu nehmen, entweder (2^x)^2 = 2^(2x), so, wenn Sie die Top-Set-Bit in Ihrem Ziel gefunden haben (die mit einem Bit-Fummeln Trick getan werden kann; ich vergessen, genau wie) kann man schnell eine Reihe von potentiellen Antworten bekommen. Wohlgemerkt, eine naive binäre hacken ist nur noch bis 31 oder 32 Iterationen nehmen gehen.
Ich ließ meine eigene Analyse mehrerer der Algorithmen in diesem Thread und kam mit einigen neuen Ergebnissen. Sie können die alten Ergebnisse in der Versionsgeschichte dieser Antwort sehen, aber sie sind nicht genau, wie ich einen Fehler gemacht, und verschwendete Zeit mehrere Algorithmen zu analysieren, die nicht in der Nähe sind. Allerdings Lehren aus verschiedenen Antworten ziehen, ich habe jetzt zwei Algorithmen, die die „Gewinner“ dieses Threads zerquetschen. Hier ist der Kern, was ich anders machen 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;
Allerdings ist diese einfache Linie, die die meiste Zeit ein oder zwei sehr schnelle Befehle ergänzt, vereinfacht die switch-case-Anweisung in einer if-Anweisung. Er kann jedoch auf die Laufzeit hinzufügen, wenn viele der getesteten Zahlen signifikant haben Potenz von zwei Faktoren ab.
Die Algorithmen unten sind wie folgt:
- Internet - Kips Gesendete Antwort
- Durron - Meine modifizierte Antwort mit der One-Pass-Antwort als Basis
- DurronTwo -. Meine modifizierte Antwort unter Verwendung der zwei Pässe Antwort (von @JohnnyHeggheim), mit einigen anderen geringfügigen Änderungen
Hier ist ein Beispiel Laufzeit, wenn die Zahlen erzeugt werden unter Verwendung von 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 Probe der Laufzeit, wenn es auf den ersten Millionen longs laufen gelassen nur:
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, DurronTwo tut besser für große Eingänge, weil es den magischen Trick sehr sehr oft benutzen wird, wird aber im Vergleich zum ersten Algorithmus und Math.sqrt verprügelt, weil die Zahlen so viel kleiner sind. Inzwischen hat der einfachere Durron ist ein großer Gewinner, weil es nie um 4 viele, viele Male in den ersten Million Zahlen zu teilen hat.
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 meine Benchmark Gurtzeug: (Erfordert Google 0,1-RC5 Sattel)
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 gemacht, die schneller in einigen Szenarien ist, langsamer in anderen, habe ich verschiedene Benchmarks auf verschiedene Eingaben basieren bekommen. Wenn wir Modulo 0xFFFFFF = 3 x 3 x 5 x 7 x 13 x 17 x 241 berechnen, können wir 97,82% der Zahlen beseitigen, die nicht Quadrate sein. Dies kann (Art) sein in einer Zeile durchgeführt, mit 5 Bit-Operationen:
if (!goodLookupSquares[(int) ((n & 0xFFFFFFl) + ((n >> 24) & 0xFFFFFFl) + (n >> 48))]) return false;
Die sich ergebende Index ist entweder 1) Der Rückstand, 2) der Rückstand + 0xFFFFFF oder 3) der Rückstand + 0x1FFFFFE. Natürlich müssen wir für die Reste modulo 0xFFFFFF, eine Lookup-Tabelle haben, die sich um eine 3mb Datei (in diesem Fall als ASCII-Text Dezimalzahlen gespeichert ist, nicht optimal, aber deutlich verbesserungsfähig mit einem ByteBuffer und so weiter. Aber da das ist es Vorkalkulation nicht so wichtig. können Sie die Datei hier finden (oder selbst erzeugen ):
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 es in ein boolean Array wie folgt geladen werden:
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 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
Es sollte viel schneller sein, um Newton-Methode zu verwenden Integer Quadratwurzel , dann diese Zahl quadriert und überprüfen, wie Sie in Ihrer aktuellen Lösung zu tun. Newton-Verfahren ist die Grundlage für die Carmack Lösung in einigen anderen Antworten erwähnt. Sie sollten eine schnellere Antwort zu bekommen, da Sie nur daran interessiert sind in dem Integer-Teil der Wurzel der Lage sein, so dass Sie früher den Approximationsalgorithmus zu stoppen.
Eine weitere Optimierung, die Sie ausprobieren können: Wenn die Digitale Wurzel einer Reihe nicht endet im 1, 4, 7 oder 9 ist die Zahl nicht ein perfektes Quadrat. Dies kann als eine schnelle Art und Weise verwendet werden, 60% Ihrer Eingaben zu beseitigen, bevor den langsamen Quadratwurzel-Algorithmus angewandt wird.
Ich möchte diese Funktion mit allen arbeiten positive 64-Bit-Integer mit Vorzeichen
Math.sqrt() arbeitet mit Doppel als Eingangsparameter, so dass Sie keine genauen Ergebnisse für ganze Zahlen größer als 2 ^ 53 erhalten werden.
Nur für das Protokoll, ein anderer Ansatz ist es, die Primzerlegung zu verwenden. Wenn jeder Faktor der Zersetzung selbst ist, dann ist die Zahl ein perfektes Quadrat. Also, was Sie wollen, ist zu sehen, ob eine Zahl als Produkt von Quadraten von Primzahlen zerlegt werden. Natürlich können Sie nicht über eine solche Zersetzung erhalten müssen, nur um zu sehen, ob es existiert.
First eine Tabelle der Quadrate von Primzahlen bauen, die niedriger sind als 2 ^ 32. Dies ist bei weitem kleiner als eine Tabelle aller ganzen Zahlen bis zu dieser Grenze.
Eine Lösung würde dann so aussehen:
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. Was sie tut, ist in jedem Schritt überprüft, die das Quadrat einer Primzahl die Eingangsnummer teilen. Ist dies der Fall, dann teilt er sich die Nummer von dem Platz, solange es möglich ist, diesen Platz aus der Primzerlegung zu entfernen. Wenn durch diesen Prozess, wir 1 kam, dann war die Eingangsnummer eine Zersetzung von Quadrat der Primzahlen. Wenn der Platz selbst größer als die Zahl wird, dann gibt es keine Möglichkeit, dieses Quadrat oder irgendwelche größeren Quadrate, können sich unterteilen, so dass die Zahl nicht eine Zersetzung von Quadraten von Primzahlen sein kann.
heutzutage Da sqrt in Hardware und die Notwendigkeit zu tun hier Primzahlen zu berechnen, ich denke, diese Lösung ist viel langsamer. Aber es sollte mit sqrt bessere Ergebnisse als Lösung geben, die sich über nicht mehr als 2 ^ 54 funktionieren wird, wie sagt mrzl in seiner Antwort.
Ein Integer Problem verdient eine ganzzahlige Lösung. So
Sie binäre Suche auf den (nicht-negativ) ganzen Zahlen die größte ganze Zahl t, so dass t**2 <= n zu finden. Dann testen, ob r**2 = n genau. Das kostet Zeit O (log n).
Wenn Sie nicht wissen, wie die positiven ganzen Zahlen binäre Suche, weil die Menge unbegrenzt ist, ist es einfach. Sie beginnen, indem Sie Ihre wachsende Funktion f (oben f(t) = t**2 - n) Berechnung auf Zweierpotenzen. Wenn Sie es drehen positiv sehen, haben Sie eine obere Grenze gefunden. Dann können Sie Standardbinärdistributionen Suche.
Es ist darauf hingewiesen worden, dass die letzten d Ziffern einer Quadratzahl nur auf bestimmte Werte annehmen kann. Die letzten d digits (in der Basis b) einer Anzahl n ist der gleiche wie der Rest, wenn n durch b unterteilt d , dh. in C-Notation n % pow(b, d).
Dies kann zu jedem Modul m verallgemeinert werden, dh. n % m kann verwendet werden, einen gewissen Prozentsatz der Zahlen auszuschließen perfekt Plätzen zu sein. Der Modul Sie sind zur Zeit 64, die ermöglicht, 12, dh. 19% der Reste, wie möglich Quadrate. Mit einer wenig Codierung fand ich das Modul 110880, die nur 2016, also erlaubt. 1,8% von Resten wie möglich Quadrate. Also je nach den Kosten einer Modulo-Operation (dh. Division) und anhand einer Tabelle im Vergleich zu einem Quadratwurzel auf Ihrem Computer, um dieses Modul mit schneller sein könnte.
Durch die Art und Weise, wenn Java eine Art und Weise hat eine gepackte Anordnung von Bits für die Nachschlagtabelle zu speichern, verwenden Sie es nicht. 110.880 32-Bit-Worte nicht viel in diesen Tagen RAM und ein Maschinenwort holen wird schneller sein als ein einzelnes Bit abgerufen werden.
Für Leistung, Sie haben sehr oft einige compromsies zu tun. Andere verschiedene Verfahren zum Ausdruck gebracht haben jedoch festgestellt, Sie Carmacks Hack schneller war dann bis auf bestimmte Werte von N., sollten Sie die „n“ zu überprüfen und, wenn es weniger als diese Zahl ist N, verwenden Carmacks Hack, sonst eine andere Methode verwenden, beschrieben in den Antworten hier.
Dies ist die schnellste Java-Implementierung Ich einfiel, eine Kombination von Techniken, die von anderen in diesem Thread vorgeschlagen werden.
- Mod-256 Test
- Ungenaue mod-3465-Test (Integer-Division auf Kosten einiger Fehlalarme vermeidet)
- Fließkommaquadratwurzel, rund und Vergleichen mit Eingabewert
Ich experimentierte auch mit diesen Änderungen, aber sie haben nicht die Leistung helfen:
- Zusätzlicher mod-255 Test
- Die Aufteilung des Eingangswertes durch Potenzen von 4
- Fast Inverse Square Root (für hohe Werte von N zu arbeiten, um es drei Iterationen benötigt, ist es langsamer als die Hardware Radizierfunktion genug 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;
}
}
}
Die folgende Vereinfachung der maaartinus Lösung erscheint ein paar Prozentpunkte vor der Laufzeit zu rasieren, aber ich bin nicht gut genug, um das Benchmarking eine Benchmark zu produzieren 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 wäre wert, wie der erste Test Weglassen
if (goodMask << x >= 0) return false;
würde die Leistung auswirken.
Sie sollten sie den 2-Leistungsteil von N von Anfang an los zu werden.
2. Bearbeiten Der magische Ausdruck für m sollte unter sein
m = N - (N & (N-1));
und nicht als geschrieben
Ende 2. Bearbeiten
m = N & (N-1); // the lawest bit of N
N /= m;
byte = N & 0x0F;
if ((m % 2) || (byte !=1 && byte !=9))
return false;
1. Edit:
Minor Verbesserung:
m = N & (N-1); // the lawest bit of N
N /= m;
if ((m % 2) || (N & 0x07 != 1))
return false;
Ende des 1. Bearbeiten
Jetzt weiter wie gewohnt. Auf diese Weise, durch die Zeit, die Sie mit dem Floating-Point-Teil bekommen, haben Sie bereits alle Zahlen zu befreien, deren 2-Leistungsteil ungerade ist (etwa die Hälfte), und dann nur Sie 1/8 betrachten, was ist links. D. h Sie führen Sie den Floating-Point-Teil auf 6% der Zahlen.
Dies ist eine Nacharbeit von dezimal in binär des alten Rechner Algorithmus Marchant (sorry, ich habe keine Referenz), in Ruby, angepasst speziell für diese Frage:
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 mich für die Codierung Stil nicht nach unten / Gerüchen oder klobig O / O - es ist der Algorithmus, der zählt, und C ++ ist nicht meine Muttersprache). In diesem Fall suchen wir Rückstand == 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;
};
Der sqrt Anruf ist nicht absolut genau, wie erwähnt wurde, aber es ist interessant und lehrreich, dass es nicht die anderen Antworten in Bezug auf die Geschwindigkeit nicht wegblasen. Schließlich ist die Folge von Assemblersprache Anweisungen für einen sqrt winzig. Intel hat einen Hardware-Befehl, der nicht von Java verwendet wird, ich glaube, weil es nicht zu IEEE nicht entspricht.
Also, warum ist es langsam? Da Java ist eigentlich eine C-Routine durch JNI Aufruf, und es ist tatsächlich langsamer zu tun, als ein Java-Unterprogramm zu nennen, die sich langsamer als es inline zu tun. Das ist sehr ärgerlich, und Java sollte mit einer besseren Lösung zu kommen, dh den Aufbau Punkt Bibliothek Anrufe bei Bedarf in schweben. Na gut.
In C ++, ich vermute, all die komplexen Alternativen auf Geschwindigkeit verlieren würden, aber ich habe sie nicht alle überprüft. Was habe ich, und was Java Menschen nützlich finden werden, ist eine einfache Hack, eine Verlängerung des Sonderfalls von A. Rex vorgeschlagen Tests. Verwenden, um einen einzelnen langen Wert als ein Bit-Array, das nicht Grenzen überprüft wird. Auf diese Weise haben Sie 64-Bit-Boolesche Lookup.
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 in etwa 1/3 der Zeit auf meinem Core 2 Duo-Maschine. Ich vermute, dass weitere Verbesserungen auf der gleichen Linie könnte die Zeit weiter im Durchschnitt reduzieren, aber jedes Mal, wenn Sie überprüfen, Sie sind für mehr eliminiert mehr Tests Handel ab, so kann man nicht gehen zu viel weiter auf dieser Straße.
Sicher, anstatt für negative einen separaten Test mit, können Sie den hohen 6 Bits die gleiche Art und Weise überprüfen.
Beachten Sie, dass alles, was ich tue, ist möglich Quadrate eliminieren, aber wenn ich einen potenziellen Fall habe ich habe das Original zu nennen, inlined isPerfectSquare.
Die INIT2 Routine wird einmal aufgerufen, um die statischen Werte von PP1 und PP2 zu initialisieren. Beachten Sie, dass in meiner Implementierung in C ++, ich bin mit unsigned long long, so da Sie angemeldet sind, dann würden Sie den >>> Operator verwenden.
Es gibt keine innere Notwendigkeit, Grenzen des Arrays überprüfen, aber Java-Optimierer hat dieses Zeug ziemlich schnell, um herauszufinden, so dass ich gebe ihnen keine Schuld dafür.
Ich mag die Idee, eine fast richtige Methode auf einem Teil der Eingabe verwendet werden. Hier ist eine Version mit einem höheren „Offset“. Der Code scheint zu funktionieren und übergibt meinen einfachen Testfall.
Ersetzen Sie einfach Ihre:
if(n < 410881L){...}
Code mit dieser:
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);
}
Projekt Euler wird in den Tags und viele der genannten Probleme darin Zahlen >> 2^64 erfordern überprüfen. Die meisten der oben genannten Optimierungen nicht leicht arbeiten, wenn Sie mit einem 80-Byte-Puffer arbeiten.
habe ich java BigInteger und eine leicht modifizierte Version der Newton-Verfahrens, eine, die mit ganzen Zahlen besser funktioniert. Das Problem war, dass eine exakte Quadrate n^2 statt (n-1) n konvergiert, weil n^2-1 = (n-1)(n+1) und der letzte Fehler war nur eine Stufe unter dem letzten Divisor und der Algorithmus beendet. Es war leicht zu beheben eine zum ursprünglichen Argumente hinzufügen, bevor die Fehler berechnet wird. (Fügen Sie zwei für Kubikwurzeln usw.)
Eine nette Eigenschaft dieses Algorithmus ist, dass Sie sofort sagen können, wenn die Zahl eine Quadratzahl ist - der letzte Fehler (keine Korrektur) in Newton-Verfahren Null. Eine einfache Modifikation kann auch schnell berechnen floor(sqrt(x)) Sie anstelle der nächsten ganzen Zahl. Das ist praktisch, mit mehreren Euler Probleme auf.
Ich habe alle möglichen Ergebnisse, wenn die letzten n Bits eines Quadrates beobachtet wird. Durch sukzessive mehrere Bits untersucht, bis zu 5 / 6.en Eingaben entfallen. Ich entwarf eigentlich diese Fermats Faktorisierung Algorithmus zu implementieren, und es ist sehr schnell da.
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 von Pseudo-Code kann verwendet werden, um die Tests zu erweitern, um mehr Werte zu eliminieren. Die oben genannten Tests sind für k = 0, 1, 2, 3
Es prüft zuerst, ob es einen quadratischen Rest mit Modulen von Zweierpotenz hat, dann testet sie auf der Grundlage eines Abschlussmodul, dann verwendet er die Math.sqrt einen letzten Test zu tun. Ich kam mit der Idee von den oberen Pfosten auf und versuchte, auf ihn zu verlängern. Ich schätze alle Kommentare oder Vorschläge.
Update: , um den Test von einem Modul verwenden, (modSq) und ein Modul Basis von 44.352, mein Testlauf in 96% der Zeit von dem in der Aktualisierung des OP für Zahlen bis zu 1 Mrd. .
Unter Berücksichtigung der allgemeinen Bitlänge (obwohl ich hier bestimmte Art verwendet habe), habe ich versucht, wie unten verein algo zu entwerfen. Einfache und offensichtliche Check für 0,1,2 oder <0 ist zunächst erforderlich. Im Anschluss ist in Sinne einfach, dass es nicht alle vorhandenen Funktionen Mathematik zu verwenden ist zu versuchen. Die meisten der Bediener kann mit bitweise Operatoren ersetzt werden. Ich habe allerdings nicht mit jeder Bank Markierungsdaten getestet. Ich bin weder Experte in Mathematik oder Computeralgorithmus Design insbesondere, würde ich liebe du Problem unter Hinweis darauf, zu sehen. Ich weiß, dass es viele Verbesserungs Chancen gibt es.
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;
}
Ich weiß nicht, ob dies bereits erwähnt wurde. Aber ich fand eine Lösung hier :
int result = (int)(floor(sqrt(b)) - ceil(sqrt(a)) + 1);
Wenn die Geschwindigkeit ein Problem ist, warum nicht die am häufigsten verwendeten Satz von Eingängen und ihre Werte zu einer Lookup-Tabelle abzuteilen und dann tun, was Magie Algorithmus optimiert die Sie für die Ausnahmefällen gekommen sind oben?
Es sollte möglich sein, das ‚kann nicht ein perfektes Quadrat, wenn die letzten X Ziffern N sind‘ zu packen viel effizienter als das! Ich werde Java 32 Bit ints verwenden und produzieren genug Daten, um die letzten 16 Bits der Nummer zu überprüfen -. Das ist 2048 hexadezimal int Werte
...
Ok. Entweder ich habe in eine Zahlentheorie ausführen, die ein wenig über mich ist, oder es ist ein Fehler in meinem Code. Auf jeden Fall, hier ist 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:
(Hrsg. Elided für schlechte Leistung in prettify.js; Sicht-Revisions-Geschichte zu sehen)
Hier ist die einfachste und knappste Art und Weise, obwohl ich weiß nicht, wie es in Bezug auf den CPU-Zyklen vergleicht. Dies funktioniert gut, wenn Sie wissen wollen, ob die Wurzel eine ganze Zahl ist. Wenn Sie wirklich egal, ob es sich um eine ganze Zahl ist, können Sie auch, dass herauszufinden. Hier ist eine einfache (und rein) Funktion:
public static boolean isRootWhole(double number) {
return Math.sqrt(number) % 1 == 0;
}
Wenn Sie Mikro-Optimierung nicht brauchen, diese Antwort ist besser in Bezug auf Einfachheit und Wartbarkeit. Wenn Sie negative Zahlen bekommen werden, vielleicht wollen Sie Math.abs () auf der Anzahl Argumente als Math.sqrt () Argument verwenden.
Auf meinem 3,6 GHz Intel i7-4790 CPU, ein Lauf dieses Algorithmus auf 0 - 10.000.000 dauerte durchschnittlich 35 bis 37 ns pro Berechnung. Ich habe 10 aufeinanderfolgende Läufe, das Drucken die durchschnittliche Verweildauer auf jedem der zehn Millionen sqrt Berechnungen ausgegeben. Jeder Gesamtlauf dauerte nur etwas mehr als 600 ms abgeschlossen.
Wenn Sie eine geringere Anzahl von Berechnungen durchführen, nehmen die früheren Berechnungen etwas länger.
Hier ist ein Teil und Herrscht Lösung.
Wenn die Quadratwurzel aus einer natürlichen Zahl (number) eine natürliche Zahl (solution) ist, können Sie einfach einen Bereich für solution bestimmen basierend auf der Anzahl der Stellen von number:
-
numberhat 1 Ziffer:solutionin Bereich = 1 bis 4 -
numberhat 2 Stellen:solutionin range = 3 bis 10 -
numberhat 3 Stellen:solutionin range = 10-40 -
numberhat 4 Ziffern:solutionin Bereich = 30-100 -
numberhat 5 Ziffern:solutionin Bereich = 100-400
die Wiederholung Beachten Sie?
Sie können diesen Bereich in einem binären Suchansatz verwenden, um zu sehen, ob es ein solution, für die:
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 dafür, wie es zu benutzen.
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"
Wenn Sie Geschwindigkeit wollen, da Ihre ganze Zahlen sind von endlicher Größe, ich vermute, dass der schnellste Weg, würde bedeuten, (a) Aufteilen der Parameter Größe (zB in Kategorien von größte Bit gesetzt), dann wird der Wert gegen eine Anordnung überprüft von Quadratzahlen innerhalb dieses Bereichs.
Im Hinblick auf die Carmac Methode scheint es, wie es ganz einfach einfach sein würde, noch einmal zu wiederholen, was die Anzahl der Ziffern der Genauigkeit verdoppeln sollte. Es ist immerhin ein extrem verkürzten iteratives Verfahren -. Newtons, mit einer sehr guten ersten Vermutung
In Bezug auf Ihre aktuellen besten sehe ich zwei Mikro-Optimierungen:
- das Kontroll vs. 0 nach der Prüfung bewegen Sie mit mod255
- ordnen Sie die Teilung aus Potenzen von vier bis alle Prüfungen für die übliche (75%) Fall zu überspringen.
D.h.:
// 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 sein, ein einfaches
while ((n & 0x03L) == 0) n >>= 2;
Natürlich wäre es interessant zu wissen, wie viele Zahlen an jedem Kontrollpunkt gekeult bekommen -. Ich bezweifle, eher die Kontrollen sind wirklich unabhängig, welche Dinge heikel macht
„Ich bin für den schnellsten Weg, um zu bestimmen, ob ein langer Wert ein perfektes Quadrat ist (das heißt seine Quadratwurzel ist ein andere ganze Zahl ist).“
Die Antworten sind beeindruckend, aber ich konnte eine einfache Prüfung, um zu sehen:
prüfen, ob die erste Zahl auf der rechten Seite des lange es sich um ein Mitglied des Satzes (0,1,4,5,6,9). Wenn dies nicht der Fall, dann kann es nicht vielleicht ein ‚perfektes Quadrat‘ sein.
zB.
4567 -. Kann kein perfektes Quadrat sein
