Le moyen le plus rapide de déterminer si la racine carrée d'un nombre entier est un nombre entier.

Question

Je cherche le moyen le plus rapide de déterminer si un long est un carré parfait (c'est-à-dire que sa racine carrée est un autre entier). Je l'ai fait de la manière la plus simple, en utilisant la fonction intégrée Math.sqrt(), mais je me demande s'il existe un moyen de le faire plus rapidement en se limitant au domaine des entiers. Maintenir une table de consultation est peu pratique (puisqu'il y a environ 2 31.5 les 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;
}

---

Notes : J'utilise cette fonction dans plusieurs Projet Euler problèmes. Ainsi, personne d'autre n'aura jamais à maintenir ce code. Et ce type de micro-optimisation pourrait faire la différence, car une partie du défi consiste à réaliser chaque algorithme 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 postée par A. Rex s'est avéré être encore plus rapide. Lors d'une exécution sur le premier milliard d'entiers, la solution n'a nécessité que 34 % du temps utilisé par la solution originale. Alors que le hack de John Carmack est un peu meilleur pour les petites valeurs de n mais l'avantage par rapport à cette solution est assez faible.

Voici la solution de 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 approfondis, j'ai découvert que l'ajout de 0.5 au résultat de Math.sqrt() n'est pas nécessaire, du moins pas sur ma machine.
• Le site John Carmack hack était plus rapide, mais il donnait des résultats incorrects à partir de n=410881. Cependant, comme suggéré par BobbyShaftoe on peut utiliser le hack de Carmack pour n < 410881.
• La méthode de Newton était un peu plus lente que Math.sqrt() . Ceci est probablement dû au fait que Math.sqrt() utilise quelque chose de similaire à la méthode de Newton, mais implémentée dans le matériel, ce qui la rend beaucoup plus rapide qu'en Java. En outre, la méthode de Newton nécessite toujours l'utilisation de doubles.
• Une méthode de Newton modifiée, qui utilise quelques astuces pour n'impliquer que des calculs sur des entiers, a nécessité quelques bidouillages pour éviter les débordements (je veux que cette fonction fonctionne avec tous les entiers signés positifs de 64 bits), et elle était toujours plus lente que Math.sqrt() .
• Le découpage binaire était encore plus lent. Cela est logique car le découpage binaire nécessite en moyenne 16 passages pour trouver la racine carrée d'un nombre de 64 bits.

La seule suggestion qui a montré des améliorations a été faite par John D. Cook . Vous pouvez observer que le dernier chiffre hexagonal (c'est-à-dire 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 carrés possibles. La mise en œuvre de cette solution a entraîné une réduction d'environ 50 % du temps d'exécution.

En travaillant à partir de la suggestion de John, j'ai étudié les propriétés du dernier n bits d'un carré parfait. En analysant les 6 derniers bits, j'ai constaté que seules 12 valeurs sur 64 sont possibles pour les 6 derniers bits. Cela signifie que 81% des valeurs peuvent être éliminées sans avoir recours aux mathématiques. La mise en œuvre de cette solution a permis une réduction supplémentaire de 8 % du temps d'exécution (par rapport à mon algorithme original). L'analyse de plus de 6 bits donne une liste de bits de fin possibles trop importante pour être pratique.

Voici le code que j'ai utilisé, qui s'exécute en 42% du temps requis par l'algorithme original (basé sur une exécution sur les 100 premiers millions d'entiers). Pour des valeurs de n inférieur à 410881, il s'exécute en 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, en utilisant or est plus rapide en C++ que l'utilisation d'un switch mais en Java et C#, il ne semble pas y avoir de différence entre les deux. or et switch .
• J'ai également essayé de créer une table de consultation (sous la forme d'un tableau statique privé de 64 valeurs booléennes). Ensuite, au lieu d'utiliser soit switch, soit or déclaration, je dirais simplement if(lookup[(int)(n&0x3F)]) { test } else return false; . À ma grande surprise, il était (à peine) plus lent. Je ne sais pas pourquoi. Cela s'explique par le fait que Les limites des tableaux sont vérifiées en Java .

Answer 1

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

Mon approche est triple :

