Pregunta La forma más rápida de determinar si la raíz cuadrada de un entero es un número entero


Estoy buscando la forma más rápida de determinar si long valor es un cuadrado perfecto (es decir, su raíz cuadrada es otro entero):

  1. Lo hice de la manera más fácil, usando el Math.sqrt incorporado () función, pero me pregunto si hay una manera de hacerlo más rápido por restringirse a un dominio de solo entero.
  2. Mantener una tabla de búsqueda es impráctico (ya que hay 231.5 enteros cuyo cuadrado es menor que 263)

Aquí está la manera simple y directa en que lo estoy haciendo ahora:

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

  long tst = (long)(Math.sqrt(n) + 0.5);
  return tst*tst == n;
}

Notas: Estoy usando esta función en muchos Proyecto Euler problemas. Entonces, nadie más tendrá que mantener este código. Y este tipo de micro-optimización realmente podría hacer una diferencia, ya que parte del desafío es hacer cada algoritmo en menos de un minuto, y esta función deberá llamarse millones de veces en algunos problemas.


Una nueva solución publicada por A. Rex ha demostrado ser aún más rápido. En una ejecución de los primeros mil millones de enteros, la solución solo requirió el 34% del tiempo que usó la solución original. Mientras que el truco de John Carmack es un poco mejor para los pequeños valores de norte, el beneficio comparado con esta solución es bastante pequeño.

Aquí está la solución A. Rex, convertida a 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
};

He intentado las diferentes soluciones presentadas a continuación.

  • Después de exhaustivas pruebas, descubrí que agregar 0.5 al resultado de Math.sqrt () no es necesario, al menos no en mi máquina.
  • los John Carmack hackeo fue más rápido, pero dio resultados incorrectos a partir de n = 410881. Sin embargo, según lo sugerido por BobbyShaftoe, podemos usar el truco de Carmack para n <410881.
  • El método de Newton fue un poco más lento que Math.sqrt(). Esto es probablemente porque Math.sqrt() utiliza algo similar al Método de Newton, pero implementado en el hardware, por lo que es mucho más rápido que en Java. Además, el Método de Newton aún requería el uso de dobles.
  • Un método de Newton modificado, que utilizaba algunos trucos para involucrar solamente matemáticas enteras, requería algunos intentos de hack para evitar el desbordamiento (quiero que esta función funcione con todos los enteros con signo de 64 bits positivos), y aún era más lento que Math.sqrt().
  • La chuleta binaria fue aún más lenta. Esto tiene sentido porque la tajada binaria requerirá, en promedio, 16 pasadas para encontrar la raíz cuadrada de un número de 64 bits.

La única sugerencia que mostró mejoras fue hecha por John D. Cook. Puede observar que el último dígito hexadecimal (es decir, los últimos 4 bits) de un cuadrado perfecto debe ser 0, 1, 4 o 9. Esto significa que el 75% de los números se pueden eliminar inmediatamente como posibles cuadrados. La implementación de esta solución dio como resultado una reducción del 50% en el tiempo de ejecución.

Trabajando desde la sugerencia de John, investigué propiedades de la última norte pedazos de un cuadrado perfecto. Al analizar los últimos 6 bits, encontré que solo 12 de 64 valores son posibles para los últimos 6 bits. Esto significa que el 81% de los valores se pueden eliminar sin utilizar ninguna matemática. La implementación de esta solución dio una reducción adicional del 8% en el tiempo de ejecución (en comparación con mi algoritmo original). El análisis de más de 6 bits da como resultado una lista de posibles bits de finalización que es demasiado grande para ser práctico.

Aquí está el código que he usado, que se ejecuta en el 42% del tiempo requerido por el algoritmo original (basado en una ejecución sobre los primeros 100 millones de enteros). Para valores de norte menos de 410881, se ejecuta en solo el 29% del tiempo requerido por el algoritmo 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;
  }
}

Notas:

  • De acuerdo con las pruebas de John, el uso or declaraciones es más rápido en C ++ que usando un switch, pero en Java y C # parece que no hay diferencia entre or y switch.
  • También intenté hacer una tabla de búsqueda (como una matriz estática privada de 64 valores booleanos). Entonces, en lugar de cambiar o or declaración, solo diría if(lookup[(int)(n&0x3F)]) { test } else return false;. Para mi sorpresa, esto fue (solo un poco) más lento. No estoy seguro por qué.  Esto es porque los límites de la matriz se verifican en Java.

1209


origen


Respuestas:


