Méthode la plus rapide pour déterminer si la racine carrée d'un entier est un entier

1455

Je cherche le moyen le plus rapide pour déterminer si une longvaleur est un carré parfait (c'est-à-dire que sa racine carrée est un autre entier):

  1. Je l'ai fait de manière simple, en utilisant la Math.sqrt() fonction intégrée, mais je me demande s'il y a un moyen de le faire plus rapidement en vous limitant au domaine entier.
  2. Il n'est pas pratique de gérer une table de correspondance (car il existe environ 2 31,5 entiers dont le carré est inférieur à 2 63 ).

Voici la façon très simple et directe dont je le 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 liés à Project Euler . Donc, personne d'autre n'aura jamais à maintenir ce code. Et ce type de micro-optimisation pourrait réellement faire une différence, car une partie du défi consiste à faire 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é les différentes solutions au problème:

  • Après des tests exhaustifs, j'ai trouvé que l'ajout 0.5au résultat de Math.sqrt () n'est pas nécessaire, du moins pas sur ma machine.
  • La racine carrée inverse rapide était plus rapide, mais elle a donné 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 Math.sqrt(). C'est probablement parce qu'il Math.sqrt()utilise quelque chose de similaire à la méthode de Newton, mais implémenté dans le matériel, c'est donc beaucoup plus rapide qu'en Java. De plus, la méthode de Newton exigeait toujours l'utilisation de doubles.
  • Une méthode de Newton modifiée, qui utilisait quelques astuces pour que seules les mathématiques entières soient impliquées, nécessitait des hacks pour éviter le débordement (je veux que cette fonction fonctionne avec tous les entiers signés 64 bits positifs), et elle était toujours plus lente que Math.sqrt().
  • La coupe binaire était encore plus lente. Cela a du sens, car le découpage binaire nécessitera en moyenne 16 passes pour trouver la racine carrée d'un nombre 64 bits.
  • Selon les tests de John, l'utilisation d' orinstructions est plus rapide en C ++ que l'utilisation de a switch, mais en Java et C #, il ne semble pas y avoir de différence entre oret switch.
  • J'ai également essayé de créer une table de recherche (en tant que tableau statique privé de 64 valeurs booléennes). Ensuite, au lieu d'un commutateur ou d'une ordéclaration, je dirais simplement if(lookup[(int)(n&0x3F)]) { test } else return false;. À ma grande surprise, c'était (légèrement) plus lent. En effet , les limites des tableaux sont vérifiées en Java .
java math optimization perfect-square Kip
la source
21
Il s'agit du code Java, où int == 32 bits et long == 64 bits, et les deux sont signés.
Kip
14
@Shreevasta: J'ai fait des tests sur de grandes valeurs (supérieures à 2 ^ 53), et votre méthode donne des faux positifs. Le premier rencontré est pour n = 9007199326062755, qui n'est pas un carré parfait mais est retourné comme un.
Kip
37
S'il vous plaît ne l'appelez pas le "piratage de John Carmack". Il n'est pas venu avec ça.
user9282
84
@mamama - Peut-être, mais cela lui est attribué. Henry Ford n'a pas inventé la voiture, les Wright Bros.n'ont pas inventé l'avion, et Galleleo n'a pas été le premier à comprendre que la Terre tournait autour du soleil ... le monde est composé d'inventions volées (et amour).
Robert Fraser
4
Vous pourriez obtenir une augmentation de vitesse minime dans le «quickfail» en utilisant quelque chose comme ((1<<(n&15))|65004) != 0, au lieu d'avoir trois contrôles distincts.
Nabb

Réponses:

736

J'ai trouvé une méthode qui fonctionne ~ 35% plus rapidement que votre code 6bits + Carmack + sqrt, au moins avec mon CPU (x86) et mon langage de programmation (C / C ++). Vos résultats peuvent varier, surtout parce que je ne sais pas comment le facteur Java se déroulera.

Mon approche est triple:

  1. Tout d'abord, filtrez les réponses évidentes. Cela inclut les nombres négatifs et en regardant 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 ma saisie est int64 x.) 
    if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) )
    return false;
if( x == 0 )
    return true;
  2. Ensuite, vérifiez si c'est un carré modulo 255 = 3 * 5 * 17. Parce que c'est un produit de trois nombres premiers distincts, seulement environ 1/8 des résidus mod 255 sont des carrés. Cependant, d'après mon expérience, appeler l'opérateur modulo (%) coûte plus cher que l'avantage que l'on obtient, donc j'utilise des trucs de bits impliquant 255 = 2 ^ 8-1 pour calculer le résidu. (Pour le meilleur ou pour le pire, je n'utilise pas l'astuce de lecture des octets individuels d'un mot, seulement au niveau du bit et et des décalages.) 
    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.
    Pour vérifier réellement si le résidu est un carré, je recherche la réponse dans un tableau précalculé. 
    if( bad255[y] )
    return false;
