tableaux - racine carré java




Le moyen le plus rapide pour déterminer si la racine carrée d'un entier est un nombre entier (20)

Je cherche le moyen le plus rapide de déterminer si une valeur long est un carré parfait (ie sa racine carrée est un autre entier). Je l'ai fait en toute simplicité, en utilisant la fonction Math.sqrt () intégrée, mais je me demande s'il existe un moyen de le faire plus rapidement en vous limitant au domaine entier uniquement. Maintenir une table de consultation est impratique (puisqu'il y a environ 2 31.5 entiers dont le carré est inférieur à 2 63 ).

Voici la façon très simple et directe de le faire 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;
}

Notes: 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 une partie du défi consiste à faire tous les algorithmes en moins d'une minute, et cette fonction devra être appelée des millions de fois dans certains problèmes.

Mise à jour 2 : Une nouvelle solution mise en ligne par A. Rex s'est avérée encore plus rapide. Au cours d'un passage sur le premier milliard d'entiers, la solution ne demandait que 34% du temps que la solution originale utilisait. Alors que le hack de John Carmack est un peu meilleur pour de petites valeurs de n , le bénéfice par rapport à cette solution est assez faible.

Voici la solution A. Rex, convertie en Java:

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

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

  // Divide out powers of 4 using binary search
  if((n & 0xffffffffL) == 0)
      n >>= 32;
  if((n & 0xffffL) == 0)
      n >>= 16;
  if((n & 0xffL) == 0)
      n >>= 8;
  if((n & 0xfL) == 0)
      n >>= 4;
  if((n & 0x3L) == 0)
      n >>= 2;

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

  // Compute sqrt using something like Hensel's lemma
  long r, t, z;
  r = start[(int)((n >> 3) & 0x3ffL)];
  do {
    z = n - r * r;
    if( z == 0 )
      return true;
    if( z < 0 )
      return false;
    t = z & (-z);
    r += (z & t) >> 1;
    if( r > (t  >> 1) )
    r = t - r;
  } while( t <= (1L << 33) );
  return false;
}

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