Descubrí un método que funciona ~ 35% más rápido que tu código sqrt de 6 bits + Carmack +, al menos con mi CPU (x86) y el lenguaje de programación (C / C ++). Sus resultados pueden variar, especialmente porque no sé cómo se desarrollará el factor Java.

Mi enfoque es triple:

  1. Primero, filtra las respuestas obvias. Esto incluye números negativos y mirando los últimos 4 bits. (Encontré que mirar los últimos seis no ayudó.) También respondo sí por 0. (Al leer el código a continuación, tenga en cuenta que mi opinión es int64 x.)
    if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) )
        return false;
    if( x == 0 )
        return true;
  2. A continuación, compruebe si se trata de un módulo cuadrado 255 = 3 * 5 * 17. Como se trata de un producto de tres primos distintos, solo aproximadamente 1/8 de los residuos mod 255 son cuadrados. Sin embargo, en mi experiencia, llamar al operador de módulo (%) cuesta más que el beneficio que se obtiene, así que utilizo trucos de bits que implican 255 = 2 ^ 8-1 para calcular el residuo. (Para bien o para mal, no estoy usando el truco de leer bytes individuales de una palabra, solo bit a bit, y cambia).
    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



Llego bastante tarde a la fiesta, pero espero brindar una mejor respuesta; más corto y (suponiendo que mi punto de referencia es correcto) también mucho Más rápido.

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

La primera prueba atrapa la mayoría de los no cuadrados rápidamente. Utiliza una tabla de 64 elementos empaquetada en un largo, por lo que no hay costo de acceso a la matriz (indirección y límites de verificación). Para un uniformemente al azar long, hay un 81.25% de probabilidades de terminar aquí.

La segunda prueba capta todos los números que tienen un número impar de dos en su factorización. El método Long.numberOfTrailingZeros es muy rápido ya que obtiene JIT-ed en una sola instrucción i86.

Después de descartar los ceros finales, la tercera prueba maneja los números que terminan con 011, 101 o 111 en binario, que no son cuadrados perfectos. También se preocupa por los números negativos y también maneja 0.

La prueba final se remonta a double aritmética. Como double tiene solo 53 bits de mantisa, la conversión de long a double incluye redondeo para grandes valores. No obstante, la prueba es correcta (a menos que prueba Está Mal).

Intentar incorporar la idea mod255 no fue exitoso.


260



Tendrás que hacer una evaluación comparativa. El mejor algoritmo dependerá de la distribución de tus entradas.

Su algoritmo puede ser casi óptimo, pero es posible que desee hacer una comprobación rápida para descartar algunas posibilidades antes de llamar a su rutina de raíz cuadrada. Por ejemplo, mira el último dígito de tu número en hexadecimal haciendo un poco de "y". Los cuadrados perfectos solo pueden terminar en 0, 1, 4 o 9 en la base 16, por lo que para el 75% de tus entradas (suponiendo que estén distribuidas uniformemente) puedes evitar una llamada a la raíz cuadrada a cambio de un giro muy rápido.

Kip comparó el siguiente código implementando el truco hexagonal. Al probar los números del 1 al 100 000 000, este código corrió dos veces más rápido que el 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;
    }
}

Cuando probé el código análogo en C ++, en realidad corrió más lento que el original. Sin embargo, cuando eliminé la declaración de cambio, el truco de hexágono volvió a hacer que el código sea dos veces más rápido.

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

La eliminación de la declaración del interruptor tuvo poco efecto en el código C #.


118



Estaba pensando en los tiempos horribles que pasé en el curso de Análisis Numérico.

Y luego recuerdo, había una función dando vueltas alrededor de la 'red del código fuente 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;
}

Que básicamente calcula una raíz cuadrada, usando la función de aproximación de Newton (no puedo recordar el nombre exacto).

Debería ser útil e incluso podría ser más rápido, ¡es de uno de los mejores juegos de software de identificación!

Está escrito en C ++, pero no debería ser demasiado difícil volver a utilizar la misma técnica en Java una vez que tenga la idea:

Originalmente lo encontré en: http://www.codemaestro.com/reviews/9

El método de Newton explicado en wikipedia: http://en.wikipedia.org/wiki/Newton%27s_method