// However, I just use a table of size 512
  3. Enfin, essayez de calculer la racine carrée en utilisant une méthode similaire au 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: 
    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;
    À ce stade, pour que notre nombre soit un carré, il doit être 1 mod 8. 
    if((x & 7) != 1)
    return false;
    La structure de base du lemme de Hensel est la suivante. (Remarque: code non testé; s'il ne fonctionne pas, essayez t = 2 ou 8.) 
    int64 t = 4, r = 1;
t <<= 1; r += ((x - r * r) & t) >> 1;
t <<= 1; r += ((x - r * r) & t) >> 1;
t <<= 1; r += ((x - r * r) & t) >> 1;
// Repeat until t is 2^33 or so.  Use a loop if you want.
    L'idée est qu'à chaque itération, vous ajoutez un bit sur r, la racine carrée "courante" 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, il en est de même pour -r. C'est vrai même les nombres modulo, mais attention, modulo certains nombres, les choses peuvent avoir encore plus de 2 racines carrées; cela inclut notamment les puissances de 2. ) Parce que notre racine carrée réelle est inférieure à 2 ^ 32, à ce stade, nous pouvons réellement 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 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) );
    L'accélération ici est obtenue de trois manières: valeur de départ précalculée (équivalant à ~ 10 itérations de la boucle), sortie plus précoce de la boucle et saut de certaines valeurs t. Pour la dernière partie, je regarde z = r - x * xet règle t pour être la plus grande puissance de 2 divisant z avec un petit truc. Cela me permet de sauter des valeurs t qui n'auraient pas affecté la valeur de r de toute façon. La valeur de départ précalculée dans mon cas sélectionne le "plus petit positif" racine modulo 8192.

Même si ce code ne fonctionne pas plus rapidement 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;
}
A. Rex
la source
5
Hou la la! J'essaierai de le convertir en Java et de faire une comparaison, ainsi qu'une vérification de la précision des résultats. Je vous ferai savoir ce que je trouve.
Kip
79
Wow, c'est magnifique. J'avais déjà vu Hensel se soulever auparavant (calculer les racines des polynômes modulo un nombre premier) mais je n'avais même pas réalisé que le lemme pouvait être soigneusement abaissé jusqu'à la fin pour calculer les racines carrées des nombres; c'est ... édifiant :)
ShreevatsaR
3
@nightcracker Ce n'est pas le cas. 9 < 0 => false, 9&2 => 0, 9&7 == 5 => false, 9&11 == 8 => false.
primo
53
Maartinus a publié une solution 2x plus rapide (et beaucoup plus courte) ci-dessous, un peu plus tard, qui ne semble pas susciter beaucoup d'amour.
Jason C
3
Il semble que l'avantage de vitesse dans les différentes solutions soit obtenu en filtrant les carrés évidents. Quelqu'un a-t-il évalué la situation du filtrage via la solution de Maartinus, puis en utilisant simplement la fonction sqrt car c'est une fonction intégrée?
user1914292
378

Je suis assez en retard à la fête, mais j'espère apporter une meilleure réponse; plus court et (en supposant que mon indice de référence est correct) aussi 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 capture rapidement la plupart des non-carrés. Il utilise une table de 64 éléments emballée dans un long, donc il n'y a pas de coût d'accès au tableau (vérifications d'indirection et de limites). Pour un aléatoire uniforme long, il y a une probabilité de 81,25% de se terminer ici.

Le deuxième test capture tous les nombres ayant un nombre impair de deux dans leur factorisation. La méthode Long.numberOfTrailingZerosest très rapide car elle est convertie en JIT dans une seule instruction i86.

Après avoir supprimé les zéros de fin, le troisième test gère 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 à l' doublearithmétique. Comme la doublemantisse n'a que 53 bits, la conversion de longà doubleinclut l'arrondi pour les grandes valeurs. Néanmoins, le test est correct (sauf si la preuve est fausse).

La tentative d'intégration de l'idée du mod255 n'a pas réussi.

maaartinus
la source
3
Ce masquage implicite de la valeur de décalage est un peu ... mauvais. Avez-vous une idée pourquoi c'est dans la spécification Java?
dfeuer
6
@dfeuer Je suppose qu'il y a deux raisons: 1. Décaler de plus n'a aucun sens. 2. C'est comme le HW fonctionne et toute personne utilisant des opérations au niveau du bit est intéressée par les performances, donc faire autre chose serait mal. - Le goodMasktest le fait, mais il le fait avant le bon décalage. Il faudrait donc le répéter, mais de cette façon, c'est plus simple et l'AFAIK un tout petit peu plus rapide et tout aussi bon.
maaartinus
3
@dfeuer Pour le benchmark, il est important de donner une réponse DÈS QUE POSSIBLE, et le décompte zéro en fin lui-même ne donne aucune réponse; ce n'est qu'une étape préparatoire. i86 / amd64 le font. Aucune idée sur les petits processeurs des mobiles, mais au pire, Java doit générer une instruction AND pour eux, ce qui est sûrement plus simple que l'inverse.
maaartinus
2
Un test @Sebastian probablement mieux: if ((x & (7 | Integer.MIN_VALUE)) != 1) return x == 0;.
maaartinus
4
"Comme le double n'a que 56 bits de mantisse" -> je dirais qu'il en a probablement un 53 bits . Aussi
chux
132

Vous devrez faire des analyses comparatives. Le meilleur algorithme dépendra de la distribution de vos entrées.

Votre algorithme peut être presque optimal, mais vous voudrez peut-être faire une vérification rapide pour exclure 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 faisant un "et". Les carrés parfaits ne peuvent se terminer qu'en 0, 1, 4 ou 9 en base 16, donc pour 75% de vos entrées (en supposant qu'elles sont uniformément réparties), vous pouvez éviter un appel à la racine carrée en échange d'un peu de twiddling très rapide.

Kip a testé le code suivant implémentant l'astuce hex. Lors du test des numéros 1 à 100 000 000, ce code a fonctionné 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 s'est en fait déroulé plus lentement que l'original. Cependant, lorsque j'ai supprimé l'instruction switch, l'astuce hexadécimale rend le code deux fois plus rapide.

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 #.

John D. Cook
la source
c'est assez intelligent ... n'aurait pas pensé à ça
warren
Joli point sur les bits de fin. J'essaierais de combiner ce test avec certaines des autres remarques ici.
PeterAllenWebb
3
Superbe solution. Vous vous demandez comment vous en êtes arrivé là? Est-ce un principe assez établi ou simplement quelque chose que vous avez compris? : D
Jeel Shah
3
@LarsH Il n'est pas nécessaire d'ajouter 0,5, voir ma solution pour un lien vers la preuve.
maaartinus
2
@JerryGoyal Cela dépend du compilateur et des valeurs des cas. Dans un compilateur parfait, un commutateur est toujours au moins aussi rapide que if-else. Mais les compilateurs ne sont pas parfaits, il est donc préférable de l'essayer, comme John l'a fait.
fishinear
52

Je pensais aux moments horribles que j'ai passés dans le cours d'analyse numérique.

Et puis je me souviens, il y avait cette fonction qui tournait autour du net à 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;
}

Ce qui calcule essentiellement une racine carrée, en utilisant la fonction d'approximation de Newton (je ne peux pas me souvenir du nom exact).

Il devrait être utilisable et pourrait même être plus rapide, il s'agit d'un des jeux phénoménaux du logiciel d'identification!

Il 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 l'idée:

