raiz que pseudocodigo pseint para numero ejemplos definicion cuadrada calcule calcular algoritmo java math optimization perfect-square

java - que - La forma más rápida de determinar si la raíz cuadrada de un entero es un entero



algoritmo raiz cuadrada pseudocodigo (30)

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

  1. Lo he hecho de manera fácil, mediante el uso de la función Math.sqrt () incorporada, pero me pregunto si hay una manera de hacerlo más rápido al restringirte a un dominio de solo enteros.
  2. Mantener una tabla de búsqueda es impráctico (ya que hay aproximadamente 2 31.5 enteros cuyo cuadrado es menor que 2 63 ).

Aquí está la manera muy 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 problemas del Proyecto Euler . Así que nadie más tendrá que mantener este código. Y este tipo de microoptimización podría realmente 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 incluso más rápida. En una ejecución sobre los primeros 1 mil millones de enteros, la solución solo requirió el 34% del tiempo que usó la solución original. Mientras que el hack de John Carmack es un poco mejor para valores pequeños de n , el beneficio comparado con esta solución es bastante pequeño.

Aquí está la solución de 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 probado las diferentes soluciones presentadas a continuación.

  • Después de las pruebas exhaustivas, descubrí que no es necesario agregar 0.5 al resultado de Math.sqrt (), al menos no en mi máquina.
  • El hack de John Carmack fue más rápido, pero dio resultados incorrectos comenzando en n = 410881. Sin embargo, como lo sugiere BobbyShaftoe , podemos usar el hack de Carmack para n <410881.
  • El método de Newton fue un poco más lento que Math.sqrt() . Probablemente esto se deba a que Math.sqrt() usa 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 todavía requería el uso de dobles.
  • Un método de Newton modificado, que usaba algunos trucos para que solo se involucrara la matemática de enteros, requería algunos hacks para evitar el desbordamiento (quiero que esta función funcione con todos los enteros con signo positivo de 64 bits), y aún era más lento que Math.sqrt() .
  • El corte binario fue incluso más lento. Esto tiene sentido porque el corte binario requerirá en promedio 16 pases 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 resultó en una reducción de aproximadamente el 50% en el tiempo de ejecución.

A partir de la sugerencia de John, investigué las propiedades de los últimos n bits de un cuadrado perfecto. Al analizar los últimos 6 bits, encontré que solo 12 de los 64 valores son posibles para los últimos 6 bits. Esto significa que el 81% de los valores se pueden eliminar sin usar ningún cálculo matemático. 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 en los primeros 100 millones de enteros). Para valores de n 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 son más rápidos en C ++ que en el uso de un switch , pero en Java y C # no parece haber diferencia entre el switch or y el.
  • También intenté hacer una tabla de búsqueda (como una matriz estática privada de 64 valores booleanos). Luego, en lugar de un modificador o una declaración, solo diría if(lookup[(int)(n&0x3F)]) { test } else return false; . Para mi sorpresa, esto fue (un poco) más lento. No estoy seguro de por qué. Esto se debe a que los límites de la matriz se verifican en Java .

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

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

Método de Newton con aritmética de enteros.

Si desea evitar operaciones no enteras, puede utilizar el siguiente método. Básicamente utiliza el método de Newton modificado para la aritmética de enteros.

/** * Test if the given number is a perfect square. * @param n Must be greater than 0 and less * than Long.MAX_VALUE. * @return <code>true</code> if n is a perfect * square, or <code>false</code> otherwise. */ public static boolean isSquare(long n) { long x1 = n; long x2 = 1L; while (x1 > x2) { x1 = (x1 + x2) / 2L; x2 = n / x1; } return x1 == x2 && n % x1 == 0L; }

Esta implementación no puede competir con las soluciones que utiliza Math.sqrt. Sin embargo, su rendimiento puede mejorarse utilizando los mecanismos de filtrado descritos en algunas de las otras publicaciones.