Puede seguir el enlace para obtener más explicaciones sobre cómo funciona, pero si no le importa demasiado, entonces esto es más o menos lo que recuerdo al leer el blog y tomar el curso de Análisis Numérico:

  • el * (long*) &y es básicamente una función rápida de conversión a larga, por lo que las operaciones de enteros se pueden aplicar a los bytes sin formato.
  • el 0x5f3759df - (i >> 1); línea es un valor semilla precalculado para la función de aproximación.
  • el * (float*) &i convierte el valor de nuevo a punto flotante.
  • el y = y * ( threehalfs - ( x2 * y * y ) ) line bascialmente itera el valor sobre la función nuevamente.

La función de aproximación proporciona valores más precisos cuanto más itera la función sobre el resultado. En el caso de Quake, una iteración es "suficientemente buena", pero si no fuera por ti ... entonces podrías agregar tanta iteración como necesites.

Esto debería ser más rápido, ya que reduce el número de operaciones de división hechas en naive square rooting a una división simple de 2 (en realidad una * 0.5F operación de multiplicación) y reemplazarlo con un número fijo de operaciones de multiplicación.


41



No estoy seguro si sería más rápido, o incluso exacto, pero podrías usar Raíz mágica cuadrada de John Carmack, algoritmo para resolver la raíz cuadrada más rápido. Probablemente puedas probar esto fácilmente para todos los enteros de 32 bits posibles, y validar que realmente obtuviste resultados correctos, ya que es solo una aproximación. Sin embargo, ahora que lo pienso, usar dobles también se está aproximando, así que no estoy seguro de cómo eso podría entrar en juego.


33



Si haces un corte binario para tratar de encontrar la raíz cuadrada "derecha", puedes detectar bastante fácilmente si el valor que tienes está lo suficientemente cerca como para decir:

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

Entonces habiendo calculado n^2, las opciones son:

  • n^2 = target: hecho, devuelve verdadero
  • n^2 + 2n + 1 > target > n^2 : estás cerca, pero no es perfecto: devuelve falso
  • n^2 - 2n + 1 < target < n^2 : ídem
  • target < n^2 - 2n + 1 : chuleta binaria en un nivel inferior n
  • target > n^2 + 2n + 1 : chop binario en un nivel superior n

(Lo siento, esto usa n como su conjetura actual, y target para el parámetro. Disculpa por la confusión!)

No sé si esto será más rápido o no, pero vale la pena intentarlo.

EDITAR: La tajada binaria no tiene que abarcar todo el rango de enteros, tampoco (2^x)^2 = 2^(2x), así que una vez que hayas encontrado el bit más alto en tu objetivo (lo que se puede hacer con un truco de intercambio de bits, no recuerdo exactamente cómo) puedes obtener rápidamente un rango de posibles respuestas. Eso sí, una chuleta binaria ingenua solo va a tomar hasta 31 o 32 iteraciones.


30



Ejecuté mi propio análisis de varios de los algoritmos en este hilo y obtuve algunos resultados nuevos. Puede ver los resultados anteriores en el historial de edición de esta respuesta, pero no son precisos, ya que cometí un error y perdí el tiempo analizando varios algoritmos que no están cerca. Sin embargo, sacando lecciones de varias respuestas diferentes, ahora tengo dos algoritmos que aplastan al "ganador" de este hilo. Aquí está lo esencial que hago de manera diferente a todos los demás:

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

Sin embargo, esta línea simple, que la mayoría de las veces agrega una o dos instrucciones muy rápidas, simplifica en gran medida la switch-case declaración en una declaración if. Sin embargo, puede aumentar el tiempo de ejecución si muchos de los números probados tienen factores importantes de potencia de dos.

Los algoritmos a continuación son los siguientes:

  • Internet - La respuesta publicada de Kip
  • Durron - Mi respuesta modificada usando la respuesta de un solo paso como base
  • DurronDos - Mi respuesta modificada usando la respuesta de dos pasos (por @JohnnyHeggheim), con algunas otras pequeñas modificaciones.

Aquí hay un tiempo de ejecución de muestra si los números se generan utilizando 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

Y aquí hay un tiempo de ejecución de muestra si se ejecuta solo en el primer millón de largos:

 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

Como puedes ver, DurronTwo funciona mejor para grandes entradas, ya que usa el truco de magia muy a menudo, pero se destruye en comparación con el primer algoritmo y Math.sqrt porque los números son mucho más pequeños. Mientras tanto, el más simple Durron es un gran ganador porque nunca tiene que dividirse por 4 muchas veces en los primeros millones de números.

Aquí está 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;
}

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

Y mi arnés de referencia: (Requiere Google calibre 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);
    }
}

