Moyen le plus rapide pour déterminer si la racine carrée d'un entier est un entier

je suis à la recherche du moyen le plus rapide pour déterminer si une valeur long est un carré parfait (c.-à-d. sa racine carrée est un autre entier):

  1. Je l'ai fait de la manière facile, en utilisant les mathématiques intégrées.sqrt() fonction, mais je me demande s'il y a un moyen de le faire plus rapidement par vous limiter à Domaine entier seulement.
  2. maintenir une table de recherche est impraticable (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 que 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 de nombreux projet Euler problèmes. En sorte que personne n'aura jamais à maintenir ce code. Et ce type de micro-optimisation pourrait en fait faire la différence, puisqu'une partie du défi est à faire chaque algorithme en moins d'une minute, et cette fonction devra être appelés des millions de fois dans certains problèmes.


une nouvelle solution Postée par A. Rex s'est avérée encore plus rapide. Dans un passage sur les 1 milliard premiers entiers, la solution n'a exigé que 34% du temps que la solution originale a utilisé. Alors que le hack de 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 de 0.5 au résultat des mathématiques.sqrt() n'est pas nécessaire, du moins pas sur ma machine.
  • le John Carmack hack était plus rapide, mais il a donné des résultats incorrects à partir de n=410881. Cependant , comme suggéré par BobbyShaftoe , nous pouvons utiliser le hack Carmack pour n < 410881.
  • la méthode de Newton était un bon peu plus lente que Math.sqrt() . Cela 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 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 de Newton modifiée, qui a utilisé quelques trucs de sorte que seule la mathématique entière était impliquée, a nécessité quelques hacks pour éviter le débordement (je veux que cette fonction fonctionne avec tous les entiers signés positifs de 64 bits), et il était encore plus lent que Math.sqrt() .
  • chop binaire était encore plus lent. Cela a du sens parce que le cône binaire demandera en moyenne 16 passes pour trouver la racine carrée d'un nombre 64 bits.

le une suggestion qui montre 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 éliminés immédiatement comme carrés possibles. La mise en œuvre de cette solution a permis de réduire d'environ 50% le temps d'exécution.

D'après la suggestion de John, j'ai étudié les propriétés du dernier n bits de un carré parfait. En analysant les 6 derniers bits, j'ai trouvé que seulement 12 de 64 valeurs possibles pour les 6 derniers bits. Cela signifie que 81% des valeurs peuvent être éliminées sans utiliser de mathématiques. La mise en œuvre de cette solution a permis une réduction supplémentaire de 8% de la durée d'exécution (par rapport à mon algorithme original). L'analyse de plus de 6 bits aboutit à 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 original (basé sur une course pendant les 100 premiers millions d'entiers). Pour des valeurs de n inférieures à 410881, il ne court que 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 des déclarations 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 or et switch .
  • j'ai aussi essayé de faire une table de recherche (comme un tableau statique privé de 64 valeurs booléennes). Alors, au lieu de changer ou de dire or , je dirais if(lookup[(int)(n&0x3F)]) { test } else return false; . À ma grande surprise, cela a été (juste un peu) plus lent. Je ne sais pas pourquoi. c'est parce que les limites du tableau sont vérifiées en Java .
1250
demandé sur Kip 2008-11-17 16:43:21
la source

30 ответов

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