Descubrí un método que funciona ~ 35% más rápido que su código de 6 bits + Carmack + sqrt, al menos con mi CPU (x86) y 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. (Descubrí que mirar los últimos seis no ayudó.) También respondo que sí para 0. (Al leer el siguiente código, tenga en cuenta que mi entrada 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, verifique si es un módulo cuadrado 255 = 3 * 5 * 17. Como se trata 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, por lo que utilizo trucos de bits con 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 en el modo de bits y los turnos).

    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. Para comprobar realmente si el residuo es un cuadrado, busco la respuesta en una tabla precomputada.

    if( bad255[y] ) return false; // However, I just use a table of size 512

  3. Finalmente, intente calcular la raíz cuadrada utilizando un método similar al lema de Hensel . (No creo que sea aplicable directamente, pero funciona con algunas modificaciones). Antes de hacer eso, divido todos los poderes de 2 con una búsqueda binaria:

    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; En este punto, para que nuestro número sea un cuadrado, debe ser 1 mod 8.

    if((x & 7) != 1) return false; La estructura básica del lema de Hensel es la siguiente. (Nota: código no probado; si no funciona, intente t = 2 u 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. La idea es que en cada iteración, agregue un bit a r, la raíz cuadrada "actual" de x; Cada raíz cuadrada es precisa en el módulo una potencia mayor y mayor de 2, es decir, t / 2. Al final, r y t / 2-r serán raíces cuadradas de x módulo t / 2. (Tenga en cuenta que si r es una raíz cuadrada de x, entonces también lo es -r. Esto es cierto incluso en los números de módulo, pero tenga cuidado, módulo algunos números, las cosas pueden tener incluso más de 2 raíces cuadradas; en particular, esto incluye potencias de 2. ) Debido a que nuestra raíz cuadrada real es menor que 2 ^ 32, en ese momento podemos verificar si r o t / 2-r son raíces cuadradas reales. En mi código actual, uso el siguiente bucle modificado:

    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) ); La aceleración aquí se obtiene de tres formas: valor de inicio precalculado (equivalente a ~ 10 iteraciones del bucle), salida anterior del bucle y omisión de algunos valores t. Para la última parte, miro z = r - x * x , y establezco que t es la mayor potencia de 2 dividiendo z con un pequeño truco. Esto me permite omitir t valores que no habrían afectado el valor de r de todos modos. El valor de inicio precalculado en mi caso selecciona el módulo de raíz cuadrada "positivo más pequeño" 8192.

Incluso si este código no funciona más rápido para usted, espero que disfrute algunas de las ideas que contiene. A continuación se muestra el código completo y probado, incluidas las tablas precomputadas.

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

Tendrás que hacer un benchmarking. El mejor algoritmo dependerá de la distribución de sus entradas.

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

Kip evaluó el siguiente código implementando el truco hexadecimal. Cuando se probaron los números del 1 al 100.000, este código se ejecutó el doble de 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 funcionó más lento que el original. Sin embargo, cuando eliminé la instrucción de cambio, el truco hexadecimal vuelve a hacer el código 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 instrucción de cambio tuvo poco efecto en el código C #.

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

Las respuestas son impresionantes, pero no pude ver una simple comprobación:

compruebe si el primer número a la derecha del miembro es un miembro del conjunto (0,1,4,5,6,9). Si no lo es, entonces no puede ser un ''cuadrado perfecto''.

p.ej.

4567 - no puede ser un cuadrado perfecto.

Debes deshacerte de la parte de N de 2 poderes desde el principio.

2ª Edición La expresión mágica para m debajo debería ser

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

y no como esta escrito

Final de la 2a edición

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

1ª Edición:

Mejora menor:

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

Fin de la 1ª edición

Ahora continúa como siempre. De esta manera, cuando llegas a la parte de punto flotante, ya te deshiciste de todos los números cuya parte de 2 potencias es impar (aproximadamente la mitad), y solo consideras 1/8 de lo que queda. Es decir, ejecuta la parte de punto flotante en el 6% de los números.

Esta es la implementación de Java más rápida que pude encontrar, utilizando una combinación de técnicas sugeridas por otros en este hilo.

  • Prueba mod-256
  • Prueba inexacta mod-3465 (evita la división de enteros a costa de algunos falsos positivos)
  • Raíz cuadrada de punto flotante, redondear y comparar con valor de entrada

También experimenté con estas modificaciones pero no ayudaron al rendimiento:

  • Prueba mod-255 adicional
  • Dividiendo el valor de entrada por potencias de 4.
  • Raíz cuadrada inversa rápida (para trabajar con valores altos de N necesita 3 iteraciones, suficientes para hacerla más lenta que la función de raíz cuadrada del hardware).

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

Esta es una revisión de decimal a binario del antiguo algoritmo de la calculadora Marchant (lo siento, no tengo una referencia), en Ruby, adaptado específicamente para esta pregunta:

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

