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


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

  1. Je l'ai fait en toute simplicité, en utilisant le Math.sqrt intégré () fonction, mais je me demande s'il y a un moyen de le faire plus rapidement en vous limiter au domaine entier seulement.
  2. Maintenir une table de consultation est imprévisible (puisqu'il y a environ 231.5 entiers dont le carré est inférieur à 263).

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 beaucoup de Projet Euler problèmes. 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.


Une nouvelle solution postée par A. Rex s'est avéré être 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 John Carmack est un peu mieux pour les 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
};

J'ai essayé les différentes solutions présentées ci-dessous.

  • Après des tests exhaustifs, j'ai trouvé que l'ajout 0.5 au résultat de Math.sqrt () n'est pas nécessaire, du moins pas sur ma machine.
  • le John Carmack bidouille était plus rapide, mais 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(). C'est probablement parce que 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 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 seule suggestion qui a montré des améliorations a été faite par John D. Cook. Vous pouvez observer que le dernier chiffre hexadécimal (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.

Travaillant à partir de la suggestion de John, j'ai étudié les propriétés de la dernière n des morceaux 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é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;
  }
}

Remarques:

  • Selon les tests de John, en utilisant or instructions est plus rapide en C ++ que d'utiliser un switch, mais en Java et 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). Ensuite, au lieu de l'un ou l'autre commutateur ou or déclaration, je dirais juste if(lookup[(int)(n&0x3F)]) { test } else return false;. À ma grande surprise, c'était (légèrement) plus lent. Je ne suis pas sûr pourquoi.  Ceci est dû au fait les limites du tableau sont vérifiées en Java.

1209


origine


Réponses:


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 ma contribution 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.
    

602



Je suis assez en retard à la fête, mais j'espère apporter une meilleure réponse; plus court et (en supposant que mon 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 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 hasard 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.numberOfTrailingZeros est très rapide car il 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 dernier test revient à double arithmétique. Comme double a seulement 53 bits de mantisse, la conversion de long à double comprend l'arrondissement pour les grandes valeurs. Néanmoins, le test est correct (à moins que preuve est faux).

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


260



Vous devrez faire un benchmarking. 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 peu "et". Les cases parfaites ne peuvent se terminer qu'à 0, 1, 4 ou 9 en base 16, donc pour 75% de vos entrées (en supposant qu'elles sont uniformément distribuées), vous pouvez éviter un appel à la racine carrée en échange de quelques bits très rapides.

Kip a comparé le code suivant implémentant l'astuce hexadécimale. Lors du test des numéros 1 à 100 000 000, ce code était deux fois plus rapide que l'original.

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

    switch((int)(n & 0xF))
    {
    case 0: case 1: case 4: case 9:
        long tst = (long)Math.sqrt(n);
        return tst*tst == n;

    default:
        return false;
    }
}

Lorsque j'ai testé le code analogue en C ++, il fonctionnait plus lentement que l'original. Cependant, quand j'ai éliminé l'instruction switch, le tour d'hex 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 #.


118



Je pensais aux temps horribles que j'ai passés dans le cours d'Analyse Numérique.

Et puis je me souviens, il y avait cette fonction qui tourne autour du filet 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 fondamentalement 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 est issu de l'un des jeux du logiciel id phénoménal!

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 à: http://www.codemaestro.com/reviews/9

La méthode de Newton expliquée à 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, alors c'est à peu près ce que je me souviens de la lecture du blog et de prendre le cours d'analyse numérique:

  • la * (long*) &y est fondamentalement une fonction rapide de conversion en longueur de sorte que des opérations entières peuvent être appliquées sur les octets bruts.
  • la 0x5f3759df - (i >> 1); line est une valeur de départ pré-calculée pour la fonction d'approximation.
  • la * (float*) &i convertit la valeur en virgule flottante.
  • la y = y * ( threehalfs - ( x2 * y * y ) ) line bascule à nouveau 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 pourriez ajouter autant d'itérations que nécessaire.