mon approche est triple:

  1. d'abord, filtrez les réponses évidentes. Cela inclut les nombres négatifs et en regardant les 4 derniers bits. (J'ai trouvé que regarder les six derniers n'aidait pas.) Je répondez 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 modulo carré 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 carrés. Cependant, d'après mon expérience, appeler l'opérateur modulo (%) coûte plus cher que le bénéfice que l'on obtient, donc j'utilise des trucs de bits impliquant 255 = 2^8-1 pour calculer le résidu. (Pour le meilleur et pour le pire, je n'utilise pas truc de lire des octets individuels à partir d'un mot, seulement bitwise-And et shifts.)
    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 réellement vérifier si le résidu est un carré, je regarde 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 à lemme de Hensel . (Je ne pense pas que cela s'applique directement, mais cela fonctionne avec quelques modifications.) Avant de faire cela, je divise tous les pouvoirs de 2 avec une recherche binaire:
    if((x & 4294967295LL) == 0)
        x >>= 32;
    if((x & 65535) == 0)
        x >>= 16;
    if((x & 255) == 0)
        x >>= 8;
    if((x & 15) == 0)
        x >>= 4;
    if((x & 3) == 0)
        x >>= 2;
    A ce point, 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 peu sur r, la racine carrée "actuelle" de x; chaque racine carrée est modulo précis une puissance de plus en plus grande de 2, à savoir t/2. À la fin, r et t/2-r sera racines carrées de x modulo t/2. (Notez que si r est une racine carrée de x, alors c'est-R. Ceci est vrai même les nombres modulo, mais attention, modulo certains nombres, les choses peuvent avoir même plus de 2 racines carrées; notamment, Cela inclut des pouvoirs de 2.) Parce que notre racine carrée réelle est inférieure à 2^32, à ce point nous pouvons en fait juste 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édéfinie (équivalente à ~10 itérations de la boucle), sortie anticipée de la boucle et sautant quelques valeurs de T. Pour la dernière partie, je regarde z = r - x * x , et régler t à la plus grande puissance de 2 divisant z avec un peu d'astuce. Cela me permet de sauter des valeurs t qui n'auraient pas affecté la valeur de r de toute façon. La valeur de départ prédéfinie dans mon cas indique la racine carrée du "plus petit positif" modulo 8192.

Même si ce code ne fonctionne pas plus rapide pour vous, j'espère que vous apprécierez certaines des idées qu'il contient. Code complet, testé ci-après, y compris les tableaux prédéfinis.

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;
}
623
répondu A. Rex 2013-11-18 03:39:06
la source

je suis assez en retard à la partie, mais j'espère fournir une meilleure réponse; plus court et (en supposant mon benchmark 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 prend la plupart des non-carrés rapidement. Il utilise une table de 64 éléments empaquetés dans une longue, il n'y a donc pas de coût d'accès au tableau (contrôles indirects et limites). Pour uniformément aléatoire long , il y a une probabilité de 81,25% de finir ici.

le deuxième test prend tous les nombres ayant un nombre impair de deux dans leur factorisation. La méthode Long.numberOfTrailingZeros est très rapide car il obtient JIT-ed dans une seule instruction i86.

après avoir laissé tomber les zéros de queue, le troisième test traite les nombres se terminant par 011, 101, ou 111 en binaire, qui ne sont pas des carrés parfaits. Il se soucie également des nombres négatifs et traite aussi 0.

Le test final revient à l'arithmétique double . Comme double a seulement 53 bits mantissa, la conversion de long en double inclut l'arrondissement pour les grandes valeurs. Néanmoins, le test est correct (à moins que la preuve est erronée).

essayer d'intégrer l'idée mod255 n'a pas réussi.

280
répondu maaartinus 2018-02-15 23:18:41
la source

vous devrez faire une analyse comparative. Le meilleur algorithme dépend de la distribution de vos entrées.

votre algorithme peut être presque optimal, mais vous pourriez vouloir faire une vérification rapide pour écarter quelques 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 peu sage "et."Les carrés parfaits ne peuvent finir qu'en 0, 1, 4, ou 9 en base 16, donc pour 75% de vos entrées (en supposant qu'ils sont uniformément distribué), vous pouvez éviter un appel à la racine carrée en échange de quelques très rapide peu tourner.

Kip Référencé le code suivant implémentant le truc hex. Lors du test des numéros 1 à 100 000 000, ce code a couru 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;
    }
}

quand j'ai testé le code analogue en C++, il fonctionnait en fait plus lentement que l'original. Cependant, quand j'ai éliminé l'instruction switch, le HEX trick fait à nouveau le code deux fois. aussi vite.

int isPerfectSquare(int n)
{
    int h = n & 0xF;  // h is the last hex "digit"
    if (h > 9)
        return 0;
    // Use lazy evaluation to jump out of the if statement as soon as possible
    if (h != 2 && h != 3 && h != 5 && h != 6 && h != 7 && h != 8)
    {
        int t = (int) floor( sqrt((double) n) + 0.5 );
        return t*t == n;
    }
    return 0;
}

L'élimination de la déclaration de l'interrupteur a eu peu d'effet sur le code C#.

122
répondu John D. Cook 2009-01-27 23:35:45
la source

je pensais aux moments horribles que j'ai passés en cours D'analyse numérique.

et puis je me souviens, il y avait cette fonction encerclant le 'net à partir du code source du séisme:

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 (ne peut se rappeler le nom exact).

il devrait être utilisable et pourrait même être plus rapide, il est d'un des jeux du logiciel phénoménal id!

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

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

vous pouvez suivre le lien pour plus d'explications sur la façon dont il 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:

  • le * (long*) &y est fondamentalement une fonction de conversion rapide en fonction longue de sorte que des opérations entières peuvent être appliquées sur les octets bruts.
  • la ligne 0x5f3759df - (i >> 1); est une valeur prédéfinie pour la fonction d'approximation.
  • le * (float*) &i convertit la valeur en point flottant.
  • la ligne y = y * ( threehalfs - ( x2 * y * y ) ) itère bascialement la valeur sur la fonction à nouveau.

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... ensuite, vous pouvez ajouter autant d'itération que vous avez besoin.