Aquí hay un análisis de algo similar (por favor, no me rechaces por el estilo de codificación / olores o O / O torpe: es el algoritmo lo que cuenta, y C ++ no es mi idioma natal) En este caso, estamos buscando un residuo == 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; };

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

Y luego recuerdo, había esta función dando vueltas alrededor de la red desde el código de Fuente de Sismo:

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, utilizando la función de aproximación de Newton (no recuerdo el nombre exacto).

Debería ser utilizable e incluso podría ser más rápido, ¡es de uno de los juegos de fenomenal id software!

Está escrito en C ++, pero no debería ser demasiado difícil reutilizar 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 se explica en wikipedia: http://en.wikipedia.org/wiki/Newton%27s_method

Puedes seguir el enlace para obtener una explicación más detallada de cómo funciona, pero si no te importa mucho, entonces esto es más o menos lo que recuerdo de leer el blog y de tomar el curso de Análisis Numérico:

  • el * (long*) &yes básicamente una función rápida-convertir-a larga operaciones de modo enteros se pueden aplicar en los bytes sin formato.
  • la 0x5f3759df - (i >> 1);línea es un valor de semilla precalculado para la función de aproximación.
  • El * (float*) &iconvierte el valor de nuevo a punto flotante.
  • La y = y * ( threehalfs - ( x2 * y * y ) )línea básicamente repite 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 "lo suficientemente buena", pero si no fuera por ti ... entonces podrías agregar la iteración que necesites.

Esto debería ser más rápido, ya que reduce el número de operaciones de división realizadas en el cuadradillo ingenuo hacia una simple división por 2 (en realidad es una * 0.5Foperación de multiplicación) y lo reemplaza por un número fijo de operaciones de multiplicación.

La siguiente simplificación de la solución de maaartinus parece reducir algunos puntos porcentuales del tiempo de ejecución, pero no soy lo suficientemente bueno como punto de referencia para producir una referencia en la que pueda confiar:

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

Valdría la pena comprobar cómo omitir la primera prueba,

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

afectaría el rendimiento.

Si desea velocidad, dado que sus enteros son de tamaño finito, sospecho que la forma más rápida sería (a) particionar los parámetros por tamaño (por ejemplo, en categorías por el conjunto de bits más grande), luego comparar el valor con una matriz de cuadrados perfectos dentro de ese rango

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

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

Así que habiendo calculado n^2, las opciones son:

  • n^2 = target : hecho, regreso 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 : picado binario en un inferior n
  • target > n^2 + 2n + 1 : binario picar en un alto n

(Lo sentimos, esto se usa ncomo su conjetura actual y targetpara el parámetro. ¡Discúlpese por la confusión!)

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

EDITAR: el corte binario no tiene que incluir toda la gama de enteros, (2^x)^2 = 2^(2x)así que una vez que haya encontrado el bit de conjunto superior en su objetivo (lo que se puede hacer con un truco de retoque de bits; olvido exactamente cómo) Usted puede obtener rápidamente una gama de posibles respuestas. Tenga en cuenta que un truco binario ingenuo solo tomará 31 o 32 iteraciones.

Si la velocidad es una preocupación, ¿por qué no dividir el conjunto de entradas y sus valores más comúnmente usados ​​en una tabla de búsqueda y luego hacer cualquier algoritmo mágico optimizado que se haya creado para los casos excepcionales?

¡Debería ser posible empaquetar el ''no puede ser un cuadrado perfecto si los últimos X dígitos son N'' mucho más eficientemente que eso! Usaré java 32 bit ints y produciré datos suficientes para verificar los últimos 16 bits del número, eso es 2048 valores int hexadecimales.

...

De acuerdo.O me he topado con alguna teoría numérica que está un poco más allá de mí, o hay un error en mi código. En cualquier caso, aquí está el código:

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

Y aquí están los resultados:

(ed: elidido por rendimiento deficiente en prettify.js; ver el historial de revisiones para ver).

Llego tarde a la fiesta, pero espero dar una mejor respuesta; Más corto y (asumiendo que mi benchmark es correcto) también mucho faster .