1. D'abord, filtrez les réponses évidentes. Cela inclut les nombres négatifs et l'examen des 4 derniers bits. (J'ai trouvé que regarder les six derniers bits n'aidait pas.) 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 si c'est un carré modulo 255 = 3 * 5 * 17. Comme il s'agit d'un produit de trois nombres premiers distincts, seuls environ 1/8 des résidus modulo 255 sont des carrés. Cependant, d'après mon expérience, appeler l'opérateur modulo (%) coûte plus que le bénéfice que l'on en retire, donc j'utilise des astuces 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, seulement des-and et des décalages de bits).

   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 cherche 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 à celle décrite ci-dessus. Lemme de Hensel . (Je ne pense pas que ce soit applicable directement, mais cela fonctionne avec quelques modifications). Avant de faire 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;

   A 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. (Note : 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 à r, la racine carrée "courante" de x ; chaque racine carrée est exacte modulo une puissance de 2 de plus en plus grande, à savoir t/2. À la fin, r et t/2-r seront des racines carrées de x modulo t/2. (Notez que si r est une racine carrée de x, alors -r l'est aussi. Ceci est vrai même modulo les nombres, mais attention, modulo certains nombres, les choses peuvent avoir même plus de 2 racines carrées ; notamment, cela inclut les puissances de 2). Parce que notre racine carrée réelle est inférieure à 2^32, à ce stade, nous pouvons simplement vérifier si r ou t/2-r sont des racines carrées réelles. 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 (équivalent à ~10 itérations de la boucle), sortie plus tôt de la boucle, et saut de certaines valeurs de t. Pour cette dernière partie, je regarde z = r - x * x et définir t comme étant la plus grande puissance de 2 divisant z avec une astuce binaire. Cela me permet de sauter les valeurs de t qui n'auraient de toute façon pas affecté la valeur de r. La valeur de départ précalculée dans mon cas choisit la racine carrée "la plus petite positive" modulo 8192.

Même si ce code ne fonctionne pas plus vite pour vous, j'espère que vous apprécierez certaines des idées qu'il contient. Le code complet et testé suit, y compris les tables précalculées.

typedef signed long long int int64;

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

bool bad255[512] =
{0,0,1,1,0,1,1,1,1,0,1,1,1,1,1,0,0,1,1,0,1,0,1,1,1,0,1,1,1,1,0,1,
 1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,0,1,1,1,
 0,1,0,1,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1,1,0,0,1,1,1,1,1,1,1,1,0,1,
 1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,1,1,0,1,1,1,1,0,0,1,1,1,1,1,1,
 1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,0,1,1,0,1,1,1,1,1,
 1,1,1,1,1,1,0,1,1,0,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,1,
 1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,
 1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,
 0,0,1,1,0,1,1,1,1,0,1,1,1,1,1,0,0,1,1,0,1,0,1,1,1,0,1,1,1,1,0,1,
 1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,0,1,1,1,
 0,1,0,1,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1,1,0,0,1,1,1,1,1,1,1,1,0,1,
 1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,1,1,0,1,1,1,1,0,0,1,1,1,1,1,1,
 1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,0,1,1,0,1,1,1,1,1,
 1,1,1,1,1,1,0,1,1,0,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,1,
 1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,
 1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,
 0,0};

inline bool square( int64 x ) {
    // Quickfail
    if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) )
        return false;
    if( x == 0 )
        return true;

    // Check mod 255 = 3 * 5 * 17, for fun
    int64 y = x;
    y = (y & 4294967295LL) + (y >> 32);
    y = (y & 65535) + (y >> 16);
    y = (y & 255) + ((y >> 8) & 255) + (y >> 16);
    if( bad255[y] )
        return false;

    // Divide out powers of 4 using binary search
    if((x & 4294967295LL) == 0)
        x >>= 32;
    if((x & 65535) == 0)
        x >>= 16;
    if((x & 255) == 0)
        x >>= 8;
    if((x & 15) == 0)
        x >>= 4;
    if((x & 3) == 0)
        x >>= 2;

    if((x & 7) != 1)
        return false;

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

    return false;
}

Answer 2