cela devrait être plus rapide parce qu'il réduit le nombre d'opérations de division effectuées en enracinement carré naïf jusqu'à une simple division par 2 (en fait une opération de multiplication * 0.5F ) et la remplacer par un nombre fixe d'opérations de multiplication.

45
répondu chakrit 2012-04-13 10:18:29
la source

Je ne suis pas sûr que ce soit plus rapide, ou même précis, mais vous pouvez utiliser racine carrée magique de John Carmack , algorithme pour résoudre la racine carrée plus rapidement. Vous pourriez probablement facilement tester cela pour tous les entiers 32 bits possibles, et valider que vous avez réellement obtenu des résultats corrects, car il est seulement une appoximation. Cependant, maintenant que j'y pense, utiliser des doubles est aussi approximatif, donc je ne sais pas comment cela pourrait entrer en jeu.

37
répondu Kibbee 2008-11-17 16:51:45
la source

Si vous faites un binaire chop pour essayer de trouver le "bon" 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, return true
  • n^2 + 2n + 1 > target > n^2 : vous êtes proche, mais il n'est pas parfait: return false
  • n^2 - 2n + 1 < target < n^2 : idem
  • target < n^2 - 2n + 1 : cône binaire sur un bas n
  • target > n^2 + 2n + 1 : cône binaire sur un haut n

(désolé, cela utilise n comme votre supposition actuelle, et target pour le paramètre. Excusez la confusion!)

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

EDIT: le chop binaire n'a pas à prendre dans l'ensemble gamme d'entiers, soit (2^x)^2 = 2^(2x) , donc une fois que vous avez trouvé le meilleur bit défini dans votre cible (ce qui peut être fait avec un tour de bit-twiddling; j'oublie exactement comment), vous pouvez obtenir rapidement une gamme de réponses potentielles. Attention, une chop binaire naïve ne prendra que 31 ou 32 itérations.

32
répondu Jon Skeet 2008-11-17 17:48:48
la source

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

// This is faster because a number is divisible by 2^4 or more only 6% of the time
// and more than that a vanishingly small percentage.
while((x & 0x3) == 0) x >>= 2;
// This is effectively the same as the switch-case statement used in the original
// answer. 
if((x & 0x7) != 1) return false;

cependant, cette ligne simple, qui la plupart du temps ajoute une ou deux instructions très rapides, simplifie grandement l'énoncé switch-case en un seul énoncé if. Cependant, il peut ajouter à l'exécution si de nombreux testé nombre considérable de puissance de deux facteurs.

les algorithmes ci-dessous sont les suivants:

  • Internet - de Kip posté réponse
  • Durron - Mon modifiée réponse à l'aide de l'un des passe-réponse à une base de
  • 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 échantillon runtime si il est exécuté sur le premier million de longueurs seulement:

 0% Scenario{vm=java, trial=0, benchmark=Internet} 2933380.84 ns; ?=56939.84 ns @ 10 trials
33% Scenario{vm=java, trial=0, benchmark=Durron} 2243266.81 ns; ?=50537.62 ns @ 10 trials
67% Scenario{vm=java, trial=0, benchmark=DurronTwo} 3159227.68 ns; ?=10766.22 ns @ 3 trials

benchmark   ms linear runtime
 Internet 2.93 ===========================
   Durron 2.24 =====================
DurronTwo 3.16 ==============================

vm: java
trial: 0

comme vous pouvez le voir, DurronTwo fait mieux pour de grandes entrées, parce qu'il obtient d'utiliser le tour de magie très souvent, mais obtient saboté par rapport au premier algorithme et Math.sqrt parce que les nombres sont tellement plus petits. Pendant ce temps, le plus simple Durron est un énorme gagnant parce qu'il n'a jamais à diviser par 4 beaucoup de 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 caliper 0.1-rc5)

public class SquareRootBenchmark {
    public static class Benchmark1 extends SimpleBenchmark {
        private static final int ARRAY_SIZE = 10000;
        long[] trials = new long[ARRAY_SIZE];

        @Override
        protected void setUp() throws Exception {
            Random r = new Random();
            for (int i = 0; i < ARRAY_SIZE; i++) {
                trials[i] = Math.abs(r.nextLong());
            }
        }


        public int timeInternet(int reps) {
            int trues = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < ARRAY_SIZE; j++) {
                    if(SquareRootAlgs.isPerfectSquareInternet(trials[j])) trues++;
                }
            }