private static int[] start =
{
  1,3,1769,5,1937,1741,7,1451,479,157,9,91,945,659,1817,11,
  1983,707,1321,1211,1071,13,1479,405,415,1501,1609,741,15,339,1703,203,
  129,1411,873,1669,17,1715,1145,1835,351,1251,887,1573,975,19,1127,395,
  1855,1981,425,453,1105,653,327,21,287,93,713,1691,1935,301,551,587,
  257,1277,23,763,1903,1075,1799,1877,223,1437,1783,859,1201,621,25,779,
  1727,573,471,1979,815,1293,825,363,159,1315,183,27,241,941,601,971,
  385,131,919,901,273,435,647,1493,95,29,1417,805,719,1261,1177,1163,
  1599,835,1367,315,1361,1933,1977,747,31,1373,1079,1637,1679,1581,1753,1355,
  513,1539,1815,1531,1647,205,505,1109,33,1379,521,1627,1457,1901,1767,1547,
  1471,1853,1833,1349,559,1523,967,1131,97,35,1975,795,497,1875,1191,1739,
  641,1149,1385,133,529,845,1657,725,161,1309,375,37,463,1555,615,1931,
  1343,445,937,1083,1617,883,185,1515,225,1443,1225,869,1423,1235,39,1973,
  769,259,489,1797,1391,1485,1287,341,289,99,1271,1701,1713,915,537,1781,
  1215,963,41,581,303,243,1337,1899,353,1245,329,1563,753,595,1113,1589,
  897,1667,407,635,785,1971,135,43,417,1507,1929,731,207,275,1689,1397,
  1087,1725,855,1851,1873,397,1607,1813,481,163,567,101,1167,45,1831,1205,
  1025,1021,1303,1029,1135,1331,1017,427,545,1181,1033,933,1969,365,1255,1013,
  959,317,1751,187,47,1037,455,1429,609,1571,1463,1765,1009,685,679,821,
  1153,387,1897,1403,1041,691,1927,811,673,227,137,1499,49,1005,103,629,
  831,1091,1449,1477,1967,1677,697,1045,737,1117,1737,667,911,1325,473,437,
  1281,1795,1001,261,879,51,775,1195,801,1635,759,165,1871,1645,1049,245,
  703,1597,553,955,209,1779,1849,661,865,291,841,997,1265,1965,1625,53,
  1409,893,105,1925,1297,589,377,1579,929,1053,1655,1829,305,1811,1895,139,
  575,189,343,709,1711,1139,1095,277,993,1699,55,1435,655,1491,1319,331,
  1537,515,791,507,623,1229,1529,1963,1057,355,1545,603,1615,1171,743,523,
  447,1219,1239,1723,465,499,57,107,1121,989,951,229,1521,851,167,715,
  1665,1923,1687,1157,1553,1869,1415,1749,1185,1763,649,1061,561,531,409,907,
  319,1469,1961,59,1455,141,1209,491,1249,419,1847,1893,399,211,985,1099,
  1793,765,1513,1275,367,1587,263,1365,1313,925,247,1371,1359,109,1561,1291,
  191,61,1065,1605,721,781,1735,875,1377,1827,1353,539,1777,429,1959,1483,
  1921,643,617,389,1809,947,889,981,1441,483,1143,293,817,749,1383,1675,
  63,1347,169,827,1199,1421,583,1259,1505,861,457,1125,143,1069,807,1867,
  2047,2045,279,2043,111,307,2041,597,1569,1891,2039,1957,1103,1389,231,2037,
  65,1341,727,837,977,2035,569,1643,1633,547,439,1307,2033,1709,345,1845,
  1919,637,1175,379,2031,333,903,213,1697,797,1161,475,1073,2029,921,1653,
  193,67,1623,1595,943,1395,1721,2027,1761,1955,1335,357,113,1747,1497,1461,
  1791,771,2025,1285,145,973,249,171,1825,611,265,1189,847,1427,2023,1269,
  321,1475,1577,69,1233,755,1223,1685,1889,733,1865,2021,1807,1107,1447,1077,
  1663,1917,1129,1147,1775,1613,1401,555,1953,2019,631,1243,1329,787,871,885,
  449,1213,681,1733,687,115,71,1301,2017,675,969,411,369,467,295,693,
  1535,509,233,517,401,1843,1543,939,2015,669,1527,421,591,147,281,501,
  577,195,215,699,1489,525,1081,917,1951,2013,73,1253,1551,173,857,309,
  1407,899,663,1915,1519,1203,391,1323,1887,739,1673,2011,1585,493,1433,117,
  705,1603,1111,965,431,1165,1863,533,1823,605,823,1179,625,813,2009,75,
  1279,1789,1559,251,657,563,761,1707,1759,1949,777,347,335,1133,1511,267,
  833,1085,2007,1467,1745,1805,711,149,1695,803,1719,485,1295,1453,935,459,
  1151,381,1641,1413,1263,77,1913,2005,1631,541,119,1317,1841,1773,359,651,
  961,323,1193,197,175,1651,441,235,1567,1885,1481,1947,881,2003,217,843,
  1023,1027,745,1019,913,717,1031,1621,1503,867,1015,1115,79,1683,793,1035,
  1089,1731,297,1861,2001,1011,1593,619,1439,477,585,283,1039,1363,1369,1227,
  895,1661,151,645,1007,1357,121,1237,1375,1821,1911,549,1999,1043,1945,1419,
  1217,957,599,571,81,371,1351,1003,1311,931,311,1381,1137,723,1575,1611,
  767,253,1047,1787,1169,1997,1273,853,1247,413,1289,1883,177,403,999,1803,
  1345,451,1495,1093,1839,269,199,1387,1183,1757,1207,1051,783,83,423,1995,
  639,1155,1943,123,751,1459,1671,469,1119,995,393,219,1743,237,153,1909,
  1473,1859,1705,1339,337,909,953,1771,1055,349,1993,613,1393,557,729,1717,
  511,1533,1257,1541,1425,819,519,85,991,1693,503,1445,433,877,1305,1525,
  1601,829,809,325,1583,1549,1991,1941,927,1059,1097,1819,527,1197,1881,1333,
  383,125,361,891,495,179,633,299,863,285,1399,987,1487,1517,1639,1141,
  1729,579,87,1989,593,1907,839,1557,799,1629,201,155,1649,1837,1063,949,
  255,1283,535,773,1681,461,1785,683,735,1123,1801,677,689,1939,487,757,
  1857,1987,983,443,1327,1267,313,1173,671,221,695,1509,271,1619,89,565,
  127,1405,1431,1659,239,1101,1159,1067,607,1565,905,1755,1231,1299,665,373,
  1985,701,1879,1221,849,627,1465,789,543,1187,1591,923,1905,979,1241,181
};