Je l'ai trouvé à l'origine sur: http://www.codemaestro.com/reviews/9

La méthode de Newton expliquée sur wikipedia: http://en.wikipedia.org/wiki/Newton%27s_method

Vous pouvez suivre le lien pour plus d'explications sur la façon dont cela fonctionne, mais si vous ne vous souciez pas beaucoup, c'est à peu près ce dont je me souviens en lisant le blog et en suivant le cours d'analyse numérique:

  • il * (long*) &ys'agit essentiellement d'une fonction de conversion rapide en fonction longue de sorte que des opérations entières peuvent être appliquées sur les octets bruts.
  • la 0x5f3759df - (i >> 1);ligne est une valeur de départ pré-calculée pour la fonction d'approximation.
  • le * (float*) &iconvertit la valeur en virgule flottante.
  • la y = y * ( threehalfs - ( x2 * y * y ) )ligne réitère basiquement la valeur sur la fonction.

La fonction d'approximation donne des valeurs plus précises plus vous itérez 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 ... alors vous pouvez ajouter autant d'itérations que vous le souhaitez.

Cela devrait être plus rapide car il réduit le nombre d'opérations de division effectuées en racine carrée naïve à une simple division par 2 (en fait une * 0.5Fopération de multiplication) et le remplace par un nombre fixe d'opérations de multiplication à la place.

chakrit
la source
9
Il convient de noter que cela renvoie 1 / sqrt (nombre), pas sqrt (nombre). J'ai fait quelques tests, et cela échoue à partir de n = 410881: la formule magique de John Carmack renvoie 642.00104, lorsque la racine carrée réelle est 641.
Kip
11
Vous pouvez consulter l'article de Chris Lomonts sur les racines carrées inverses rapides: lomont.org/Math/Papers/2003/InvSqrt.pdf Il utilise la même technique qu'ici, mais avec un nombre magique différent. Le papier explique pourquoi le nombre magique a été choisi.
4
De plus, Beyond3d.com/content/articles/8 et Beyond3d.com/content/articles/15 ont mis en lumière les origines de cette méthode. Il est souvent attribué à John Carmack, mais il semble que le code original ait été (éventuellement) écrit par Gary Tarolli, Greg Walsh et probablement d'autres.
3
De plus, vous ne pouvez pas taper des flottants et des encres en Java.
Antimony
10
@Antimony qui dit? FloatToIntBits et IntToFloatBits existent depuis java 1.0.2.
corsiKa
38

Je ne sais pas si ce serait plus rapide, voire précis, mais vous pouvez utiliser l' algorithme Magical Square Root de John Carmack pour résoudre la racine carrée plus rapidement. Vous pourriez probablement facilement tester cela pour tous les entiers 32 bits possibles et valider que vous avez réellement obtenu des résultats corrects, car ce n'est qu'une appoximation. Cependant, maintenant que j'y pense, l'utilisation de doubles est également approximative, donc je ne sais pas comment cela pourrait entrer en jeu.

Kibbee
la source
10
Je crois que l'astuce de Carmack est assez inutile ces jours-ci. L'instruction sqrt intégrée est beaucoup plus rapide qu'auparavant, il est donc préférable de simplement effectuer une racine carrée régulière et de tester si le résultat est un entier. Comme toujours, comparez-le.
jalf
4
Cela rompt à partir de n = 410881, la formule magique de John Carmack renvoie 642.00104, lorsque la racine carrée réelle est 641.
Kip
11
J'ai récemment utilisé l'astuce de Carmack dans un jeu Java et c'était très efficace, donnant une accélération d'environ 40%, donc c'est toujours utile, au moins en Java.
finnw
3
@Robert Fraser Oui + 40% de la fréquence d'images globale. Le jeu avait un système de physique des particules qui occupait presque tous les cycles CPU disponibles, dominé par la fonction racine carrée et la fonction arrondi au plus proche (que j'avais également optimisée en utilisant un hack de
twiddling
5
Le lien est rompu.
Pixar
36

Si vous effectuez un découpage binaire pour essayer de trouver la "bonne" racine carrée, vous pouvez assez facilement détecter si la valeur que vous avez est suffisamment proche pour le dire:

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

Donc, après avoir calculé n^2, les options sont:

  • n^2 = target: terminé, retourne vrai
  • n^2 + 2n + 1 > target > n^2 : vous êtes proche, mais ce n'est pas parfait: retour faux
  • n^2 - 2n + 1 < target < n^2 : idem
  • target < n^2 - 2n + 1 : coupure binaire sur un fond n
  • target > n^2 + 2n + 1 : coupure binaire sur un supérieur n

(Désolé, cela utilise n comme estimation actuelle et targetpour le paramètre. Veuillez vous excuser pour la confusion!)

Je ne sais pas si ce sera plus rapide ou non, mais ça vaut le coup d'essayer.

EDIT: Le cliché binaire n'a pas non plus à prendre toute la gamme d'entiers, (2^x)^2 = 2^(2x)donc une fois que vous avez trouvé le bit le plus haut dans votre cible (ce qui peut être fait avec une astuce de bit-twiddling; j'oublie exactement comment) vous pouvez rapidement obtenir une gamme de réponses potentielles. Attention, une côtelette binaire naïve ne prendra toujours que 31 ou 32 itérations.

Jon Skeet
la source
Mon argent est dans ce genre d'approche. Évitez d'appeler sqrt () car il calcule une racine carrée complète et vous n'avez besoin que des premiers chiffres.
PeterAllenWebb
3
D'un autre côté, si la virgule flottante est effectuée dans une unité FP dédiée, elle peut utiliser toutes sortes de tours amusants. Je ne voudrais pas parier dessus sans benchmark :) (je peux l'essayer ce soir en C #, juste pour voir ...)
Jon Skeet
8
Les sqrts de matériel sont en fait assez rapides de nos jours.
Adam Rosenfield
24

J'ai exécuté ma propre analyse de plusieurs des algorithmes de ce fil et j'ai trouvé de nouveaux résultats. Vous pouvez voir ces anciens résultats dans l'historique des modifications de cette réponse, mais ils ne sont pas précis, car j'ai fait une erreur et perdu du temps à analyser plusieurs algorithmes qui ne sont pas proches. Cependant, tirant des leçons de plusieurs réponses différentes, j'ai maintenant deux algorithmes qui écrasent le "gagnant" de ce fil. Voici l'essentiel que je fais différemment de tout le monde:

// 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 ligne simple, qui ajoute la plupart du temps une ou deux instructions très rapides, simplifie considérablement l' switch-caseinstruction en une instruction if. Cependant, il peut s'ajouter à l'exécution si de nombreux nombres testés ont des facteurs de puissance de deux significatifs.

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 un seul passage comme base
  • DurronTwo - Ma réponse modifiée utilisant la réponse en deux passes (par @JohnnyHeggheim), avec quelques autres légères modifications.

Voici un exemple d'exécution si les nombres sont générés à l'aide 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é uniquement sur le premier million de longs:

 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 voir, DurronTwofait mieux pour les grandes entrées, car il utilise très souvent le tour de magie, mais est encombré par rapport au premier algorithme et Math.sqrtparce que les nombres sont tellement plus petits. Pendant ce temps, le plus simpleDurron est un énorme gagnant car il n'a jamais à diviser par 4 plusieurs fois dans le premier million de nombres.

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

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

Et mon harnais de référence: (Nécessite un étrier Google 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);
    }
}