            return trues;   
        }

        public int timeDurron(int reps) {
            int trues = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < ARRAY_SIZE; j++) {
                    if(SquareRootAlgs.isPerfectSquareDurron(trials[j])) trues++;
                }
            }

            return trues;   
        }

        public int timeDurronTwo(int reps) {
            int trues = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < ARRAY_SIZE; j++) {
                    if(SquareRootAlgs.isPerfectSquareDurronTwo(trials[j])) trues++;
                }
            }

            return trues;   
        }
    }

    public static void main(String... args) {
        Runner.main(Benchmark1.class, args);
    }
}

UPDATE: j'ai 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 (en quelque sorte) fait en une ligne, avec 5 opérations bitwise:

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

L'indice est soit 1) le résidu, 2) le résidu + 0xFFFFFF , ou 3) le résidu + 0x1FFFFFE . Bien sûr , nous avons besoin d'une table de recherche pour les résidus modulo 0xFFFFFF , qui est d'environ un fichier de 3 Mo (dans ce cas stocké comme ASCII texte nombres décimaux, pas optimal mais clairement améliorable avec un ByteBuffer et ainsi de suite. Mais comme c'est un précalcul, ça n'a pas tellement d'importance. , Vous pouvez trouver le fichier ici (ou produisez-le 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 un) dans chaque procès 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
22
répondu durron597 2013-06-13 21:42:46
la source

il devrait être beaucoup plus rapide d'utiliser méthode de Newton pour calculer la racine carrée entière , puis carré ce nombre et de vérifier, comme vous le faites dans votre solution actuelle. La méthode de Newton est à la base de la solution de Carmack mentionnée dans d'autres réponses. Vous devriez être capable d'obtenir une réponse plus rapide puisque vous êtes seulement intéressé par la partie entière de la racine, vous permettant 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 se termine pas en 1, 4, 7, ou 9 le nombre est pas un carré parfait. Cela peut être utilisé comme un moyen rapide d'éliminer 60% de vos entrées avant d'appliquer l'algorithme de racine carrée plus lent.

16
répondu Bill the Lizard 2008-11-17 18:04:49
la source

je veux que cette fonction fonctionne avec tous les positif 64-bit signed entiers

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

13
répondu mrzl 2018-04-06 12:07:49
la source

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

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

une solution serait alors comme ceci:

boolean isPerfectSquare(long number)
{
    if (number < 0) return false;
    if (number < 2) return true;

    for (int i = 0; ; i++)
    {
        long square = squareTable[i];
        if (square > number) return false;
        while (number % square == 0)
        {
            number /= square;
        }
        if (number == 1) return true;
    }
}

c'est un peu mystérieux. Ce qu'il fait est de vérifier à chaque étape que le carré d'un nombre premier diviser le nombre d'entrée. S'il le fait, alors il divise le nombre par le carré aussi longtemps qu'il est possible, pour enlever ce carré de la décomposition première. Si par ce processus, nous sommes arrivés à 1, alors le nombre d'entrée était une décomposition du carré des nombres premiers. Si le carré devient plus grand que le nombre lui-même, alors il n'y a aucun moyen que ce carré, ou n'importe quels carrés plus grands, peuvent le diviser, de sorte que le nombre ne peut pas être une décomposition de carrés de nombres premiers.

compte tenu de nos jours sqrt fait dans le matériel et la nécessité de calculer des nombres premiers ici, je suppose que cette solution est beaucoup plus lente. Mais il devrait donner de meilleurs résultats que solution avec sqrt qui ne fonctionnera pas plus de 2^54, Comme dit mrzl dans sa réponse.

12
répondu Cyrille Ka 2008-12-02 13:00:22
la source

un problème entier mérite une solution entière. Ainsi

faire une recherche binaire sur les entiers (non-négatifs) pour trouver le plus grand entier T tel que t**2 <= n . Puis tester si r**2 = n exactement. Cela prend du temps O(log n).

si vous ne savez pas comment binaire rechercher les entiers positifs parce que l'ensemble est illimité, c'est facile. Vous commencez par calculer votre fonction croissante f (au-dessus de f(t) = t**2 - n ) sur des puissances de deux. Lorsque vous si ça devient positif, vous avez trouvé une limite supérieure. Alors vous pouvez faire la recherche binaire standard.

11
répondu Colonel Panic 2013-10-16 14:18:53
la source

il a été souligné que les derniers d chiffres d'un carré parfait ne peut prendre sur certaines valeurs. Le dernier chiffre d (en base b ) d'un numéro n est le même que le reste lorsque n est divisé par b d , ie. au point C n % pow(b, d) .

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