Mise à jour : j'ai essayé les différentes solutions présentées ci-dessous.

  • Après des tests exhaustifs, j'ai trouvé qu'ajouter 0.5 au résultat de Math.sqrt () n'est pas nécessaire, du moins pas sur ma machine.
  • Le hack de John Carmack était plus rapide, mais il donnait des résultats incorrects à partir de n = 410881. Cependant, comme suggéré par BobbyShaftoe , nous pouvons utiliser le hack de Carmack pour n <410881.
  • La méthode de Newton était un peu plus lente que Math.sqrt() . C'est probablement parce que Math.sqrt() utilise quelque chose de similaire à la méthode de Newton, mais implémenté dans le matériel donc c'est beaucoup plus rapide qu'en Java. De plus, la méthode de Newton exigeait toujours l'utilisation de doubles.
  • Une méthode modifiée de Newton, qui utilisait quelques astuces pour que seules les mathématiques entières soient impliquées, nécessitait des hacks pour éviter les débordements (je veux que cette fonction fonctionne avec tous les entiers signés positifs de 64 bits), et elle était encore plus lente que Math.sqrt() .
  • Chop binaire était encore plus lent. Cela a du sens car le cliché binaire nécessitera en moyenne 16 passages pour trouver la racine carrée d'un nombre de 64 bits.

La suggestion qui a montré des améliorations a été faite par John D. Cook . Vous pouvez observer que le dernier chiffre hexadécimal (les 4 derniers bits) d'un carré parfait doit être 0, 1, 4 ou 9. Cela signifie que 75% des nombres peuvent être immédiatement éliminés comme des carrés possibles. La mise en œuvre de cette solution a entraîné une réduction d'environ 50% du temps d'exécution.