long goodMask; // 0xC840C04048404040 computed below { for (int i=0; i<64; ++i) goodMask |= Long.MIN_VALUE >>> (i*i); } public boolean isSquare(long x) { // This tests if the 6 least significant bits are right. // Moving the to be tested bit to the highest position saves us masking. if (goodMask << x >= 0) return false; final int numberOfTrailingZeros = Long.numberOfTrailingZeros(x); // Each square ends with an even number of zeros. if ((numberOfTrailingZeros & 1) != 0) return false; x >>= numberOfTrailingZeros; // Now x is either 0 or odd. // In binary each odd square ends with 001. // Postpone the sign test until now; handle zero in the branch. if ((x&7) != 1 | x <= 0) return x == 0; // Do it in the classical way. // The correctness is not trivial as the conversion from long to double is lossy! final long tst = (long) Math.sqrt(x); return tst * tst == x; }

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 (controles de dirección y límites). Para un long aleatorio uniforme, hay un 81.25% de probabilidad de terminar aquí.

La segunda prueba captura 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 eliminar 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 cae de nuevo a la aritmética double . Como el double tiene solo una mantisa de 53 bits, la conversión de long a double incluye el redondeo para valores grandes. No obstante, la prueba es correcta (a menos que la proof sea ​​incorrecta).

Tratar de incorporar la idea mod255 no tuvo éxito.

Con respecto al método Carmac, parece que sería bastante fácil repetir una vez más, lo que debería duplicar el número de dígitos de precisión. Es, después de todo, un método iterativo extremadamente truncado: el de Newton, con una muy buena primera aproximación.

En cuanto a su mejor momento actual, veo dos micro-optimizaciones:

  • mueve el cheque vs. 0 después del cheque usando mod255
  • reorganice los poderes de división de cuatro para omitir todas las comprobaciones del caso habitual (75%).

Es decir:

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

Aún mejor podría ser un simple

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

Obviamente, sería interesante saber cuántos números se eliminan en cada punto de control; más bien dudo que los cheques sean verdaderamente independientes, lo que dificulta las cosas.

Debería ser mucho más rápido usar http://en.wikipedia.org/wiki/Newton%27s_method para calcular la raíz cuadrada entera , luego cuadrar este número y verificar, como lo hace en su solución actual. El método de Newton es la base de la solución Carmack mencionada en algunas otras respuestas. Debería poder obtener una respuesta más rápida, ya que solo le interesa la parte entera de la raíz, lo que le permite detener el algoritmo de aproximación antes.

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

El proyecto Euler se menciona en las etiquetas y muchos de los problemas requieren la verificación de números >> 2 ^ 64. La mayoría de las optimizaciones mencionadas anteriormente no funcionan fácilmente cuando se trabaja con un búfer de 80 bytes.

Utilicé java BigInteger y una versión ligeramente modificada del método de Newton, una que funciona mejor con enteros. El problema fue que los cuadrados exactos n ^ 2 convergieron a (n-1) en lugar de n porque n ^ 2-1 = (n-1) (n + 1) y el error final fue solo un paso por debajo del divisor final y el Algoritmo terminado. Fue fácil de arreglar agregando uno al argumento original antes de calcular el error. (Agrega dos para las raíces cúbicas, etc.)

Un buen atributo de este algoritmo es que puede saber inmediatamente si el número es un cuadrado perfecto: el error final (no la corrección) en el método de Newton será cero. Una simple modificación también le permite calcular rápidamente el piso (sqrt (x)) en lugar del entero más cercano. Esto es útil con varios problemas de Euler.

Esta es la forma más simple y concisa, aunque no sé cómo se compara en términos de ciclos de CPU. Esto funciona muy bien si solo deseas saber si la raíz es un número entero. Si realmente te importa si es un número entero, también puedes resolverlo. Aquí hay una función simple (y pura):

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

Si no necesita microoptimización, esta respuesta es mejor en términos de simplicidad y facilidad de mantenimiento. Si obtendrás números negativos, quizás quieras usar Math.abs () en el argumento del número como el argumento Math.sqrt ().

En mi CPU Intel i7-4790 de 3,6 Ghz, una ejecución de este algoritmo en 0 - 10,000,000 tomó un promedio de 35 - 37 nanosegundos por cálculo. Hice 10 ejecuciones secuenciales, imprimiendo el tiempo promedio empleado en cada uno de los diez millones de cálculos cuadrados. Cada ejecución total tomó solo un poco más de 600 ms en completarse.

Si está realizando un número menor de cálculos, los cálculos anteriores tardan un poco más.