MISE À JOUR: J'ai créé un nouvel algorithme qui est plus rapide dans certains scénarios, plus lent dans d'autres, j'ai obtenu différents repères basés sur différentes entrées. Si nous calculons le modulo 0xFFFFFF = 3 x 3 x 5 x 7 x 13 x 17 x 241, nous pouvons éliminer 97,82% des nombres qui ne peuvent pas être des carrés. Cela peut être (en quelque sorte) effectué sur une seule 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 + 0x1FFFFFE. Bien sûr, nous devons avoir une table de recherche pour les résidus modulo 0xFFFFFF, qui représente environ un fichier de 3 Mo (dans ce cas, stocké sous forme de nombres décimaux de texte ascii, pas optimal mais clairement améliorable avec a ByteBufferet ainsi de suite. C'est si important. Vous pouvez trouver 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 booleantableau comme celui-ci:

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 Durron(version un) dans chaque essai que j'ai couru.

 0% Scenario{vm=java, trial=0, benchmark=Internet} 40665.77 ns; ?=566.71 ns @ 10 trials
33% Scenario{vm=java, trial=0, benchmark=Durron} 38397.60 ns; ?=784.30 ns @ 10 trials
67% Scenario{vm=java, trial=0, benchmark=DurronThree} 36171.46 ns; ?=693.02 ns @ 10 trials

  benchmark   us linear runtime
   Internet 40.7 ==============================
     Durron 38.4 ============================
DurronThree 36.2 ==========================

vm: java
trial: 0
durron597
la source
3
Une table de recherche géante ne semble pas être une bonne idée. Un échec de cache est plus lent (~ 100 à 150 cycles) que l'instruction sqrt matérielle x86 (~ 20 cycles). En termes de débit, vous pouvez gérer de nombreux manquements au cache en suspens, mais vous supprimez toujours d'autres données utiles. Une énorme table de recherche ne vaudrait la peine que si elle était BEAUCOUP plus rapide que toute autre option, et cette fonction était le facteur majeur dans les performances de l'ensemble de votre programme.
Peter Cordes
1
@SwissFrank: la vérification du carré parfait est-elle la seule chose que fait votre programme? Une table de recherche peut sembler bonne dans un microbenchmark qui l'appelle à plusieurs reprises dans une boucle étroite, mais dans un vrai programme qui a d'autres données dans son ensemble de travail, ce n'est pas bon.
Peter Cordes
1
Un bitmap de bits 0x1FFFFFE prend 4 méga- octets s'il est stocké en tant que bitmap compressé. Un cache L3 atteint sur un ordinateur de bureau Intel moderne a> 40 cycles de latence, et pire sur un gros Xeon; plus longue que la latence sqrt + mul du matériel. S'il est stocké sous forme de carte d' octets avec 1 octet par valeur, il s'agit d'environ 32 Mo; plus grand que le cache L3 de tout sauf un Xeon à plusieurs cœurs où tous les cœurs partagent un énorme cache. Donc, si vos données d'entrée ont une distribution aléatoire uniforme sur une plage d'entrées suffisamment large, vous obtiendrez de nombreux échecs de cache L2 même dans une boucle serrée. (L2 par cœur privé sur Intel est seulement de 256k, avec une latence de ~ 12 cycles.)
Peter Cordes
1
@SwissFrank: Oh, si tout ce que vous faites est de vérifier les racines, alors il y a un potentiel avec un bitmap pour obtenir des hits L3. Je regardais la latence, mais de nombreux échecs peuvent être en vol à la fois, donc le débit est potentiellement bon. OTOH, le sqrtpsdébit SIMD ou même sqrtpd(double précision) n'est pas trop mauvais sur Skylake, mais n'est pas beaucoup mieux que la latence sur les anciens processeurs. Quoi qu'il en soit, 7-cpu.com/cpu/Haswell.html a de bons numéros expérimentaux et des pages pour d'autres CPU. Le guide des microarchives d'Agner Fog pdf contient des numéros de latence de cache pour les uarches Intel et AMD: agner.org/optimize
Peter Cordes
1
L'utilisation de SIMD x86 de Java est un problème, et au moment où vous ajoutez le coût de la conversion int-> fp et fp-> int, il est plausible qu'une bitmap puisse être meilleure. Vous avez besoin de doubleprécision pour éviter d'arrondir un entier en dehors de la plage + -2 ^ 24 (donc un entier 32 bits peut être en dehors de cela), et sqrtpdest plus lent que sqrtpset ne traite que la moitié du nombre d'éléments par instruction (par vecteur SIMD) .
Peter Cordes
18

Il devrait être beaucoup plus rapide d'utiliser la méthode de Newton pour calculer la racine carrée entière , puis de mettre ce nombre au carré et de vérifier, 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 n'êtes intéressé que par 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 nombre ne se termine pas par 1, 4, 7 ou 9, le nombre n'est pas un carré parfait. Cela peut être utilisé comme un moyen rapide d'éliminer 60% de vos entrées avant d'appliquer l'algorithme de racine carrée plus lent.