Travaillant à partir de la suggestion de John, j'ai étudié les propriétés des n derniers bits d'un carré parfait. En analysant les 6 derniers bits, j'ai trouvé que seulement 12 des 64 valeurs sont possibles pour les 6 derniers bits. Cela signifie que 81% des valeurs peuvent être éliminées sans utiliser de maths. La mise en œuvre de cette solution a donné une réduction supplémentaire de 8% du temps d'exécution (par rapport à mon algorithme d'origine). L'analyse de plus de 6 bits donne une liste de bits de fin possibles qui est trop grande pour être pratique.

Voici le code que j'ai utilisé, qui s'exécute dans 42% du temps requis par l'algorithme d'origine (basé sur un passage sur les 100 premiers millions d'entiers). Pour les valeurs de n inférieures à 410881, il s'exécute dans seulement 29% du temps requis par l'algorithme original.

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

  switch((int)(n & 0x3F))
  {
  case 0x00: case 0x01: case 0x04: case 0x09: case 0x10: case 0x11:
  case 0x19: case 0x21: case 0x24: case 0x29: case 0x31: case 0x39:
    long sqrt;
    if(n < 410881L)
    {
      //John Carmack hack, converted to Java.
      // See: http://www.codemaestro.com/reviews/9
      int i;
      float x2, y;

      x2 = n * 0.5F;
      y  = n;
      i  = Float.floatToRawIntBits(y);
      i  = 0x5f3759df - ( i >> 1 );
      y  = Float.intBitsToFloat(i);
      y  = y * ( 1.5F - ( x2 * y * y ) );

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

  default:
    return false;
  }
}

Notes :

  • Selon les tests de John, l'utilisation de or est plus rapide en C ++ qu'en utilisant un switch , mais en Java et en C # il ne semble y avoir aucune différence entre or et switch .
  • J'ai également essayé de faire une table de recherche (comme un tableau statique privé de 64 valeurs booléennes). Alors à la place de switch ou d'instruction, je dirais simplement if(lookup[(int)(n&0x3F)]) { test } else return false; . À ma grande surprise, c'était (légèrement) plus lent. Je ne sais pas pourquoi. C'est parce que les limites des tableaux sont vérifiées en Java .

I want this function to work with all positive 64-bit signed integers

Math.sqrt() works with doubles as input parameters, so you won't get accurate results for integers bigger than 2^53 .


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

Mon approche est triple:

  1. Tout d'abord, filtrer les réponses évidentes. Cela inclut les nombres négatifs et en regardant les 4 derniers bits. (J'ai trouvé en regardant les six derniers n'a pas aidé.) Je réponds aussi oui pour 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;
  2. Ensuite, vérifiez s'il s'agit d'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, dans mon expérience, appeler l'opérateur modulo (%) coûte plus cher que le bénéfice obtenu, donc j'utilise des astuces 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 consistant à lire des octets individuels à partir d'un mot, mais seulement à l'aide de bit-et-et de 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 ce soit applicable directement, mais cela fonctionne avec quelques modifications.) Avant cela, je divise toutes les puissances 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é, si cela 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 "actuelle" de x; chaque racine carrée est précise modulo une puissance plus grande et 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 de -r. Ceci est vrai même pour les nombres modulo, mais attention, modulo certains nombres, les choses peuvent avoir plus de 2 racines carrées, notamment celles de 2. Parce que notre racine carrée réelle est inférieure à 2 ^ 32, nous pouvons alors 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 façons: valeur de départ précalculée (équivalente à ~ 10 itérations de la boucle), sortie plus précoce de la boucle, et saut de quelques valeurs de t. Pour la dernière partie, je regarde z = r - x * x , et définissons t comme la plus grande puissance de 2 en divisant z avec un peu de ruse. Cela me permet d'ignorer des valeurs 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 la racine carrée "la plus petite positive" 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;
}

"I'm looking for the fastest way to determine if a long value is a perfect square (ie its square root is another integer)."

The answers are impressive, but I failed to see a simple check :

check whether the first number on the right of the long it a member of the set (0,1,4,5,6,9) . If it is not, then it cannot possibly be a 'perfect square' .

par exemple.

4567 - cannot be a perfect square.


An integer problem deserves an integer solution. Thus

Do binary search on the (non-negative) integers to find the greatest integer t such that t**2 <= n . Then test whether r**2 = n exactly. This takes time O(log n).

If you don't know how to binary search the positive integers because the set is unbounded, it's easy. You starting by computing your increasing function f (above f(t) = t**2 - n ) on powers of two. When you see it turn positive, you've found an upper bound. Then you can do standard binary search.


Don't know about fastest, but the simplest is to take the square root in the normal fashion, multiply the result by itself, and see if it matches your original value.

Since we're talking integers here, the fasted would probably involve a collection where you can just make a lookup.


For performance, you very often have to do some compromsies. Others have expressed various methods, however, you noted Carmack's hack was faster up to certain values of N. Then, you should check the "n" and if it is less than that number N, use Carmack's hack, else use some other method described in the answers here.


I checked all of the possible results when the last n bits of a square is observed. By successively examining more bits, up to 5/6th of inputs can be eliminated. I actually designed this to implement Fermat's Factorization algorithm, and it is very fast there.

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

The last bit of pseudocode can be used to extend the tests to eliminate more values. The tests above are for k = 0, 1, 2, 3

  • a is of the form (3 << 2k) - 1
  • b is of the form (2 << 2k)
  • c is of the form (2 << 2k + 2) - 1
  • d is of the form (2 << 2k - 1) * 10

    It first tests whether it has a square residual with moduli of power of two, then it tests based on a final modulus, then it uses the Math.sqrt to do a final test. I came up with the idea from the top post, and attempted to extend upon it. I appreciate any comments or suggestions.

    Update: Using the test by a modulus, (modSq) and a modulus base of 44352, my test runs in 96% of the time of the one in the OP's update for numbers up to 1,000,000,000.


  • I like the idea to use an almost correct method on some of the input. Here is a version with a higher "offset". The code seems to work and passes my simple test case.

    Just replace your:

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

    code with this one:

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

    I was thinking about the horrible times I've spent in Numerical Analysis course.

    And then I remember, there was this function circling around the 'net from the Quake Source code:

    float Q_rsqrt( float number )
    {
      long i;
      float x2, y;
      const float threehalfs = 1.5F;
    
      x2 = number * 0.5F;
      y  = number;
      i  = * ( long * ) &y;  // evil floating point bit level hacking
      i  = 0x5f3759df - ( i >> 1 ); // wtf?
      y  = * ( float * ) &i;
      y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
      // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
    
      #ifndef Q3_VM
      #ifdef __linux__
        assert( !isnan(y) ); // bk010122 - FPE?
      #endif
      #endif
      return y;
    }
    

    Which basically calculates a square root, using Newton's approximation function (cant remember the exact name).

    It should be usable and might even be faster, it's from one of the phenomenal id software's game!

    It's written in C++ but it should not be too hard to reuse the same technique in Java once you get the idea:

    I originally found it at: http://www.codemaestro.com/reviews/9

    Newton's method explained at wikipedia: http://en.wikipedia.org/wiki/Newton%27s_method

    You can follow the link for more explanation of how it works, but if you don't care much, then this is roughly what I remember from reading the blog and from taking the Numerical Analysis course:

    • the * (long*) &y is basically a fast convert-to-long function so integer operations can be applied on the raw bytes.
    • the 0x5f3759df - (i >> 1); line is a pre-calculated seed value for the approximation function.
    • the * (float*) &i converts the value back to floating point.
    • the y = y * ( threehalfs - ( x2 * y * y ) ) line bascially iterates the value over the function again.

    The approximation function gives more precise values the more you iterate the function over the result. In Quake's case, one iteration is "good enough", but if it wasn't for you... then you could add as much iteration as you need.

    This should be faster because it reduces the number of division operations done in naive square rooting down to a simple divide by 2 (actually a * 0.5F multiply operation) and replace it with a few fixed number of multiplication operations instead.


    I'm not sure if it would be faster, or even accurate, but you could use http://www.codemaestro.com/reviews/9 , algorithm to solve the square root faster. You could probably easily test this for all possible 32 bit integers, and validate that you actually got correct results, as it's only an appoximation. However, now that I think about it, using doubles is approximating also, so I'm not sure how that would come into play.


    If you do a binary chop to try to find the "right" square root, you can fairly easily detect if the value you've got is close enough to tell:

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

    So having calculated n^2 , the options are:

    • n^2 = target : done, return true
    • n^2 + 2n + 1 > target > n^2 : you're close, but it's not perfect: return false
    • n^2 - 2n + 1 < target < n^2 : ditto
    • target < n^2 - 2n + 1 : binary chop on a lower n
    • target > n^2 + 2n + 1 : binary chop on a higher n

    (Sorry, this uses n as your current guess, and target for the parameter. Apologise for the confusion!)

    I don't know whether this will be faster or not, but it's worth a try.

    EDIT: The binary chop doesn't have to take in the whole range of integers, either (2^x)^2 = 2^(2x) , so once you've found the top set bit in your target (which can be done with a bit-twiddling trick; I forget exactly how) you can quickly get a range of potential answers. Mind you, a naive binary chop is still only going to take up to 31 or 32 iterations.


    If you want speed, given that your integers are of finite size, I suspect that the quickest way would involve (a) partitioning the parameters by size (eg into categories by largest bit set), then checking the value against an array of perfect squares within that range.


    It should be much faster to use http://en.wikipedia.org/wiki/Newton%27s_method to calculate the Integer Square Root , then square this number and check, as you do in your current solution. Newton's method is the basis for the Carmack solution mentioned in some other answers. You should be able to get a faster answer since you're only interested in the integer part of the root, allowing you to stop the approximation algorithm sooner.

    Another optimization that you can try: If the Digital Root of a number doesn't end in 1, 4, 7, or 9 the number is not a perfect square. This can be used as a quick way to eliminate 60% of your inputs before applying the slower square root algorithm.


    It's been pointed out that the last d digits of a perfect square can only take on certain values. The last d digits (in base b ) of a number n is the same as the remainder when n is divided by b d , ie. in C notation n % pow(b, d) .

    This can be generalized to any modulus m , ie. n % m can be used to rule out some percentage of numbers from being perfect squares. The modulus you are currently using is 64, which allows 12, ie. 19% of remainders, as possible squares. With a little coding I found the modulus 110880, which allows only 2016, ie. 1.8% of remainders as possible squares. So depending on the cost of a modulus operation (ie. division) and a table lookup versus a square root on your machine, using this modulus might be faster.

    By the way if Java has a way to store a packed array of bits for the lookup table, don't use it. 110880 32-bit words is not much RAM these days and fetching a machine word is going to be faster than fetching a single bit.


    Project Euler is mentioned in the tags and many of the problems in it require checking numbers >> 2^64. Most of the optimizations mentioned above don't work easily when you are working with an 80 byte buffer.

    I used java BigInteger and a slightly modified version of Newton's method, one that works better with integers. The problem was that exact squares n^2 converged to (n-1) instead of n because n^2-1 = (n-1)(n+1) and the final error was just one step below the final divisor and the algorithm terminated. It was easy to fix by adding one to the original argument before computing the error. (Add two for cube roots, etc.)

    One nice attribute of this algorithm is that you can immediately tell if the number is a perfect square - the final error (not correction) in Newton's method will be zero. A simple modification also lets you quickly calculate floor(sqrt(x)) instead of the closest integer. This is handy with several Euler problems.


    Regarding the Carmac method, it seems like it would be quite easy just to iterate once more, which should double the number of digits of accuracy. It is, after all, an extremely truncated iterative method -- Newton's, with a very good first guess.

    Regarding your current best, I see two micro-optimizations:

    • move the check vs. 0 after the check using mod255
    • rearrange the dividing out powers of four to skip all the checks for the usual (75%) case.

    Ie:

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

    Even better might be a simple

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

    Obviously, it would be interesting to know how many numbers get culled at each checkpoint -- I rather doubt the checks are truly independent, which makes things tricky.


    The sqrt call is not perfectly accurate, as has been mentioned, but it's interesting and instructive that it doesn't blow away the other answers in terms of speed. After all, the sequence of assembly language instructions for a sqrt is tiny. Intel has a hardware instruction, which isn't used by Java I believe because it doesn't conform to IEEE.

    So why is it slow? Because Java is actually calling a C routine through JNI, and it's actually slower to do so than to call a Java subroutine, which itself is slower than doing it inline. This is very annoying, and Java should have come up with a better solution, ie building in floating point library calls if necessary. Tant pis.

    In C++, I suspect all the complex alternatives would lose on speed, but I haven't checked them all. What I did, and what Java people will find usefull, is a simple hack, an extension of the special case testing suggested by A. Rex. Use a single long value as a bit array, which isn't bounds checked. That way, you have 64 bit boolean lookup.

    typedef unsigned long long UVLONG
    UVLONG pp1,pp2;
    
    void init2() {
      for (int i = 0; i < 64; i++) {
        for (int j = 0; j < 64; j++)
          if (isPerfectSquare(i * 64 + j)) {
        pp1 |= (1 << j);
        pp2 |= (1 << i);
        break;
          }
       }
       cout << "pp1=" << pp1 << "," << pp2 << "\n";  
    }
    
    
    inline bool isPerfectSquare5(UVLONG x) {
      return pp1 & (1 << (x & 0x3F)) ? isPerfectSquare(x) : false;
    }
    

    The routine isPerfectSquare5 runs in about 1/3 the time on my core2 duo machine. I suspect that further tweaks along the same lines could reduce the time further on average, but every time you check, you are trading off more testing for more eliminating, so you can't go too much farther on that road.

    Certainly, rather than having a separate test for negative, you could check the high 6 bits the same way.

    Note that all I'm doing is eliminating possible squares, but when I have a potential case I have to call the original, inlined isPerfectSquare.

    The init2 routine is called once to initialize the static values of pp1 and pp2. Note that in my implementation in C++, I'm using unsigned long long, so since you're signed, you'd have to use the >>> operator.

    There is no intrinsic need to bounds check the array, but Java's optimizer has to figure this stuff out pretty quickly, so I don't blame them for that.


    This a rework from decimal to binary of the old Marchant calculator algorithm (sorry, I don't have a reference), in Ruby, adapted specifically for this 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
    

    Here's a workup of something similar (please don't vote me down for coding style/smells or clunky O/O - it's the algorithm that counts, and C++ is not my home language). In this case, we're looking for residue == 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;
    };
    

    You should get rid of the 2-power part of N right from the start.

    2nd Edit The magical expression for m below should be

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

    and not as written

    End of 2nd edit

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

    1st Edit:

    Minor improvement:

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

    End of 1st edit

    Now continue as usual. This way, by the time you get to the floating point part, you already got rid of all the numbers whose 2-power part is odd (about half), and then you only consider 1/8 of whats left. Ie you run the floating point part on 6% of the numbers.


    Je suis assez en retard à la fête, mais j'espère apporter une meilleure réponse; plus court et (en supposant que mon benchmark est correct) aussi beaucoup faster .

    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 la plupart des non-carrés rapidement. 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 (indirection et contrôles de limites). Pour un long uniformément aléatoire, 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.numberOfTrailingZeros est très rapide car elle se transforme en une seule instruction i86.

    Après avoir déposé 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 à la double arithmétique. Comme le double n'a qu'une mantisse de 53 bits, la conversion du long au double comprend l'arrondi pour les grandes valeurs. Néanmoins, le test est correct (sauf si la proof est fausse).

    Essayer d'incorporer l'idée mod255 n'a pas réussi.





    perfect-square