par ailleurs si Java a un moyen de stocker un tableau emballé de bits de la table de recherche, ne l'utilisez pas. 110880 mots 32 bits n'est pas beaucoup de RAM ces jours-ci et aller chercher un mot machine va être plus rapide que aller chercher un seul bit.

10
répondu Hugh Allen 2008-11-29 06:52:36
la source

pour l'exécution, il faut très souvent faire quelques compromis. D'autres ont exprimé diverses méthodes, cependant, vous avez noté que le hack de Carmack était plus rapide jusqu'à certaines valeurs de N. alors, vous devriez vérifier le "n" et s'il est inférieur à ce nombre N, utilisez le hack de Carmack, sinon utilisez une autre méthode décrite dans les réponses ici.

9
répondu BobbyShaftoe 2008-12-05 08:36:38
la source

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

  • test Mod-256
  • test Inexact mod-3465 (évite la division entière au prix de quelques faux positifs)
  • racine carrée à virgule flottante, ronde et comparer avec la valeur d'entrée

j'ai également expérimenté ces modifications mais ils ont fait Non help performance:

  • Additional mod-255 test
  • divisant la valeur d'entrée par des puissances de 4
  • racine carrée inversée rapide (pour fonctionner avec des valeurs élevées de N il faut 3 itérations, assez pour la rendre plus lente que la fonction racine carrée matérielle.)

public class SquareTester {

    public static boolean isPerfectSquare(long n) {
        if (n < 0) {
            return false;
        } else {
            switch ((byte) n) {
            case -128: case -127: case -124: case -119: case -112:
            case -111: case -103: case  -95: case  -92: case  -87:
            case  -79: case  -71: case  -64: case  -63: case  -60:
            case  -55: case  -47: case  -39: case  -31: case  -28:
            case  -23: case  -15: case   -7: case    0: case    1:
            case    4: case    9: case   16: case   17: case   25:
            case   33: case   36: case   41: case   49: case   57:
            case   64: case   65: case   68: case   73: case   81:
            case   89: case   97: case  100: case  105: case  113:
            case  121:
                long i = (n * INV3465) >>> 52;
                if (! good3465[(int) i]) {
                    return false;
                } else {
                    long r = round(Math.sqrt(n));
                    return r*r == n; 
                }
            default:
                return false;
            }
        }
    }

    private static int round(double x) {
        return (int) Double.doubleToRawLongBits(x + (double) (1L << 52));
    }

    /** 3465<sup>-1</sup> modulo 2<sup>64</sup> */
    private static final long INV3465 = 0x8ffed161732e78b9L;

    private static final boolean[] good3465 =
        new boolean[0x1000];

    static {
        for (int r = 0; r < 3465; ++ r) {
            int i = (int) ((r * r * INV3465) >>> 52);
            good3465[i] = good3465[i+1] = true;
        }
    }

}
8
répondu finnw 2010-05-06 20:37:40
la source

la simplification suivante de la solution de maaartinus semble réduire de quelques points de pourcentage le temps d'exécution, mais je ne suis pas assez bon à l'étalonnage pour produire un benchmark je peux faire confiance:

long goodMask; // 0xC840C04048404040 computed below
{
    for (int i=0; i<64; ++i) goodMask |= Long.MIN_VALUE >>> (i*i);
}