ACTUALIZAR: Creé un nuevo algoritmo que es más rápido en algunos escenarios, más lento en otros, obtuve diferentes puntos de referencia basados ​​en diferentes entradas. Si calculamos el módulo 0xFFFFFF = 3 x 3 x 5 x 7 x 13 x 17 x 241, podemos eliminar el 97.82% de los números que no pueden ser cuadrados. Esto se puede (hacer) en una línea, con 5 operaciones a nivel de bits:

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

El índice resultante es 1) el residuo, 2) el residuo + 0xFFFFFF, o 3) el residuo + 0x1FFFFFE. Por supuesto, necesitamos tener una tabla de búsqueda para los residuos módulo 0xFFFFFF, que se trata de un archivo de 3mb (en este caso almacenado como números decimales de texto ascii, no es óptimo, pero se puede mejorar claramente con un ByteBuffer Etcétera. Pero dado que eso es un cálculo previo, no importa tanto. Puedes encontrar el archivo aquí (o generarlo usted mismo):

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

Lo cargo en una boolean matriz como esta:

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

Ejemplo de tiempo de ejecución. Latió Durron (versión uno) en cada prueba que ejecuté.

 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



Debería ser mucho más rápido de usar El método de Newton para calcular el Entero Square Root, luego cuadre este número y verifique, como lo hace en su solución actual. El método de Newton es la base de la solución de Carmack mencionada en algunas otras respuestas. Debería poder obtener una respuesta más rápida ya que solo está interesado en la parte entera de la raíz, lo que le permite detener el algoritmo de aproximación más rápido.

Otra optimización que puedes probar: si Raíz digital de un número no termina en 1, 4, 7 o 9 el número es no un cuadrado perfecto Esto se puede utilizar como una forma rápida de eliminar el 60% de sus entradas antes de aplicar el algoritmo de raíz cuadrada más lenta.


14



Quiero que esta función funcione con todos   enteros positivos con signo de 64 bits

Math.sqrt() funciona con dobles como parámetros de entrada, por lo que no obtendrá resultados precisos para enteros más grandes que 2 ^ 53.


12



Solo para el registro, otro enfoque es usar la descomposición principal. Si cada factor de descomposición es par, entonces el número es un cuadrado perfecto. Entonces, lo que quieres es ver si un número se puede descomponer como producto de cuadrados de números primos. Por supuesto, no necesita obtener dicha descomposición, solo para ver si existe.

Primero construya una tabla de cuadrados de números primos que sean inferiores a 2 ^ 32. Esto es mucho más pequeño que una tabla de todos los enteros hasta este límite.

Una solución sería así:

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

Supongo que es un poco críptico. Lo que hace es verificar en cada paso que el cuadrado de un número primo divide el número de entrada. Si lo hace, entonces divide el número por el cuadrado, siempre que sea posible, para eliminar este cuadrado de la descomposición principal. Si por este proceso, llegamos a 1, entonces el número de entrada fue una descomposición del cuadrado de números primos. Si el cuadrado se vuelve más grande que el número mismo, entonces no hay manera de que este cuadrado, o cualquier otro cuadrado más grande, pueda dividirlo, por lo que el número no puede ser una descomposición de cuadrados de números primos.

Teniendo en cuenta que en la actualidad el "sqrt está hecho en hardware y la necesidad de calcular números primos aquí", creo que esta solución es mucho más lenta. Pero debería dar mejores resultados que la solución con sqrt, que no funcionará en 2 ^ 54, como dice mrzl en su respuesta.


11



Se ha señalado que el último d los dígitos de un cuadrado perfecto solo pueden tomar ciertos valores. El último d dígitos (en la base) b) de un número n es lo mismo que el resto cuando nestá dividido por bd, es decir. en notación C n % pow(b, d).

Esto se puede generalizar a cualquier módulo m, es decir. n % m se puede usar para descartar que un porcentaje de los números sea un cuadrado perfecto. El módulo que está utilizando actualmente es 64, que permite 12, es decir. 19% de los residuos, como posibles cuadrados. Con un poco de codificación encontré el módulo 110880, que solo permite 2016, es decir. 1.8% de los residuos como posibles cuadrados. Entonces, dependiendo del costo de una operación de módulo (es decir, división) y una búsqueda de tabla en lugar de una raíz cuadrada en su máquina, el uso de este módulo podría ser más rápido.

Por cierto, si Java tiene una forma de almacenar una matriz empaquetada de bits para la tabla de búsqueda, no la use. 110880 palabras de 32 bits no es mucha RAM en estos días y buscar una palabra de máquina va a ser más rápido que ir a buscar un solo bit.


10