J'arrive un peu tard dans la soirée, mais j'espère fournir une meilleure réponse, plus courte et (en supposant que ma réponse soit la bonne) plus complète. repère est correcte) 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 attrape rapidement la plupart des non-squares. Il utilise un tableau de 64 éléments emballé dans un long, de sorte qu'il n'y a pas de coût d'accès au tableau (indirection et vérification des limites). Pour un échantillon uniformément aléatoire long il y a une probabilité de 81,25% de finir ici.

Le deuxième test permet d'attraper tous les nombres ayant un nombre impair de deux dans leur factorisation. La méthode Long.numberOfTrailingZeros est très rapide car il est intégré dans une seule instruction i86.

Le troisième test traite les nombres se terminant par 011, 101 ou 111 en binaire, qui ne sont pas des carrés parfaits. Il prend également en compte les nombres négatifs et traite également le 0.

Le test final revient à double arithmétique. Comme double n'a qu'une mantisse de 56 bits, la conversion de long à double comprend l'arrondi pour les grandes valeurs. Néanmoins, le test est correct (sauf si l'option preuve est erronée).

Essayer d'incorporer l'idée du mod255 n'a pas été couronné de succès.

Answer 3

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

Il se peut que votre algorithme soit presque optimal, mais vous voudrez peut-être effectuer une vérification rapide pour écarter certaines possibilités avant d'appeler votre routine Racine carrée. Par exemple, regardez le dernier chiffre de votre nombre en hexadécimal en faisant un "et" au niveau du bit. Les carrés parfaits ne peuvent se terminer que par 0, 1, 4 ou 9 en base 16. Ainsi, pour 75 % de vos entrées (en supposant qu'elles soient uniformément distribuées), vous pouvez éviter d'appeler la racine carrée en échange d'un traitement très rapide des bits.

Kip a évalué le code suivant, qui met en œuvre l'astuce hexagonale. En testant les nombres de 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 avéré plus lent que l'original. Cependant, lorsque j'ai éliminé l'instruction switch, le tour hexagonal a de nouveau rendu 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;
}

La suppression de l'instruction switch a eu peu d'effet sur le code C#.

Answer 4

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 circulait sur le 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;
}

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

Il devrait être utilisable et pourrait même être plus rapide, il provient d'un des jeux phénoménaux d'id software !

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 en aurez saisi l'idée :

Je l'ai trouvé à l'origine chez : 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 son fonctionnement, mais si vous n'y tenez pas trop, voici en gros ce dont je me souviens en lisant le blog et en suivant le cours d'analyse numérique :

• le site * (long*) &y est essentiellement une fonction de conversion rapide en long afin que les opérations sur les entiers puissent être appliquées aux octets bruts.
• le site 0x5f3759df - (i >> 1); est une valeur de départ pré-calculée pour la fonction d'approximation.
• le site * (float*) &i convertit la valeur en virgule flottante.
• le site y = y * ( threehalfs - ( x2 * y * y ) ) itère de nouveau la valeur sur la fonction.

La fonction d'approximation donne des valeurs plus précises au fur et à mesure que l'on itère la fonction sur le résultat. Dans le cas de Quake, une itération est "assez bonne", mais si ce n'était pas le cas pour vous... alors vous pourriez ajouter autant d'itérations que nécessaire.

Cette méthode devrait être plus rapide car elle réduit le nombre d'opérations de division effectuées dans le cadre de l'enracinement naïf au carré à une simple division par 2 (en fait, un * 0.5F opération de multiplication) et le remplacer par un petit nombre fixe d'opérations de multiplication à la place.

Answer 5

Je ne suis pas sûr que ce soit plus rapide, ni même précis, mais vous pourriez utiliser La racine carrée magique de John Carmack Cet algorithme permet de résoudre la racine carrée plus rapidement. Vous pourriez probablement tester facilement cette méthode pour tous les entiers 32 bits possibles et vérifier que vous obtenez des résultats corrects, puisqu'il ne s'agit que d'une approximation. Cependant, maintenant que j'y pense, l'utilisation de doubles est également une approximation, donc je ne suis pas sûr que cela entre en jeu.