public boolean isSquare(long x) {
    // This tests if the 6 least significant bits are right.
    // Moving the to be tested bit to the highest position saves us masking.
    if (goodMask << x >= 0) return false;
    // Remove an even number of trailing zeros, leaving at most one.
    x >>= (Long.numberOfTrailingZeros(x) & (-2);
    // Repeat the test on the 6 least significant remaining bits.
    if (goodMask << x >= 0 | x <= 0) return x == 0;
    // Do it in the classical way.
    // The correctness is not trivial as the conversion from long to double is lossy!
    final long tst = (long) Math.sqrt(x);
    return tst * tst == x;
}

Il serait intéressant de vérifier comment en omettant le premier test,

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

affecterait la performance.

8
répondu dfeuer 2014-07-13 23:24:11
la source

vous devez vous débarrasser de la partie 2-puissance de N dès le début.

2e Édition L'expression magique pour M ci-dessous devrait être

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

et non pas comme il est écrit

fin de la 2e édition

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

1ère Édition:

amélioration mineure:

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

Fin de la 1ère édition

continue comme d'habitude. De cette façon, au moment où vous arrivez à la partie flottante, vous vous êtes déjà débarrassé de tous les numéros dont la partie 2-puissance est étrange (environ la moitié), et puis vous ne considérez que 1/8 de ce qui reste. I. e. vous exécutez la virgule flottante partie sur 6% des effectifs.

7
répondu David Lehavi 2009-01-02 11:17:46
la source

c'est une reprise de Décimal en binaire de L'ancien algorithme de calcul de Marchant (désolé, je n'ai pas de référence), en Ruby, adapté spécifiquement pour cette question:

def isexactsqrt(v)
    value = v.abs
    residue = value
    root = 0
    onebit = 1
    onebit <<= 8 while (onebit < residue)
    onebit >>= 2 while (onebit > residue)
    while (onebit > 0)
        x = root + onebit
        if (residue >= x) then
            residue -= x
            root = x + onebit
        end
        root >>= 1
        onebit >>= 2
    end
    return (residue == 0)
end

voici un calcul de quelque chose de similaire (s'il vous plaît ne me votez pas vers le bas pour le style de codage/odeurs ou clunky O/O - c'est l'algorithme qui compte, et C++ n'est pas ma langue maternelle). Dans ce cas, nous cherchons 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;
};
6
répondu Brent.Longborough 2009-01-02 14:25:59
la source

l'appel de la sqrt n'est pas parfaitement exact, comme cela a été mentionné, mais il est intéressant et instructif qu'il ne souffle pas les autres réponses en termes de vitesse. Après tout, la séquence des instructions de langage de montage pour un sqrt est minuscule. Intel a une instruction matérielle, qui N'est pas utilisée par Java je crois parce qu'elle n'est pas conforme à IEEE.

alors pourquoi est-ce lent? Parce que Java appelle en fait une routine C via JNI, et c'est en fait plus lent à le faire que d'appeler un sous-programme Java, qui lui-même est plus lent que de le faire en ligne. C'est très gênant, et Java aurait dû trouver une meilleure solution, c'est-à-dire construire des appels de bibliothèque en virgule flottante si nécessaire. Oh bien.

en C++, je soupçonne que toutes les alternatives complexes perdraient en vitesse, mais je ne les ai pas toutes vérifiées. Ce que J'ai fait, et ce que les gens de Java trouveront utile, est un simple hack, une extension du cas spécial de test suggéré par A. Rex. Utilisez un seul long valeur comme un tableau de bits, qui n'est pas limité vérifié. De cette façon, vous avez 64 bits de recherche booléenne.

typedef unsigned long long UVLONG
UVLONG pp1,pp2;

void init2() {
  for (int i = 0; i < 64; i++) {
    for (int j = 0; j < 64; j++)
      if (isPerfectSquare(i * 64 + j)) {
    pp1 |= (1 << j);
    pp2 |= (1 << i);
    break;
      }
   }
   cout << "pp1=" << pp1 << "," << pp2 << "\n";  
}


inline bool isPerfectSquare5(UVLONG x) {
  return pp1 & (1 << (x & 0x3F)) ? isPerfectSquare(x) : false;
}

la routine isPerfectSquare5 fonctionne dans environ 1/3 du temps sur ma machine Core2 duo. Je soupçonne que d'autres modifications dans le même sens pourraient réduire le temps encore plus en moyenne, mais à chaque fois que vous vérifiez, vous échangez plus de tests pour plus d'élimination, de sorte que vous ne pouvez pas aller trop loin sur cette route.

Certainement, plutôt que d'avoir un test séparé pour négatif, vous pouvez vérifier la haute 6 bits de la même façon.

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

la routine init2 est appelée une fois pour initialiser les valeurs statiques de pp1 et pp2. Notez que dans mon application en C++, je suis en utilisant unsigned long long, donc, puisque vous êtes connecté, vous devez utiliser la >>> opérateur.

il n'y a pas besoin intrinsèque de vérifier les limites du tableau, mais L'optimiseur de Java doit trouver ce truc assez rapidement, donc je ne les blâme pas pour cela.

6
répondu hydrodog 2009-03-11 16:37:53
la source

le projet Euler est mentionné dans les étiquettes et bon nombre des problèmes qu'il pose nécessitent des numéros de contrôle >> 2^64. La plupart des optimisations mentionnées ci-dessus ne fonctionnent pas facilement lorsque vous travaillez avec un tampon de 80 octets.

j'ai utilisé java BigInteger et une version légèrement modifiée de la méthode de Newton, qui fonctionne mieux avec les entiers. Le problème était que les carrés exacts N^2 convergeaient vers (n-1) au lieu de n parce que n^2-1 = (n-1)(n+1) et que l'erreur finale n'était qu'une pas en dessous du diviseur final et l'algorithme terminé. Il était facile de corriger en ajoutant un à l'argument original Avant de calculer l'erreur. (Ajouter deux pour les racines cubiques, etc.)

un attribut agréable de cet algorithme est que vous pouvez dire immédiatement si le nombre est un carré parfait - l'erreur finale (Pas de correction) dans la méthode de Newton sera zéro. Une modification simple vous permet également de calculer rapidement le plancher(sqrt(x)) au lieu de l'entier le plus proche. Ce qui est pratique avec plusieurs problèmes Euler.

6
répondu bgiles 2009-03-25 18:23:05
la source

j'aime l'idée d'utiliser un près de méthode correcte sur certains de l'entrée. Voici une version avec un "offset"plus élevé. Le code semble fonctionner et passe mon test simple.

il suffit de remplacer votre:

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

code avec celui-ci:

if (n < 11043908100L) {
    //John Carmack hack, converted to Java.
    // See: http://www.codemaestro.com/reviews/9
    int i;
    float x2, y;

    x2 = n * 0.5F;
    y = n;
    i = Float.floatToRawIntBits(y);
    //using the magic number from 
    //http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf
    //since it more accurate
    i = 0x5f375a86 - (i >> 1);
    y = Float.intBitsToFloat(i);
    y = y * (1.5F - (x2 * y * y));
    y = y * (1.5F - (x2 * y * y)); //Newton iteration, more accurate

    sqrt = Math.round(1.0F / y);
} else {
    //Carmack hack gives incorrect answer for n >= 11043908100.
    sqrt = (long) Math.sqrt(n);
}
6
répondu Jonny Heggheim 2009-05-25 05:38:24
la source

j'ai vérifié tous les résultats possibles lorsque les n derniers bits d'un carré est observée. En examinant successivement plus de bits, jusqu'à 5/6 entrées peuvent être éliminés. J'ai conçu ceci pour implémenter L'algorithme de factorisation de Fermat, et c'est très rapide là-bas.

public static boolean isSquare(final long val) {
   if ((val & 2) == 2 || (val & 7) == 5) {
     return false;
   }
   if ((val & 11) == 8 || (val & 31) == 20) {
     return false;
   }

   if ((val & 47) == 32 || (val & 127) == 80) {
     return false;
   }

   if ((val & 191) == 128 || (val & 511) == 320) {
     return false;
   }

   // if((val & a == b) || (val & c == d){
   //   return false;
   // }

   if (!modSq[(int) (val % modSq.length)]) {
        return false;
   }

   final long root = (long) Math.sqrt(val);
   return root * root == val;
}

le dernier bit de pseudocode peut être utilisé pour étendre les tests pour éliminer plus de valeurs. Les essais ci-dessus sont pour k = 0, 1, 2, 3

  • est un de la forme (3 << 2k) - 1
  • B est de la forme (2 << 2k)
  • c est de la forme (2 << 2k + 2) - 1
  • D est de la forme (2 << 2k - 1) * 10

    il teste d'abord si elle a un résidu carré avec des modules de puissance de deux, puis il teste basé sur un module final, puis il utilise les mathématiques.sqrt faire un test final. Je suis venu avec l'idée du haut du poteau, et ai essayé de s'étendre sur elle. J'apprécie tous les commentaires ou suggestion.

    mise à Jour: à l'Aide du test par un module, (modSq) et un module de base de 44352, mes essais dans 96% du temps de l'un à l'OP de mise à jour pour les nombres jusqu'à 1 000 000 000 d'.

  • 5
    répondu Fractaly 2011-12-05 08:29:48
    la source

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

    int main()
    {
        unsigned int c1=0 ,c2 = 0;  
        unsigned int x = 0;  
        unsigned int p = 0;  
        int k1 = 0;  
        scanf("%d",&p);  
        if(p % 2 == 0) {  
            x = p/2; 
        }  
        else {  
            x = (p/2) +1;  
        }  
        while(x) 
        {
            if((x*x) > p) {  
                c1 = x;  
                x = x/2; 
            }else {  
                c2 = x;  
                break;  
            }  
        }  
        if((p%2) != 0)  
            c2++;
    
        while(c2 < c1) 
        {  
            if((c2 * c2 ) == p) {  
                k1 = 1;  
                break;  
            }  
            c2++; 
        }  
        if(k1)  
            printf("\n Perfect square for %d", c2);  
        else  
            printf("\n Not perfect but nearest to :%d :", c2);  
        return 0;  
    }  
    
    5
    répondu nabam serbang 2018-03-06 00:50:20
    la source

    si la vitesse est un problème, pourquoi ne pas séparer l'ensemble le plus couramment utilisé d'entrées et leurs valeurs à une table de recherche et puis faire tout algorithme magique optimisé que vous avez mis au point pour les cas exceptionnels?

    1
    répondu Elijah 2008-11-18 02:29:58
    la source

    il devrait être possible d'emballer le 'ne peut pas être un carré parfait si les derniers x chiffres sont N' beaucoup plus efficace que cela! Je vais utiliser des ints java 32 bits, et produire assez de données pour vérifier les 16 derniers bits du nombre - c'est 2048 valeurs int hexadécimales.

    ...

    Ok. Soit j'ai rencontré une théorie des nombres qui me dépasse un peu, soit il y a un bug dans mon code. En tout cas, voici le code:

    public static void main(String[] args) {
        final int BITS = 16;
    
        BitSet foo = new BitSet();
    
        for(int i = 0; i< (1<<BITS); i++) {
            int sq = (i*i);
            sq = sq & ((1<<BITS)-1);
            foo.set(sq);
        }
    
        System.out.println("int[] mayBeASquare = {");
    
        for(int i = 0; i< 1<<(BITS-5); i++) {
            int kk = 0;
            for(int j = 0; j<32; j++) {
                if(foo.get((i << 5) | j)) {
                    kk |= 1<<j;
                }
            }
            System.out.print("0x" + Integer.toHexString(kk) + ", ");
            if(i%8 == 7) System.out.println();
        }
        System.out.println("};");
    }
    

    et voici les résultats:

    (ndlr: gommés pour de faibles performances dans l'embellir.js; voir l'historique des révisions pour voir.)

    1
    répondu paulmurray 2010-01-07 14:00:07
    la source

    voici le moyen le plus simple et le plus concis, bien que je ne sais pas comment il se compare en termes de cycles CPU. Cela fonctionne très bien si vous ne souhaitez savoir si la racine est un nombre entier. Si vous vous souciez vraiment si c'est un entier, vous pouvez également trouver. Voici une fonction simple (et pure):

    public static boolean isRootWhole(double number) {
        return Math.sqrt(number) % 1 == 0;
    }
    

    si vous n'avez pas besoin de micro-optimisation, cette réponse est meilleure en termes de simplicité et de maintenabilité. Si vous aurez des nombres négatifs, peut-être vous voulez utiliser les Mathématiques.abs() sur le nombre d'argument que les Mathématiques.argument sqrt ().

    sur mon processeur Intel i7-4790 de 3,6 Ghz, une exécution de cet algorithme sur 0 - 10,000,000 a pris en moyenne 35 - 37 nanosecondes par calcul. J'ai fait 10 tirages séquentiels, imprimant le temps moyen passé sur chacun des 10 millions de calculs de la sqrt. Chaque course a pris un peu plus de 600 ms à compléter.

    si vous effectuez un nombre moindre de calculs, les calculs antérieurs prennent un peu plus de temps.

    1
    répondu Steve Storck 2017-12-05 15:45:34
    la source

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

    0
    répondu Celestial M Weasel 2008-11-17 16:48:29
    la source

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

    en ce qui concerne votre meilleur, je vois deux micro-optimisations:

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

    i. e:

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

    encore mieux pourrait être un simple

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

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

    0
    répondu Ben 2009-03-11 16:25:39
    la source

    " je suis à la recherche du moyen le plus rapide pour déterminer si une valeur longue est un carré parfait (i.e. sa racine carrée est un autre entier)."

    les réponses sont impressionnantes, mais je n'ai pas vu un simple chèque:

    vérifier si le premier nombre sur la droite du long il un membre de l'ensemble (0,1,4,5,6,9) . Si ce n'est pas le cas, alors il ne peut pas être un "carré parfait".

    par exemple.

    4567-ne peut pas être un carré parfait.

    0
    répondu dstibbe 2009-09-24 13:46:57
    la source

    Je ne suis pas sûr que ce soit le moyen le plus rapide, mais c'est quelque chose que j'ai découvert (il y a longtemps au lycée) quand je m'ennuyais et que je jouais avec ma calculatrice pendant les cours de mathématiques. À l'époque, j'étais vraiment étonné de voir ce qui fonctionnait...

    public static boolean isIntRoot(int number) {
        return isIntRootHelper(number, 1);
    }
    
    private static boolean isIntRootHelper(int number, int index) {
        if (number == index) {
            return true;
        }
        if (number < index) {
            return false;
        }
        else {
            return isIntRootHelper(number - 2 * index, index + 1);
        }
    }
    
    -1
    répondu MWB 2018-09-26 19:32:44
    la source

    ne sait pas plus rapide, mais le plus simple est de prendre la racine carrée de la façon normale, multiplier le résultat par lui-même, et voir si elle correspond à votre valeur originale.

    puisque nous parlons d'entiers ici, le jeûne impliquerait probablement une collection où vous pouvez juste faire une recherche.

    -2
    répondu Joel Coehoorn 2008-11-17 17:49:26
    la source

    Autres questions sur java optimization math perfect-square