Bill le lézard
la source
1
La racine numérique est strictement équivalente au calcul au modulo, donc devrait être considérée avec d'autres méthodes modulo ici, comme le mod 16 et le mod 255.
Christian Oudard
1
Êtes-vous sûr que la racine numérique est équivalente à modulo? Cela semble être quelque chose de complètement différent comme expliqué par le lien. Notez que la liste est 1,4,7,9 et non 1,4,5,9.
Fractaly
1
La racine numérique dans le système décimal équivaut à utiliser le modulo 9 (bien dr (n) = 1 + ((n-1) mod 9); donc un léger décalage également). Les nombres 0,1,4,5,9 sont pour modulo 16, et 0, 1, 4, 7 sont pour modulo 9 - qui correspondent à 1, 4, 7, 9 pour racine numérique.
Hans Olsson
16

Je veux que cette fonction fonctionne avec tous les entiers signés 64 bits positifs

Math.sqrt()fonctionne avec des doubles comme paramètres d'entrée, donc vous n'obtiendrez pas de résultats précis pour des entiers supérieurs à 2 ^ 53 .

mrzl
la source
5
J'ai en fait testé la réponse sur tous les carrés parfaits supérieurs à 2 ^ 53, ainsi que tous les nombres de 5 en dessous de chaque carré parfait à 5 au-dessus de chaque carré parfait, et j'obtiens le résultat correct. (l'erreur d'arrondi est corrigée lorsque j'arrondis la réponse sqrt à un long, puis je mets cette valeur au carré et la compare)
Kip
2
@Kip: Je suppose que j'ai prouvé que cela fonctionne .
maaartinus
Les résultats ne sont pas parfaitement précis, mais plus précis que vous ne le pensez. Si nous supposons au moins 15 chiffres précis après la conversion en double et après la racine carrée, c'est beaucoup, car nous n'avons pas besoin de plus de 11: 10 chiffres pour la racine carrée 32 bits et moins de 1 pour une décimale, car les +0,5 tours au plus proche.
mwfearnley
3
Math.sqrt () n'est pas totalement précis, mais ce n'est pas obligatoire. Dans le tout premier article, tst est un entier proche de sqrt (N). Si N n'est pas un carré, alors tst * tst! = N, quelle que soit la valeur de tst. Si N est un carré parfait, alors sqrt (N) <2 ^ 32, et tant que sqrt (N) est calculé avec une erreur <0,5, tout va bien.
gnasher729
13

Pour mémoire, une autre approche consiste à utiliser la décomposition principale. Si chaque facteur de la décomposition est pair, alors le nombre est un carré parfait. Donc, ce que vous voulez, c'est voir si un nombre peut être décomposé comme un produit de carrés de nombres premiers. Bien sûr, vous n'avez pas besoin d'obtenir une telle décomposition, juste pour voir si elle existe.

Construisez d'abord un tableau de carrés de nombres premiers inférieurs à 2 ^ 32. C'est beaucoup plus petit qu'une table de tous les nombres entiers jusqu'à cette limite.

Une solution serait alors comme ceci:

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. Il vérifie à chaque étape que le carré d'un nombre premier divise le nombre entré. Si c'est le cas, il divise le nombre par le carré aussi longtemps que possible, pour retirer ce carré de la décomposition principale. Si par ce processus, nous arrivions à 1, alors le nombre d'entrée était une décomposition du carré des nombres premiers. Si le carré devient plus grand que le nombre lui-même, il n'y a aucun moyen que ce carré, ou des carrés plus grands, puisse le diviser, donc le nombre ne peut pas être une décomposition de carrés de nombres premiers.

Étant donné le sqrt de nos jours fait en matériel et la nécessité de calculer des 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 sur 2 ^ 54, comme le dit mrzl dans sa réponse.

Cyrille Ka
la source
1
la division entière est plus lente que FP sqrt sur le matériel actuel. Cette idée n'a aucune chance. >. <Même en 2008, le sqrtsddébit de Core2 est de un par 6-58c. C'est idivun par 12-36 cycles. (latences similaires aux débits: aucune des unités n'est en pipeline).
Peter Cordes
sqrt n'a pas besoin d'être parfaitement précis. C'est pourquoi vous vérifiez en mettant au carré le résultat et en effectuant une comparaison d'entier pour décider si l'entier d'entrée avait un sqrt entier exact.
Peter Cordes
11

Il a été souligné que les derniers dchiffres d'un carré parfait ne peuvent prendre que certaines valeurs. Les derniers dchiffres (en base b) d'un nombre nsont les mêmes que le reste lorsqu'il nest divisé par bd, c'est-à-dire. en notation C n % pow(b, d).

Cela peut être généralisé à n'importe quel module m, c'est-à-dire. n % mpeut être utilisé pour exclure un certain pourcentage des nombres d'être des carrés parfaits. Le module que vous utilisez actuellement est de 64, ce qui permet 12, c'est-à-dire. 19% des restes, comme des carrés possibles. Avec un peu de codage j'ai trouvé le module 110880, qui ne permet que 2016, c'est à dire. 1,8% des restes comme carrés possibles. Ainsi, en fonction du coût d'une opération de module (c.-à-d. Division) et d'une recherche de table par rapport à une racine carrée sur votre machine, l'utilisation de ce module peut être plus rapide.

Soit dit en passant, si Java a un moyen de stocker un tableau compact de bits pour la table de recherche, ne l'utilisez pas. 110880 Les mots 32 bits ne consomment pas beaucoup de RAM de nos jours et la récupération d'un mot machine va être plus rapide que la récupération d'un seul bit.

Hugh Allen
la source
Agréable. Avez-vous calculé cela algébriquement ou par essais et erreurs? Je peux voir pourquoi il est si efficace - beaucoup de collisions entre des carrés parfaits, par exemple 333 ^ 2% 110880 == 3 ^ 2, 334 ^ 2% 110880 == 26 ^ 2, 338 ^ 2% 110880 == 58 ^ 2 .. .
finnw
IIRC c'était la force brute, mais notez que 110880 = 2 ^ 5 * 3 ^ 2 * 5 * 7 * 11, ce qui donne 6 * 3 * 2 * 2 * 2 - 1 = 143 diviseurs propres.
Hugh Allen
J'ai trouvé qu'en raison des limites de la recherche, 44352 fonctionne mieux, avec un taux de réussite de 2,6%. Au moins dans ma mise en œuvre.
Fractaly
1
La division entière ( idiv) a un coût égal ou pire à FP sqrt ( sqrtsd) sur le matériel x86 actuel. En outre, vous n'êtes pas du tout d'accord pour éviter les champs de bits. Le taux de réussite du cache sera bien meilleur avec un champ binaire, et tester un bit dans un champ binaire n'est qu'une ou deux instructions plus simples que tester un octet entier. (Pour les tables minuscules qui tiennent dans le cache même en tant que non-champs de bits, un tableau d'octets serait préférable, pas des entiers de 32 bits. X86 a un accès à un octet avec une vitesse égale à 32 bits dword.)
Peter Cordes
11

Un problème entier mérite une solution entière. Donc

Effectuez une recherche binaire sur les entiers (non négatifs) pour trouver le plus grand entier t tel que t**2 <= n. Testez ensuite si r**2 = nexactement. Cela prend du temps O (log n).

Si vous ne savez pas comment rechercher binaire les entiers positifs parce que l'ensemble est illimité, c'est facile. 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 faire une recherche binaire standard.

Colonel Panic
la source
En fait, le temps serait au moins O((log n)^2)parce que la multiplication n'est pas à temps constant mais a en fait une limite inférieure de O(log n), ce qui devient apparent lorsque l'on travaille avec de grands nombres multi-précision. Mais la portée de ce wiki semble être de 64 bits, donc c'est peut-être nbd.
10

La simplification suivante de la solution de maaartinus semble réduire de quelques points le temps d'exécution, mais je ne suis pas assez bon en analyse comparative 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 vaudrait la peine de vérifier comment omettre le premier test,

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

affecterait les performances.

dfeuer
la source
2
Les résultats sont ici . Supprimer le premier test est mauvais car il résout la plupart des cas à peu de frais. La source est dans ma réponse (mise à jour).
maaartinus
9

Pour les performances, vous devez très souvent faire quelques 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 piratage de Carmack, sinon utilisez une autre méthode décrite dans les réponses ici.

BobbyShaftoe
la source
J'ai également intégré votre suggestion dans la solution. Aussi, belle poignée. :)
Kip
8

C'est l'implémentation Java la plus rapide que j'ai pu trouver, en utilisant une combinaison de techniques suggérées par d'autres dans ce fil.

  • Test Mod-256
  • Test mod-3465 inexact (évite la division entière au prix de certains 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 mod-255 supplémentaire
  • Diviser la valeur d'entrée par des puissances de 4
  • Racine carrée inverse rapide (pour travailler pour des valeurs élevées de N, il faut 3 itérations, assez pour 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;
        }
    }

}
finnw
la source
7

Vous devez vous débarrasser de la partie à 2 puissances de N dès le début.

2nd Edit L'expression magique pour m ci-dessous devrait être

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

et pas comme écrit

Fin du 2e montage

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 du 1er montage

Continuez maintenant comme d'habitude. De cette façon, au moment où vous arrivez à la partie à virgule flottante, vous vous êtes déjà débarrassé de tous les nombres dont la partie à 2 puissances est impaire (environ la moitié), puis vous ne considérez que 1/8 de ce qui reste. C'est-à-dire que vous exécutez la partie à virgule flottante sur 6% des nombres.

David Lehavi
la source
7

Le projet Euler est mentionné dans les balises et de nombreux problèmes nécessitent une vérification des numéros >> 2^64. La plupart des optimisations mentionnées ci-dessus ne fonctionnent pas facilement lorsque vous travaillez avec 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 des entiers. Le problème était que les carrés exacts n^2convergeaient au (n-1)lieu de nparce que n^2-1 = (n-1)(n+1)et l'erreur finale était juste une étape en dessous du diviseur final et l'algorithme s'est terminé. Il a été facile à corriger en ajoutant un à l'argument d'origine avant de calculer l'erreur. (Ajoutez deux pour les racines cubiques, 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 (pas de correction) dans la méthode de Newton sera nulle. Une simple modification vous permet également de calculer rapidement floor(sqrt(x))au lieu de l'entier le plus proche. C'est pratique avec plusieurs problèmes d'Euler.

bgiles
la source
1
Je pensais la même chose à propos de ces algorithmes ne se traduisant pas bien en tampons multi-précision. Alors j'ai pensé que je resterais ici ... J'ai trouvé en fait un test d'équerrabilité probabiliste avec une meilleure complexité asymptotique pour des nombres énormes ..... où les applications de la théorie des nombres ne se trouvent pas rarement. Pas familier avec Project Euler ... semble intéressant.
6

Il s'agit d'un remaniement de la décimale au binaire de l'ancien algorithme de la calculatrice Marchant (désolé, je n'ai pas de référence), en Ruby, adapté spécifiquement pour 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 résumé de quelque chose de similaire (s'il vous plaît ne me votez pas pour le style de codage / les odeurs ou les O / O maladroits - c'est l'algorithme qui compte, et 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;
};
Brent.Longborough
la source
Le nombre d'itérations ressemble à O (ln n), où n est la longueur en bits de v, donc je doute que cela économise beaucoup pour un v plus grand. Le virgule flottante sqrt est lente, peut-être 100-200 cycles, mais les mathématiques entières ne le sont pas libre non plus. Une douzaine d'itérations avec 15 cycles chacune, et ce serait un lavage. Pourtant, +1 pour être intéressant.
Tadmas
En fait, je pense que les ajouts et les soustractions peuvent être effectués par XOR.
Brent.Longborough
C'était un commentaire idiot - seul l'ajout peut être fait par un XOR; la soustraction est arithmétique.
Brent.Longborough
1
Y a-t-il vraiment une différence substantielle entre le temps d'exécution de XOR et l'addition?
Tadmas
1
@Tadmas: probablement pas assez pour enfreindre la règle "optimiser plus tard". (:-)
Brent.Longborough
6

L'appel sqrt n'est pas parfaitement précis, comme cela a été mentionné, mais il est intéressant et instructif qu'il n'épuise pas les autres réponses en termes de vitesse. Après tout, la séquence d'instructions du langage d'assemblage pour un sqrt est minuscule. Intel a une instruction matérielle, qui n'est pas utilisée par Java, je crois, car elle n'est pas conforme à IEEE.

Alors pourquoi est-ce lent? Parce que Java appelle en fait une routine C via JNI, et il est en fait plus lent de le faire que d'appeler un sous-programme Java, lui-même plus lent que de le faire en ligne. C'est très ennuyeux, et Java aurait dû trouver une meilleure solution, c'est-à-dire intégrer des appels de bibliothèque à virgule flottante si nécessaire. Tant pis.

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, est un simple hack, une extension des tests de cas spéciaux suggérés par A. Rex. Utilisez une seule valeur longue comme tableau de bits, qui n'est pas vérifiée. 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 environ 1/3 du temps sur ma machine core2 duo. Je soupçonne que de nouveaux ajustements dans le même sens pourraient réduire davantage le temps en moyenne, mais chaque fois que vous vérifiez, vous échangez plus de tests pour plus d'élimination, vous ne pouvez donc pas aller trop loin sur cette route.

Certainement, plutôt que d'avoir un test séparé pour les négatifs, vous pouvez vérifier les 6 bits les plus élevés de la même manière.

Notez que tout ce que je fais est d'éliminer les carrés possibles, mais quand j'ai un cas potentiel, je dois appeler l'isPerfectSquare original et en ligne.

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 non signé depuis longtemps, donc puisque vous êtes signé, vous devez utiliser l'opérateur >>>.

Il n'y a pas de besoin intrinsèque de vérifier le tableau, mais l'optimiseur de Java doit comprendre ce genre de choses assez rapidement, donc je ne leur en veux pas.

hydrodog
la source
3
Je parie que vous vous trompez deux fois. 1. Intel sqrt est conforme à IEEE. Les seules instructions non conformes sont les instructions goniométriques pour les arguments de lange. 2. Java utilise intrinsèque pour Math.sqrt, pas de JNI .
maaartinus
1
N'as-tu pas oublié d'utiliser pp2? Je comprends que pp1c'est utilisé pour tester les six bits les moins significatifs, mais je ne pense pas que tester les six bits suivants ait un sens.
maaartinus
6

J'aime l'idée d'utiliser une méthode presque correcte sur certaines entrées. Voici une version avec un "offset" plus élevé. Le code semble fonctionner et passe mon cas de test simple.

Remplacez simplement 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);
}
Jonny Heggheim
la source
6