Cela devrait être plus rapide car cela réduit le nombre d'opérations de division effectuées dans l'enracinement carré naïf à une simple division par 2 (en fait un * 0.5F multipliez l'opération) et remplacez-le par un nombre fixe d'opérations de multiplication.


41



Je ne suis pas sûr que ce serait plus rapide, ou même précis, mais vous pourriez utiliser Racine carrée magique de John Carmack, algorithme pour résoudre la racine carrée plus rapidement. Vous pourriez probablement tester ceci pour tous les entiers de 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 se rapproche également, donc je ne suis pas sûr de la façon dont cela entrerait en jeu.


33



Si vous faites une coupure binaire pour essayer de trouver la "bonne" racine carrée, vous pouvez assez facilement détecter si la valeur que vous avez est assez proche pour dire:

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

Donc ayant calculé n^2, les options sont:

  • n^2 = target: fait, 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 : couper binaire sur un bas n
  • target > n^2 + 2n + 1 : couper binaire sur un plus haut n

(Désolé, cela utilise n comme votre estimation actuelle, et target pour le paramètre. Excusez-vous pour la confusion!)

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

EDIT: La côtelette binaire n'a pas à prendre dans l'ensemble des entiers, soit (2^x)^2 = 2^(2x), donc une fois que vous avez trouvé le bit de la partie supérieure dans votre cible (ce qui peut être fait avec un peu de trépidation, j'oublie exactement comment), vous pouvez rapidement obtenir une gamme de réponses potentielles. Rappelez-vous, une coupure binaire naïve ne va encore prendre jusqu'à 31 ou 32 itérations.


30



J'ai couru ma propre analyse de plusieurs des algorithmes dans ce fil et ai trouvé de nouveaux résultats. Vous pouvez voir ces vieux résultats dans l'historique d'édition de cette réponse, mais ils ne sont pas précis, car j'ai fait une erreur, et j'ai 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 la chose principale que je fais différemment que 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 grandement switch-case déclaration dans une instruction if. Cependant, il peut ajouter à l'exécution si beaucoup des nombres testés ont des facteurs significatifs de puissance de deux.

Les algorithmes ci-dessous sont les suivants:

  • l'Internet - La réponse affichée de Kip
  • Durron - Ma réponse modifiée en utilisant la réponse à une passe comme base
  • DurronTwo - Ma réponse modifiée en utilisant la réponse en deux passages (par @JohnnyHeggheim), avec quelques autres légères modifications.

Voici un exemple d'exécution si les nombres sont générés en utilisant 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 de runtime 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, DurronTwo fait mieux pour les gros intrants, car il arrive très souvent à utiliser l'astuce magique, mais il est plus frôlé que le premier algorithme et Math.sqrt parce que les chiffres sont tellement plus petits. En attendant, le plus simple Durron est un grand gagnant parce qu'il n'a jamais à diviser par 4 plusieurs fois dans le premier million de numéros.

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 Google étrier 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);
    }
}

METTRE À JOUR: J'ai fait un nouvel algorithme qui est plus rapide dans certains scénarios, plus lent dans d'autres, j'ai obtenu différents benchmarks basés sur différentes entrées. Si nous calculons 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 carrés. Cela peut être fait (en quelque sorte) en une ligne, avec 5 opérations au niveau du bit:

if (!goodLookupSquares[(int) ((n & 0xFFFFFFl) + ((n >> 24) & 0xFFFFFFl) + (n >> 48))]) return false;

L'indice résultant est soit 1) le résidu, 2) le résidu + 0xFFFFFFou 3) le résidu + 0x1FFFFFE. Bien sûr, nous devons avoir une table de recherche pour les résidus modulo 0xFFFFFF, qui est d'environ un fichier de 3mb (dans ce cas, stocké sous forme de chiffres décimaux ASCII, pas optimal mais clairement perfectible avec un ByteBuffer et ainsi de suite. Mais puisque c'est une précalculation, cela n'a pas tellement d'importance. 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 boolean tableau comme ceci:

private static boolean[] goodLookupSquares = null;

public static void initGoodLookupSquares() throws Exception {
    Scanner s = new Scanner(new File("24residues_squares.txt"));

    goodLookupSquares = new boolean[0x1FFFFFE];

    while(s.hasNextLine()) {
        int residue = Integer.valueOf(s.nextLine());
        goodLookupSquares[residue] = true;
        goodLookupSquares[residue + 0xFFFFFF] = true;
        goodLookupSquares[residue + 0x1FFFFFE] = true;
    }

    s.close();
}

Exemple d'exécution. Il a battu Durron (version 1) 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

21



Il devrait être beaucoup plus rapide à utiliser La méthode de Newton pour calculer le Racine carrée entière, puis placez ce nombre et vérifiez, comme vous le faites dans votre solution actuelle. La méthode de Newton est à la base de la solution de Carmack mentionnée dans d'autres réponses. Vous devriez être en mesure d'obtenir une réponse plus rapide puisque 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 le Racine numérique d'un nombre ne finit pas dans 1, 4, 7 ou 9 le nombre est ne 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 lente.


14



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

Math.sqrt() fonctionne avec des doubles comme paramètres d'entrée, de sorte que vous n'obtiendrez pas de résultats précis pour les entiers plus grands que 2 ^ 53.


12