La llamada sqrt no es perfectamente precisa, como se ha mencionado, pero es interesante e instructivo que no desaprueba las otras respuestas en términos de velocidad. Después de todo, la secuencia de instrucciones en lenguaje ensamblador para un sqrt es pequeña. Intel tiene una instrucción de hardware, que no es utilizada por Java, creo, porque no cumple con IEEE.

Entonces, ¿por qué es lento? Porque Java en realidad está llamando a una rutina de C a través de JNI, y en realidad es más lento hacerlo que llamar a una subrutina Java, que en sí misma es más lenta que hacerlo en línea. Esto es muy molesto, y Java debería haber encontrado una mejor solución, es decir, construir llamadas de biblioteca de punto flotante si es necesario. Oh bien.

En C ++, sospecho que todas las alternativas complejas perderían velocidad, pero no las he comprobado todas. Lo que hice, y lo que la gente de Java encontrará útil, es un simple truco, una extensión de las pruebas de casos especiales sugeridas por A. Rex. Utilice un solo valor largo como una matriz de bits, que no está marcada con límites. De esa manera, tienes búsqueda booleana de 64 bits.

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 rutina isPerfectSquare5 se ejecuta en aproximadamente 1/3 del tiempo en mi máquina core2 duo. Sospecho que más ajustes en la misma línea podrían reducir el tiempo en promedio, pero cada vez que verifica, está cambiando más pruebas por más eliminatorias, por lo que no puede ir mucho más lejos en esa carretera.

Ciertamente, en lugar de tener una prueba separada para el negativo, puede verificar los 6 bits altos de la misma manera.

Tenga en cuenta que todo lo que estoy haciendo es eliminar los cuadrados posibles, pero cuando tengo un caso potencial, tengo que llamar al original, en línea esPerfectSquare.

La rutina init2 se llama una vez para inicializar los valores estáticos de pp1 y pp2. Tenga en cuenta que en mi implementación en C ++, estoy usando unsigned long long, así que ya que está firmado, tendría que usar el operador >>>.

No hay una necesidad intrínseca de verificar los límites de la matriz, pero el optimizador de Java tiene que resolver esto rápidamente, así que no los culpo por eso.

Me gusta la idea de usar un método casi correcto en algunas de las entradas. Aquí hay una versión con un "offset" más alto. El código parece funcionar y pasa mi caso de prueba simple.

Sólo reemplaza tu:

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

código con este:

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

No estoy seguro de si sería más rápido, o incluso preciso, pero podría usar http://www.codemaestro.com/reviews/9 , algoritmo para resolver la raíz cuadrada más rápido. Probablemente podría probar esto fácilmente para todos los enteros de 32 bits posibles y validar que realmente obtuvo resultados correctos, ya que solo es una designación. Sin embargo, ahora que lo pienso, usar dobles también se está aproximando, así que no estoy seguro de cómo entraría en juego.

No sé si esto ha sido mencionado antes. Pero encontré una solución here :

int result = (int)(floor(sqrt(b)) - ceil(sqrt(a)) + 1);

Para el rendimiento, muy a menudo tienes que hacer algunos compromisos. Otros han expresado varios métodos, sin embargo, usted notó que el hackeo de Carmack fue más rápido hasta ciertos valores de N. Luego, debe marcar la "n" y si es menor que ese número N, use el hack de Carmack, de lo contrario use otro método descrito En las respuestas aquí.

Realicé mi propio análisis de varios de los algoritmos en este hilo y encontré algunos nuevos resultados. Puedes ver esos 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, al extraer lecciones de varias respuestas diferentes, ahora tengo dos algoritmos que aplastan al "ganador" de este hilo. Aquí está lo que hago 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 enormemente la switch-casedeclaración en una sola sentencia if. Sin embargo, puede agregarse al tiempo de ejecución si muchos de los números probados tienen factores significativos de poder de dos.

Los algoritmos a continuación son los siguientes:

  • Internet - respuesta publicada de Kip
  • Durron - Mi respuesta modificada utilizando la respuesta de un paso como base
  • DurronTwo - Mi respuesta modificada utilizando 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 usando 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, DurronTwofunciona mejor con entradas grandes, porque utiliza el truco de magia muy a menudo, pero se ve superado en comparación con el primer algoritmo y Math.sqrtporque los números son mucho menores. Mientras tanto, el más simple Durrones un gran ganador porque nunca tiene que dividirse por 4 muchas veces en el primer millón 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 calibre de Google 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); } }