Compte tenu de la longueur générale des bits (bien que j'aie utilisé un type spécifique ici), j'ai essayé de concevoir un algo simpliste comme ci-dessous. Un contrôle simple et évident pour 0,1,2 ou <0 est requis au départ. Ce qui suit est simple en ce sens qu'il n'essaie pas d'utiliser les fonctions mathématiques existantes. La plupart des opérateurs peuvent être remplacés par des opérateurs bit à bit. Je n'ai cependant pas testé de données de référence. Je ne suis ni un expert en mathématiques ni en conception d'algorithmes informatiques en particulier, j'aimerais bien vous voir signaler un problème Je sais qu'il y a beaucoup de chances d'amélioration là-bas.

int main()
{
    unsigned int c1=0 ,c2 = 0;  
    unsigned int x = 0;  
    unsigned int p = 0;  
    int k1 = 0;  
    scanf("%d",&p);  
    if(p % 2 == 0) {  
        x = p/2; 
    }  
    else {  
        x = (p/2) +1;  
    }  
    while(x) 
    {
        if((x*x) > p) {  
            c1 = x;  
            x = x/2; 
        }else {  
            c2 = x;  
            break;  
        }  
    }  
    if((p%2) != 0)  
        c2++;

    while(c2 < c1) 
    {  
        if((c2 * c2 ) == p) {  
            k1 = 1;  
            break;  
        }  
        c2++; 
    }  
    if(k1)  
        printf("\n Perfect square for %d", c2);  
    else  
        printf("\n Not perfect but nearest to :%d :", c2);  
    return 0;  
}
nabam serbang
la source
@Kip: Un problème avec mon navigateur.
nabam serbang
1
Vous avez besoin d'un retrait.
Steve Kuo
5

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, jusqu'à 5 / 6ème des entrées peuvent être éliminées. En fait, j'ai conçu cela pour implémenter l'algorithme de factorisation de Fermat, et c'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 de 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

  • a est de la forme (3 << 2k) - 1
  • b est de la forme (2 << 2k)
  • c est de la forme (2 << 2k + 2) - 1
  • d est de la forme (2 << 2k - 1) * 10

    Il teste d'abord s'il a un résidu carré avec des modules de puissance de deux, puis il teste en fonction d'un module final, puis il utilise le Math.sqrt pour faire un test final. Je suis venu avec l'idée du poste supérieur, et j'ai essayé de la développer. J'apprécie tout commentaire ou suggestion.

    Mise à jour: En utilisant le test par 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.

    • Fractaly
    la source
    2

    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 solutionfonction du nombre de chiffres de number:

    • numbera 1 chiffre: solutiondans la plage = 1 - 4
    • numbera 2 chiffres: solutiondans la plage = 3 - 10
    • numbera 3 chiffres: solutiondans la plage = 10 - 40
    • numbera 4 chiffres: solutiondans la plage = 30 - 100
    • numbera 5 chiffres: solutiondans la plage = 100 - 400

    Remarquez la répétition?

    Vous pouvez utiliser cette plage dans une approche de recherche binaire pour voir s'il existe un solutionpour 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 sur la façon de l'utiliser.

    long number =  1234567;
long square = number * number;
SquareRootChecker squareRootChecker = new SquareRootChecker(square);
System.out.println(square + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677489: true"

long notSquare = square + 1;
squareRootChecker = new SquareRootChecker(notSquare);
System.out.println(notSquare + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677490: false"
    MWB
    la source
    2
    J'adore le concept, mais je voudrais souligner poliment un défaut majeur: les nombres sont en base 2 binaire. La conversion de la base 2 en base 10 via toStringest une opération incroyablement coûteuse par rapport aux opérateurs au niveau du bit. Ainsi, pour satisfaire l'objectif de la question - les performances - vous devez utiliser des opérateurs au niveau du bit au lieu des chaînes de base 10. Encore une fois, j'aime vraiment votre concept. Néanmoins, votre implémentation (telle qu'elle est actuellement) est de loin la plus lente de toutes les solutions possibles affichées pour la question.
    Jack Giffin
    1

    Si la vitesse est un problème, pourquoi ne pas partitionner l'ensemble des entrées les plus couramment utilisées et leurs valeurs dans une table de recherche, puis faire l'algorithme magique optimisé que vous avez trouvé pour les cas exceptionnels?

    Elijah
    la source
    Le problème est qu'il n'y a pas "d'ensemble d'entrées couramment utilisé" - généralement j'itère dans une liste, donc je n'utiliserai pas les mêmes entrées deux fois.
    Kip
    1

    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 des entiers java 32 bits et produire suffisamment de données pour vérifier les 16 derniers bits du nombre - c'est 2048 valeurs int hexadécimales.

    ...

    D'accord. Soit j'ai rencontré 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: élidé pour de mauvaises performances dans prettify.js; voir l'historique des révisions pour voir.)

    paulmurray
    la source
    1

    Méthode de Newton avec arithmétique entière

    Si vous souhaitez éviter les opérations non entières, vous pouvez utiliser la méthode ci-dessous. Il utilise essentiellement la méthode de Newton modifiée pour l'arithmétique entière.

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

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

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

    Cette implémentation ne peut rivaliser avec les solutions qui utilisent Math.sqrt. Cependant, ses performances peuvent être améliorées en utilisant les mécanismes de filtrage décrits dans certains des autres articles.

    aventurine
    la source
    1

    Le calcul des racines carrées par la méthode de Newton est terriblement rapide ... à condition que la valeur de départ soit raisonnable. Cependant, il n'y a pas de valeur de départ raisonnable et, en pratique, nous terminons par un comportement de bissection et de log (2 ^ 64).
    Pour être vraiment rapide, nous avons besoin d'un moyen rapide d'atteindre une valeur de départ raisonnable, et cela signifie que nous devons descendre dans le langage machine. Si un processeur fournit une instruction comme POPCNT dans le Pentium, cela compte les zéros de tête que nous pouvons utiliser pour avoir une valeur de départ avec la moitié des bits significatifs. Avec soin, nous pouvons trouver un nombre fixe d'étapes de Newton qui suffira toujours. (Ainsi, il est inutile de boucler et d'avoir une exécution très rapide.)

    Une deuxième solution passe par la fonction de virgule flottante, qui peut avoir un calcul sqrt rapide (comme le coprocesseur i87.) Même une excursion via exp () et log () peut être plus rapide que Newton dégénéré en recherche binaire. Il y a un aspect délicat à cela, une analyse dépendante du processeur de quoi et si un raffinement par la suite est nécessaire.

    Une troisième solution résout un problème légèrement différent, mais mérite d'être mentionnée car la situation est décrite dans la question. Si vous souhaitez calculer un grand nombre de racines carrées pour des nombres légèrement différents, vous pouvez utiliser l'itération de Newton, si vous ne réinitialisez jamais la valeur de départ, mais laissez-la simplement là où le calcul précédent s'était arrêté. Je l'ai utilisé avec succès dans au moins un problème Euler.

    Albert van der Horst
    la source
    Obtenir une bonne estimation n'est pas trop difficile. Vous pouvez utiliser le nombre de chiffres du nombre pour estimer une limite inférieure et supérieure pour la solution. Voir aussi ma réponse où je propose une solution diviser pour mieux régner.
    MWB
    Quelle est la différence entre POPCNT et compter le nombre de chiffres? Sauf que vous pouvez faire POPCNT en une nanoseconde.
    Albert van der Horst
    1

    Racine carrée d'un nombre, étant donné que le nombre est un carré parfait.

    La complexité est log (n)

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

public static int calculateSquareRoot(int number) {

    int sum=1;
    int count =1;
    int squareRoot=1;
    while(sum<number) {
        count+=2;
        sum+=count;
        squareRoot++;
    }
    return squareRoot;
}
    Sajjad Ali Vayani
    la source
    0

    Si vous voulez de la vitesse, étant donné que vos entiers sont de taille finie, je soupçonne que le moyen le plus rapide impliquerait (a) de partitionner les paramètres par taille (par exemple en catégories par le plus grand ensemble de bits), puis de vérifier la valeur par rapport à un tableau de carrés parfaits dans cette plage.

    Belestial M Belette
    la source
    2
    Il y a 2 ^ 32 carrés parfaits dans la gamme d'un long. Ce tableau serait énorme. De plus, l'avantage de calculer la valeur par rapport à un accès à la mémoire pourrait être énorme.
    PeterAllenWebb
    Oh non, il n'y en a pas, il y en a 2 ^ 16. 2 ^ 32 est 2 ^ 16 au carré. Il y en a 2 ^ 16.
    Celestial M Weasel
    3
    oui, mais la plage d'un long est de 64 bits, pas de 32 bits. sqrt (2 ^ 64) = 2 ^ 32. (j'ignore le bit de signe pour rendre les calculs un peu plus faciles ... il y a en fait (long) (2 ^ 31.5) = 3037000499 carrés parfaits)
    Kip
    0

    En ce qui concerne la méthode Carmac, il semble qu'il serait assez facile de répéter une fois de plus, ce qui devrait doubler le nombre de chiffres de précision. C'est, après tout, une méthode itérative extrêmement tronquée - celle de Newton, avec une très bonne première supposition.

    Concernant votre meilleur actuel, je vois deux micro-optimisations:

    • déplacer le chèque contre 0 après le chèque en utilisant le mod255
    • réorganiser les pouvoirs de division de quatre pour sauter tous les contrôles pour le cas habituel (75%).

    C'est à dire:

    // 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 pourrait être un simple

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

    Évidemment, il serait intéressant de savoir combien de numéros sont abattus à chaque point de contrôle - je doute que les contrôles soient vraiment indépendants, ce qui rend les choses délicates.

    Ben
    la source