Le moyen le plus rapide de déterminer si la racine carrée d'un entier est un entier
https://stackoverflow.com/questions/295579
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je cherche le moyen le plus rapide de déterminer si une long valeur est un carré parfait (c'est-à-dire que sa racine carrée est un autre entier):
- Je l'ai fait facilement, en utilisant le
Math.sqrt()intégré fonctionner, mais je me demande s’il existe un moyen de le faire plus rapidement en vous restreindre à un domaine entier uniquement. - Maintenir une table de recherche n’est pas pratique (car il y a environ 2 nombres 31.5 dont le carré est inférieur à 2 63 ).
Voici la manière très simple et directe que je fais maintenant:
public final static boolean isPerfectSquare(long n)
{
if (n < 0)
return false;
long tst = (long)(Math.sqrt(n) + 0.5);
return tst*tst == n;
}
Remarque: j'utilise cette fonction dans de nombreux problèmes de Project Euler . Donc, personne d'autre n'aura jamais à maintenir ce code. Et ce type de micro-optimisation pourrait réellement faire la différence, car le défi consiste en partie à exécuter chaque algorithme en moins d’une minute et cette fonction devra être appelée des millions de fois dans certains problèmes.
J'ai essayé différentes solutions au problème:
- Après des tests exhaustifs, j'ai constaté qu'il n'était pas nécessaire d'ajouter
0.5au résultat de Math.sqrt (), du moins pas sur ma machine. - La racine carrée rapide rapide était plus rapide, mais donnait des résultats incorrects pour n > = 410881. Cependant, comme suggéré par BobbyShaftoe , nous pouvons utiliser le hack FISR pour n < 410881.
- La méthode de Newton était un peu plus lente que
or. Ceci est probablement dû au fait queswitchutilise quelque chose de similaire à la méthode de Newton, mais implémenté dans le matériel, donc il est beaucoup plus rapide qu'en Java. De plus, la méthode de Newton nécessitait toujours l’utilisation de doubles. - Une méthode de Newton modifiée, qui utilisait quelques astuces pour que seuls les calculs entiers soient impliqués, nécessitait quelques piratages pour éviter les débordements (je veux que cette fonction fonctionne avec tous les entiers positifs signés sur 64 bits), et elle était toujours plus lente que d'habitude.
if(lookup[(int)(n&0x3F)]) { test } else return false;. - La hachage binaire était encore plus lente. Cela a du sens, car le hachage binaire nécessitera en moyenne 16 passes pour trouver la racine carrée d’un nombre 64 bits.
- Selon les tests de John, utiliser des instructions <=> est plus rapide en C ++ qu'en <<>, mais en Java et en C #, il ne semble pas y avoir de différence entre <=> et <=>.
- J'ai également essayé de créer une table de consultation (en tant que tableau statique privé de 64 valeurs booléennes). Ensuite, au lieu de l’interrupteur ou de la <=> déclaration, je dirais simplement <=>. À ma grande surprise, c'était (légèrement) plus lent. En effet, les limites du tableau sont vérifiées en Java .
La solution
J'ai découvert une méthode qui fonctionne environ 35% plus rapidement que votre code 6bits + Carmack + code sqrt, du moins avec mon processeur (x86) et mon langage de programmation (C / C ++). Vos résultats peuvent varier, notamment parce que je ne sais pas comment le facteur Java va se jouer.
Mon approche est triple:
- D'abord, filtrez les réponses évidentes. Cela inclut les nombres négatifs et les 4 derniers bits. (J'ai trouvé que regarder les six derniers n'a pas aidé.) Je réponds également oui à 0. (En lisant le code ci-dessous, notez que mon entrée est
int64 x.)if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) ) return false; if( x == 0 ) return true; - Ensuite, vérifiez s’il s’agit d’un carré modulo 255 = 3 * 5 * 17. Comme il s’agit d’un produit de trois nombres premiers distincts, il ne reste que 1/8 des résidus du mod 255 qui sont des carrés. Cependant, selon mon expérience, appeler l'opérateur modulo (%) coûte plus que l'avantage que l'on en tire. J'utilise donc des astuces sur les bits impliquant 255 = 2 ^ 8-1 pour calculer le résidu. (Pour le meilleur ou pour le pire, je n'utilise pas l'astuce consistant à lire des octets individuels dans un mot, uniquement au niveau des bits et des décalages.)
Pour vérifier si le résidu est un carré, je cherche la réponse dans un tableau précalculé.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 - Enfin, essayez de calculer la racine carrée en utilisant une méthode similaire à celle du le lemme de Hensel . (Je ne pense pas que cela s'applique directement, mais cela fonctionne avec quelques modifications.) Avant de faire cela, je divise tous les pouvoirs de 2 avec une recherche binaire:
À ce stade, pour que notre nombre soit un carré, il doit être 1 mod 8.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;
La structure de base du lemme de Hensel est la suivante. (Remarque: code non testé; si cela ne fonctionne pas, essayez t = 2 ou 8.)if((x & 7) != 1) return false;
L'idée est qu'à chaque itération, vous ajoutez un bit à r, le & "Courant &"; racine carrée de x; chaque racine carrée est précise modulo une puissance de plus en plus grande de 2, à savoir t / 2. À la fin, r et t / 2-r seront des racines carrées de x modulo t / 2. (Notez que si r est une racine carrée de x, alors il en est -r. Ceci est vrai même pour les nombres modulo, mais méfiez-vous, modulo de certains nombres, les choses peuvent même avoir plus de 2 racines carrées; cela inclut notamment des puissances de 2. ) Parce que notre racine carrée réelle est inférieure à 2 ^ 32, nous pouvons alors simplement vérifier si r ou t / 2-r sont de vraies racines carrées. Dans mon code actuel, j'utilise la boucle modifiée suivante: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.
L’accélération s’obtient ici de trois manières: valeur initiale précalculée (équivalente à environ 10 itérations de la boucle), sortie antérieure de la boucle et saute certaines valeurs t. Pour la dernière partie, je regardeint64 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 * xet définit t pour être la plus grande puissance de 2 divisant z avec un truc. Cela me permet de sauter des valeurs qui n'auraient de toute façon pas affecté la valeur de r. La valeur de départ précalculée dans mon cas sélectionne le & "Plus petit positif &"; racine carrée modulo 8192.
Même si ce code ne fonctionne pas plus vite pour vous, j'espère que vous apprécierez certaines des idées qu'il contient. Le code complet et testé suit, y compris les tables précalculées.
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;
}Autres conseils
Je suis assez tard pour la fête, mais j'espère donner une meilleure réponse. plus court et (en supposant que mon référence est correct) également beaucoup plus rapide .
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;
}
Le premier test permet d’attraper rapidement la plupart des non-carrés. Il utilise une table de 64 éléments conditionnés de manière longue, il n'y a donc pas de coût d'accès au tableau (contrôles d'indirection et de limites). Pour un long uniformément aléatoire, il y a 81,25% de chances de se terminer ici.
Le deuxième test détecte tous les nombres ayant un nombre impair de deux dans leur factorisation. La méthode Long.numberOfTrailingZeros est très rapide car elle intègre JIT-ed en une seule instruction i86.
Après avoir supprimé les zéros de fin, le troisième test traite les nombres se terminant par 011, 101 ou 111 en binaire, qui ne sont pas des carrés parfaits. Il se soucie également des nombres négatifs et gère également 0.
Le test final revient à double l'arithmétique. Comme <=> a seulement une mantisse de 53 bits,
la conversion de <=> à <=> inclut l’arrondi pour les grandes valeurs. Néanmoins, le test est correct (à moins que le la preuve est fausse).
Essayer d'intégrer l'idée de mod255 n'a pas abouti.
Vous devrez faire des analyses comparatives. Le meilleur algorithme dépendra de la distribution de vos entrées.
Votre algorithme est peut-être presque optimal, mais vous souhaiterez peut-être effectuer une vérification rapide pour éliminer certaines possibilités avant d'appeler votre routine racine carrée. Par exemple, regardez le dernier chiffre de votre numéro en hexadécimal en effectuant un binaire & Quot; et. & Quot; Les carrés parfaits ne peuvent se terminer que par 0, 1, 4 ou 9 en base 16. Ainsi, pour 75% de vos entrées (en supposant qu'elles soient uniformément réparties), vous pouvez éviter un appel à la racine carrée en échange d'une rotation très rapide.
Kip a comparé le code suivant en implémentant l’astuce hexadécimale. Lors des tests entre 1 et 100 000 000, ce code a été exécuté deux fois plus vite que l'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;
}
}
Lorsque j'ai testé le code analogue en C ++, il fonctionnait plus lentement que l'original. Cependant, lorsque j’ai éliminé l’instruction switch, l’astuce hexadécimale rend le code deux fois plus vite.
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;
}
L'élimination de l'instruction switch a eu peu d'effet sur le code C #.
Je pensais aux horribles moments passés dans le cours d’analyse numérique.
Et puis je me souviens, cette fonction contournait le réseau à partir du code source de Quake:
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // wtf?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
#ifndef Q3_VM
#ifdef __linux__
assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
return y;
}
Qui calcule fondamentalement une racine carrée, en utilisant la fonction d'approximation de Newton (je ne me souviens plus du nom exact).
Il devrait être utilisable et peut-être même plus rapide, il s'agit d'un jeu du logiciel phénoménal id!
C'est écrit en C ++, mais il ne devrait pas être trop difficile de réutiliser la même technique en Java une fois que vous avez eu l'idée:
Je l'ai trouvé à l'origine à l'adresse http://www.codemaestro.com/reviews/9
La méthode de Newton est expliquée sur wikipedia: http://en.wikipedia.org/wiki/Newton% 27s_method
Vous pouvez suivre le lien pour plus d'explications sur son fonctionnement, mais si vous vous en moquez bien, c'est en gros ce que je me souviens de lire le blog et de suivre le cours d'analyse numérique:
- la
* (long*) &yest fondamentalement une fonction rapide de conversion en longue, de sorte que les opérations sur les nombres entiers peuvent être appliquées aux octets bruts. - la
0x5f3759df - (i >> 1);ligne est une valeur initiale pré-calculée pour la fonction d'approximation. - la
* (float*) &iconvertit la valeur en virgule flottante. - la
y = y * ( threehalfs - ( x2 * y * y ) )ligne itère de nouveau la valeur sur la fonction.
La fonction d'approximation donne des valeurs plus précises au fur et à mesure que vous répétez la fonction sur le résultat. Dans le cas de Quake, une itération est & "Assez bonne &"; Mais si ce n'était pas pour vous ... vous pouvez ajouter autant d'itérations que nécessaire.
Cela devrait être plus rapide car il réduit le nombre d'opérations de division effectuées selon un enracinement carré naïf à une simple division par 2 (en réalité une opération de multiplication * 0.5F) et le remplace par un nombre fixe d'opérations de multiplication à la place.
Je ne sais pas si ce serait plus rapide ni même exact, mais vous pouvez utiliser Racine carrée magique de John Carmack , algorithme permettant de résoudre la racine carrée plus rapidement. Vous pourriez probablement facilement tester cela pour tous les entiers possibles sur 32 bits et valider que vous obteniez des résultats corrects, car il ne s'agit que d'une approximation. Cependant, maintenant que j'y pense, utiliser des doubles, c'est aussi une approximation, alors je ne sais pas comment cela pourrait entrer en jeu.
Si vous faites un hachage binaire pour essayer de trouver le & "right &"; racine carrée, vous pouvez assez facilement détecter si la valeur que vous avez est assez proche pour dire:
(n+1)^2 = n^2 + 2n + 1
(n-1)^2 = n^2 - 2n + 1
Après avoir calculé n^2, les options sont les suivantes:
-
n^2 = target: done, retourne vrai -
n^2 + 2n + 1 > target > n^2: vous êtes proche, mais ce n'est pas parfait: retournez false -
n^2 - 2n + 1 < target < n^2: idem -
target < n^2 - 2n + 1: hachage binaire sur une valeur inférieuren -
target > n^2 + 2n + 1: hachage binaire sur une valeur supérieuretarget
(Désolé, cela utilise (2^x)^2 = 2^(2x) comme hypothèse actuelle et <=> pour le paramètre. Faites des excuses pour la confusion!)
Je ne sais pas si ce sera plus rapide ou pas, mais ça vaut le coup d'essayer.
EDIT: le hachage binaire ne doit pas nécessairement englober toute la gamme d’entiers, ni <=>, donc une fois que vous avez trouvé le bit de jeu maximal dans votre cible (ce qui peut être fait avec une astuce très complexe J'oublie exactement comment) vous pouvez rapidement obtenir une gamme de réponses potentielles. Remarquez, une côtelette binaire naïve ne prendra encore que 31 ou 32 itérations.
J'ai effectué ma propre analyse de plusieurs algorithmes de ce fil de discussion et j'ai abouti à de nouveaux résultats. Vous pouvez voir ces anciens résultats dans l'historique des modifications de cette réponse, mais ils sont inexacts, car j'ai commis une erreur et perdu du temps à analyser plusieurs algorithmes non proches. Cependant, tirant des leçons de plusieurs réponses différentes, j’ai maintenant deux algorithmes qui écrasent le & Quot; gagnant & Quot; de ce fil. Voici ce que je fais différemment des autres:
// 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;
Cependant, cette simple ligne, qui ajoute la plupart du temps une ou deux instructions très rapides, simplifie grandement l'instruction switch-case en une seule instruction if. Toutefois, cela peut s’ajouter au temps d’exécution si bon nombre des nombres testés ont des facteurs significatifs de puissance de deux.
Les algorithmes ci-dessous sont les suivants:
- Internet - La réponse publiée de Kip
- Durron - Ma réponse modifiée utilisant la réponse en une passe comme base
- DurronTwo : ma réponse modifiée à l'aide de la réponse en deux passes (de @JohnnyHeggheim), avec quelques autres modifications mineures.
Voici un exemple d'exécution si les nombres sont générés à l'aide de 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
Et voici un exemple d’exécution, s’il est exécuté sur le premier million seulement:
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
Comme vous pouvez le constater, DurronTwo fait mieux pour les entrées volumineuses, car il utilise très souvent le tour de magie, mais se désagrège par rapport au premier algorithme et Math.sqrt car les nombres sont beaucoup plus petits. En attendant, le plus simple Durron est un énorme gagnant car il n'a jamais à diviser par 4 de nombreuses fois dans le premier million de chiffres.
Voici 0xFFFFFF = 3 x 3 x 5 x 7 x 13 x 17 x 241:
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;
}
Et + 0xFFFFFF
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;
}
Et mon harnais de référence: (nécessite 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: j'ai mis au point un nouvel algorithme plus rapide dans certains scénarios et plus lent dans d'autres. J'ai obtenu différents points de repère en fonction de différentes entrées. Si nous calculons modulo + 0x1FFFFFE, nous pouvons éliminer 97,82% des nombres qui ne peuvent pas être des carrés. Cela peut être fait (en quelque sorte) sur une ligne, avec 5 opérations au niveau du bit:
if (!goodLookupSquares[(int) ((n & 0xFFFFFFl) + ((n >> 24) & 0xFFFFFFl) + (n >> 48))]) return false;
L'indice résultant est soit 1) le résidu, 2) le résidu 0xFFFFFF, ou 3) le résidu ByteBuffer. Bien sûr, nous avons besoin d’une table de recherche pour les résidus modulo boolean, qui concerne un fichier de 3 Mo (dans ce cas, stockée sous forme de nombres décimaux en texte ASCII, non optimale mais clairement pouvant être améliorée avec un <=> et ainsi de suite. Le précalcul n'a pas beaucoup d'importance. Vous trouverez le fichier ici ( ou le générer vous-même):
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;
}
Je le charge dans un <=> tableau comme ceci:
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();
}
Exemple d'exécution. Il a battu <=> (version un) dans chaque essai que j'ai exécuté.
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
Il devrait être beaucoup plus rapide d'utiliser la la méthode de Newton pour calculer le Racine carrée d'un nombre entier , puis convertissez ce nombre en carrés et vérifiez, comme vous le faites dans votre solution actuelle. La méthode de Newton est à la base de la solution de Carmack mentionnée dans certaines autres réponses. Vous devriez pouvoir obtenir une réponse plus rapide car vous ne vous intéressez qu'à la partie entière de la racine, ce qui vous permet d'arrêter l'algorithme d'approximation plus tôt.
Une autre optimisation que vous pouvez essayer: Si la Racine numérique d'un numéro ne se termine pas dans 1, 4, 7 ou 9, le nombre n'est pas un carré parfait. Cela peut être utilisé comme moyen rapide d’éliminer 60% de vos entrées avant d’appliquer l’algorithme de racine carrée plus lente.
Je veux que cette fonction fonctionne avec tous entiers positifs signés 64 bits
Math.sqrt() fonctionne avec des doublons en tant que paramètres d'entrée. Par conséquent, vous n'obtiendrez pas de résultats précis pour les entiers supérieurs à 2 ^ 53 .
Juste pour mémoire, une autre approche consiste à utiliser la décomposition principale. Si tous les facteurs de la décomposition sont pairs, alors le nombre est un carré parfait. Vous voulez donc savoir si un nombre peut être décomposé en tant que produit de carrés de nombres premiers. Bien sûr, vous n'avez pas besoin d'obtenir une telle décomposition, il suffit de voir si elle existe.
Commencez par créer une table de carrés de nombres premiers inférieurs à 2 ^ 32. C'est beaucoup plus petit qu'une table de tous les entiers jusqu'à cette limite.
Une solution serait alors la suivante:
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;
}
}
Je suppose que c'est un peu cryptique. Cela vérifie à chaque étape que le carré d'un nombre premier divise le nombre saisi. Si tel est le cas, il divise le nombre par le carré aussi longtemps que possible, afin de supprimer ce carré de la décomposition principale. Si, par ce processus, nous arrivons à 1, le nombre entré est une décomposition de carrés de nombres premiers. Si le carré devient plus grand que le nombre lui-même, il n’est en aucun cas possible que ce carré, ou un carré plus grand, puisse le diviser. Ce nombre ne peut donc être une décomposition de carrés de nombres premiers.
Étant donné les connaissances techniques actuelles et la nécessité de calculer les nombres premiers ici, je suppose que cette solution est beaucoup plus lente. Mais cela devrait donner de meilleurs résultats que la solution avec sqrt qui ne fonctionnera pas au-delà de 2 ^ 54, comme le dit mrzl dans sa réponse.
Un problème d’entier mérite une solution d’entier. Ainsi
Faites une recherche binaire sur les entiers (non négatifs) pour trouver le plus grand entier t tel que t**2 <= n. Puis testez si r**2 = n exactement. Cela prend du temps O (log n).
Si vous ne savez pas comment effectuer une recherche binaire sur les entiers positifs car l'ensemble est illimité, c'est simple. Vous commencez par calculer votre fonction croissante f (ci-dessus f(t) = t**2 - n) sur des puissances de deux. Lorsque vous le voyez devenir positif, vous avez trouvé une limite supérieure. Ensuite, vous pouvez effectuer une recherche binaire standard.
Il a été souligné que les derniers d chiffres d'un carré parfait ne peuvent prendre que certaines valeurs. Les derniers b chiffres (en base n) d'un nombre n % pow(b, d) sont identiques au reste lorsque m est divisé par n % m <=> , c'est-à-dire. en notation C <=>.
Ceci peut être généralisé à n’importe quel module <=>, c.-à-d. <=> peut être utilisé pour exclure certains pourcentages de carrés parfaits. Le module que vous utilisez actuellement est 64, ce qui permet 12, c'est-à-dire. 19% des restes, en carrés possibles. Avec un peu de codage, j'ai trouvé le module 110880 qui n'autorise que 2016, c'est-à-dire. 1,8% des restes sont des carrés possibles. Par conséquent, en fonction du coût d’une opération de module (division) et d’une recherche de table par rapport à une racine carrée de votre machine, l’utilisation de ce module peut s'avérer plus rapide.
Soit dit en passant, si Java dispose d’un moyen de stocker un tableau condensé de bits pour la table de recherche, ne l’utilisez pas. 110880 Les mots de 32 bits n’ont pas beaucoup de RAM ces jours-ci, et récupérer un mot machine va être plus rapide que de récupérer un seul bit.
Pour les performances, vous devez très souvent faire des compromis. D'autres ont exprimé diverses méthodes, cependant, vous avez noté que le piratage de Carmack était plus rapide jusqu'à certaines valeurs de N. Ensuite, vous devriez vérifier le & "N &"; et s'il est inférieur à ce nombre N, utilisez le hack de Carmack, sinon utilisez une autre méthode décrite dans les réponses fournies ici.
C’est l’implémentation Java la plus rapide que j’ai pu imaginer, utilisant une combinaison de techniques suggérées par d’autres dans ce fil.
- Test Mod-256
- Test Inexact mod-3465 (évite la division entière au prix de faux positifs)
- Racine carrée à virgule flottante, arrondir et comparer avec la valeur d'entrée
J'ai également expérimenté ces modifications, mais elles n'ont pas amélioré les performances:
- Test supplémentaire du mod-255
- Division de la valeur d'entrée par des puissances de 4
- Racine carrée rapide rapide (pour fonctionner avec des valeurs élevées de N, il faut 3 itérations, ce qui suffit à la rendre plus lente que la fonction racine carrée matérielle.)
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;
}
}
}
La simplification suivante de la solution de maaartinus semble réduire de quelques points de pourcentage le temps d'exécution, mais je ne suis pas assez bon en benchmarking pour produire une référence en laquelle je peux avoir confiance:
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;
}
Il serait utile de vérifier comment omettre le premier test,
if (goodMask << x >= 0) return false;
affecterait les performances.
Vous devriez vous débarrasser de la partie à 2 puissances de N dès le début.
2e édition L’expression magique pour m ci-dessous devrait être
m = N - (N & (N-1));
et non tel qu'écrit
Fin de la 2ème édition
m = N & (N-1); // the lawest bit of N
N /= m;
byte = N & 0x0F;
if ((m % 2) || (byte !=1 && byte !=9))
return false;
1ère édition:
Amélioration mineure:
m = N & (N-1); // the lawest bit of N
N /= m;
if ((m % 2) || (N & 0x07 != 1))
return false;
Fin de la première édition
Maintenant, continuez comme d'habitude. De cette façon, lorsque vous atteignez la partie à virgule flottante, vous avez déjà supprimé tous les nombres dont la partie à 2 puissances est impair (environ la moitié), et vous ne considérez alors que 1/8 de ce qui reste. C'est à dire. vous exécutez la partie à virgule flottante sur 6% des nombres.
C’est un remaniement décimal / binaire de l’ancien algorithme de la calculatrice Marchant (désolé, je n’ai pas de référence), en Ruby, spécialement adapté à cette question:
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
Voici un bilan de quelque chose de similaire (ne me refusez pas le style / les odeurs de codage ou le mauvais fonctionnement du code, c’est l’algorithme qui compte et le C ++ n’est pas ma langue maternelle). Dans ce cas, nous recherchons des résidus == 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;
};
L'appel à venir n'est pas parfaitement précis, comme cela a été mentionné, mais il est intéressant et instructif de ne pas détruire les autres réponses en termes de rapidité. Après tout, la séquence d'instructions en langage assembleur pour un sqrt est minuscule. Intel propose une instruction matérielle, qui n’est pas utilisée par Java, car elle n’est pas conforme à la norme IEEE.
Alors pourquoi est-ce lent? Parce que Java appelle en fait une routine C par l’intermédiaire de JNI, il est plus lent que d’appeler un sous-programme Java, qui est lui-même plus lent que de le faire en ligne. Ceci est très gênant et Java aurait dû proposer une meilleure solution, à savoir la construction d’appels de bibliothèque à virgule flottante si nécessaire. Oh bien.
En C ++, je soupçonne que toutes les alternatives complexes perdraient de la vitesse, mais je ne les ai pas toutes vérifiées. Ce que j’ai fait, et ce que les gens de Java trouveront utile, c’est un simple hack, une extension du test de cas particulier suggéré par A. Rex. Utilisez une seule valeur longue sous forme de tableau de bits, qui n'est pas coché. De cette façon, vous avez une recherche booléenne 64 bits.
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;
}
La routine isPerfectSquare5 s'exécute dans environ un tiers du temps sur ma machine Core2 Duo. Je pense que d'autres ajustements dans le même sens pourraient réduire le temps en moyenne, mais chaque fois que vous cochez, vous échangez plus de tests pour plus d'éliminations, de sorte que vous ne pouvez pas aller trop loin dans cette voie.
Bien sûr, plutôt que d’avoir un test séparé pour le négatif, vous pouvez vérifier les 6 bits les plus forts de la même manière.
Notez que tout ce que je fais est d'éliminer les carrés possibles, mais lorsque j'ai un cas potentiel, je dois appeler l'original en ligne, isPerfectSquare.
La routine init2 est appelée une fois pour initialiser les valeurs statiques de pp1 et pp2. Notez que dans mon implémentation en C ++, j'utilise unsigned long long, donc puisque vous êtes signé, vous devez utiliser le & Gt; & Gt; & Gt; opérateur.
Il n’existe aucun besoin intrinsèque de contrôler le tableau, mais l’optimiseur Java doit résoudre ce problème assez rapidement, je ne les en blâme donc pas.
J'aime l'idée d'utiliser une méthode presque correcte sur certaines des entrées. Voici une version avec un & Quotient supérieur & Quot; Le code semble fonctionner et réussit mon cas de test simple.
Il suffit de remplacer votre:
if(n < 410881L){...}
code avec celui-ci:
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);
}
Le projet Euler est mentionné dans les balises et bon nombre de ses problèmes nécessitent la vérification des numéros > > 2^64 La plupart des optimisations mentionnées ci-dessus ne fonctionnent pas facilement lorsque vous utilisez un tampon de 80 octets.
J'ai utilisé java BigInteger et une version légèrement modifiée de la méthode de Newton, qui fonctionne mieux avec les entiers. Le problème était que les carrés exacts n^2 convergeaient vers (n-1) au lieu de n car n^2-1 = (n-1)(n+1) et que l'erreur finale était juste une étape en dessous du diviseur final et que l'algorithme était terminé. Il était facile de corriger en ajoutant un à l'argument initial avant de calculer l'erreur. (Ajoutez deux pour les racines de cube, etc.)
Un attribut intéressant de cet algorithme est que vous pouvez immédiatement dire si le nombre est un carré parfait - l'erreur finale (et non la correction) dans la méthode de Newton sera égale à zéro. Une simple modification vous permet également de calculer rapidement floor(sqrt(x)) au lieu du nombre entier le plus proche. C’est pratique avec plusieurs problèmes d’Euler.
J'ai vérifié tous les résultats possibles lorsque les n derniers bits d'un carré sont observés. En examinant successivement plus de bits, il est possible d’éliminer jusqu’à 5 / 6e des entrées. J'ai en fait conçu cela pour implémenter l'algorithme de factorisation de Fermat, et il est très rapide là-bas.
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;
}
Le dernier bit du pseudocode peut être utilisé pour étendre les tests afin d’éliminer plus de valeurs. Les tests ci-dessus sont pour k = 0, 1, 2, 3
Il vérifie d’abord s'il a un carré résiduel avec des modules de puissance de deux, puis il utilise un module final, puis utilise Math.sqrt pour effectuer un test final. J'ai eu l'idée du poste principal et j'ai essayé de la prolonger. J'apprécie vos commentaires ou suggestions.
Mise à jour: En utilisant le test avec un module (modSq) et une base de module de 44352, mon test s'exécute dans 96% du temps de celui de la mise à jour du PO pour des nombres allant jusqu'à 1 000 000 000 .
Considérant la longueur de bit générale (bien que j’ai utilisé un type spécifique ici), j’ai essayé de concevoir un algorithme simpliste comme ci-dessous. Un contrôle simple et évident pour 0,1,2 ou & Lt; 0 est requis au départ. Ce qui suit est simple dans le sens où il n’essaye pas d’utiliser les fonctions mathématiques existantes. La plupart des opérateurs peuvent être remplacés par des opérateurs binaires. Je n'ai pas testé avec des données de référence cependant. Je ne suis ni un spécialiste des mathématiques ni de la conception d'algorithmes informatiques en particulier, j'aimerais beaucoup que vous signaliez un problème. Je sais que les chances d’amélioration sont nombreuses.
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;
}
Je ne sais pas si cela a déjà été mentionné. Mais j’ai trouvé une solution ici :
int result = (int)(floor(sqrt(b)) - ceil(sqrt(a)) + 1);
Si la rapidité vous préoccupe, pourquoi ne pas partitionner le jeu d'entrées le plus couramment utilisé et ses valeurs dans une table de correspondance, puis utiliser l'algorithme magique optimisé que vous avez conçu pour les cas exceptionnels?
Il devrait être possible d’emballer le 'ne peut pas être un carré parfait si les X derniers chiffres sont N' beaucoup plus efficacement que cela! Je vais utiliser java 32 bits ints et produire suffisamment de données pour vérifier les 16 derniers bits du nombre, c'est-à-dire 2048 valeurs int hexadécimales.
...
Ok. Soit je suis tombé sur une théorie des nombres qui me dépasse un peu, soit il y a un bug dans mon code. En tout cas, voici le 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("};");
}
et voici les résultats:
(ed: élué pour ses performances médiocres dans prettify.js; affiche l'historique des révisions pour le voir.)
Voici le moyen le plus simple et le plus concis, bien que je ne sache pas comment il se compare en termes de cycles de processeur. Cela fonctionne très bien si vous souhaitez uniquement savoir si la racine est un nombre entier. Si vous vous souciez vraiment de savoir s'il s'agit d'un entier, vous pouvez également le comprendre. Voici une fonction simple (et pure):
public static boolean isRootWhole(double number) {
return Math.sqrt(number) % 1 == 0;
}
Si vous n'avez pas besoin de la micro-optimisation, cette réponse est meilleure en termes de simplicité et de facilité de maintenance. Si vous voulez obtenir des nombres négatifs, vous voudrez peut-être utiliser Math.abs () sur l'argument de nombre comme argument Math.sqrt ().
Sur mon processeur Intel i7-4790 à 3,6 GHz, une exécution de cet algorithme entre 0 et 10 000 000 a pris en moyenne 35 à 37 nanosecondes par calcul. J'ai effectué 10 analyses séquentiels, en affichant le temps moyen consacré à chacun des dix millions de calculs carrés. Chaque course totale a pris un peu plus de 600 ms.
Si vous effectuez un nombre inférieur de calculs, les calculs antérieurs prennent un peu plus longtemps.
Voici une solution de division et de conquête.
Si la racine carrée d'un nombre naturel (number) est un nombre naturel (solution), vous pouvez facilement déterminer une plage pour <=> en fonction du nombre de chiffres de <=>:
- <=> a 1 chiffre: <=> dans la plage = 1 - 4
- <=> a 2 chiffres: <=> dans la plage = 3 - 10
- <=> a 3 chiffres: <=> dans la plage = 10 - 40
- <=> a 4 chiffres: <=> dans la plage = 30 - 100
- <=> a 5 chiffres: <=> dans la plage = 100 - 400
Notez la répétition?
Vous pouvez utiliser cette plage dans une approche de recherche binaire pour voir s'il existe un <=> pour lequel:
number == solution * solution
Voici le code
Voici ma classe 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;
}
}
Et voici un exemple d'utilisation.
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"
Si vous voulez la vitesse, étant donné que vos entiers sont de taille finie, je suppose que le moyen le plus rapide impliquerait (a) de partitionner les paramètres par taille (par exemple, en catégories par plus grand ensemble de bits), puis en comparant la valeur à un tableau. des carrés parfaits dans cette plage.
En ce qui concerne la méthode Carmac, il semble assez facile d’itérer une nouvelle fois, ce qui devrait doubler le nombre de chiffres de précision. Après tout, il s’agit d’une méthode itérative extrêmement tronquée - celle de Newton, avec une très bonne première hypothèse.
En ce qui concerne votre meilleur actuel, je vois deux micro-optimisations:
- déplacez le chèque contre 0 après le chèque en utilisant mod255
- réorganisez les puissances de division de quatre pour ignorer toutes les vérifications du cas habituel (75%).
I.e:
// 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;
}
Encore mieux, un simple
while ((n & 0x03L) == 0) n >>= 2;
Évidemment, il serait intéressant de savoir combien de numéros sont cueillis à chaque point de contrôle - je doute que les contrôles soient vraiment indépendants, ce qui complique les choses.
& "; Je cherche le moyen le plus rapide de déterminer si une valeur longue est un carré parfait (c'est-à-dire que sa racine carrée est un autre entier). &";
Les réponses sont impressionnantes, mais je n’ai pas réussi à voir un simple contrôle:
vérifie si le premier nombre à droite du membre devient un membre du jeu (0,1,4,5,6,9). Si ce n'est pas le cas, il ne peut pas s'agir d'un "carré parfait".
par exemple.
4567 - ne peut pas être un carré parfait.