ACTUALIZACIÓN: he creado un nuevo algoritmo que es más rápido en algunos escenarios, más lento en otros, he obtenido diferentes puntos de referencia basados ​​en diferentes entradas. Si calculamos 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 (más o menos) 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 + 0xFFFFFFo 3) el residuo + 0x1FFFFFE. Por supuesto, necesitamos tener una tabla de búsqueda para el módulo de residuos 0xFFFFFF, que se trata de un archivo de 3 mb (en este caso, almacenado como números decimales en texto ASCII, no es óptimo pero claramente mejorable con A ByteBuffery así sucesivamente. No importa mucho. Puede 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 carga en una booleanmatriz 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. Batió Durron(versión uno) en cada prueba que corrí.

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

Se ha señalado que los últimos ddígitos de un cuadrado perfecto solo pueden tomar ciertos valores. Los últimos ddígitos (en base b) de un número nson los mismos que el resto cuando nse divide por b d, es decir. en C notación n % pow(b, d).

Esto se puede generalizar a cualquier módulo m, es decir. n % mse puede usar para descartar algún porcentaje de números de ser cuadrados perfectos. 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 permite solo 2016, es decir. 1.8% de los residuos como posibles cuadrados. Por lo tanto, dependiendo del costo de una operación de módulo (es decir, la división) y una búsqueda de tabla frente a 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 de bits empaquetada para la tabla de búsqueda, no la use. 110880 Las palabras de 32 bits no son mucho RAM en estos días y la obtención de una palabra de máquina será más rápida que la obtención de un solo bit.

Solo para el registro, otro enfoque es usar la descomposición principal. Si todos los factores de la descomposición son pares, entonces el número es un cuadrado perfecto. Entonces, lo que desea es ver si un número puede descomponerse como un producto de cuadrados de números primos. Por supuesto, no es necesario obtener tal descomposición, solo para ver si existe.

Primero construye una tabla de cuadrados de números primos que sean más bajos que 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 los números primos. Si el cuadrado se vuelve más grande que el número en sí, entonces no hay forma de que este cuadrado, o cualquier 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 hoy en día el hardware y la necesidad de calcular los números primos aquí, supongo 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.

Teniendo en cuenta la longitud general de los bits (aunque he utilizado un tipo específico aquí), intenté diseñar algo simplista como se muestra a continuación. Se requiere un control simple y obvio para 0,1,2 o <0 inicialmente. Lo siguiente es simple en el sentido de que no intenta usar ninguna función matemática existente. La mayoría del operador puede ser reemplazado por operadores de bit a bit. Sin embargo, no he probado con ningún dato de referencia. No soy ni experto en matemáticas ni en diseño de algoritmos de computadora en particular, me encantaría verlo señalar un problema. Sé que hay muchas posibilidades de mejora allí.

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

Un problema entero merece una solución entera. Así

Haga una búsqueda binaria en los enteros (no negativos) para encontrar el mayor entero t tal que t**2 <= n. Entonces prueba si r**2 = nexactamente. Esto lleva tiempo O (log n).

Si no sabe cómo buscar binarios en los enteros positivos porque el conjunto no tiene límites, es fácil. Comenzando por calcular su función creciente f (arriba f(t) = t**2 - n) en potencias de dos. Cuando lo ves se vuelve positivo, has encontrado un límite superior. Entonces puedes hacer una búsqueda binaria estándar.

Verifiqué todos los resultados posibles cuando se observan los últimos n bits de un cuadrado. Al examinar sucesivamente más bits, se pueden eliminar hasta 5/6 de entradas. De hecho, diseñé esto para implementar el algoritmo de factorización de Fermat, y es muy rápido allí.

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

El último bit de pseudocódigo se puede usar para extender las pruebas y eliminar más valores. Las pruebas anteriores son para k = 0, 1, 2, 3

  • a es de la forma (3 << 2k) - 1
  • b es de la forma (2 << 2k)
  • c es de la forma (2 << 2k + 2) - 1
  • d es de la forma (2 << 2k - 1) * 10

    Primero comprueba si tiene un cuadrado residual con módulos de potencia de dos, luego prueba basándose en un módulo final, luego usa Math.sqrt para hacer una prueba final. Se me ocurrió la idea del primer puesto, e intenté extenderla. Agradezco cualquier comentario o sugerencia.

    Actualización: usando la prueba por un módulo, (modSq) y un módulo base de 44352, mi prueba se ejecuta en el 96% del tiempo de la actualización de OP para números de hasta 1,000,000,000.