La forma más rápida de determinar si un número entero de la raíz cuadrada es un número entero
https://stackoverflow.com/questions/295579
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estoy buscando la manera más rápida para determinar si un long el valor es un cuadrado perfecto (es decir,su raíz cuadrada es otro entero):
- Yo lo he hecho de la manera más fácil, mediante el uso de la incorporada en el
Math.sqrt()la función, pero me pregunto si hay una manera de hacerlo más rápido por restringir el mismo a entero-solo dominio. - El mantenimiento de una tabla de búsqueda es poco práctico (ya que hay acerca de 231.5 enteros cuyo cuadrado es menor que 263).
Aquí es muy simple y directo de la manera en que yo 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;
}
Nota:Yo estoy usando esta función en muchos Proyecto De Euler problemas.Así que nadie nunca lo va a tener que mantener este código.Y este tipo de micro-optimización de hecho, podría hacer una diferencia, ya que parte del desafío es hacer de cada algoritmo en menos de un minuto, y esta función tendrá que ser llamado millones de veces en algunos problemas.
He intentado de diferentes soluciones para el problema:
- Después de un exhaustivo proceso de pruebas, he encontrado que la adición de
0.5para el resultado de la Matemática.la función sqrt() no es necesario, al menos no en mi máquina. - El rápido inversa de la raíz cuadrada era más rápido, pero dio resultados incorrectos para n >= 410881.Sin embargo, como se sugiere por BobbyShaftoe, podemos utilizar el FISR hack para n < 410881.
- El método de Newton fue un poco más lento que
Math.sqrt().Esto es probablemente debido aMath.sqrt()utiliza algo similar al Método de Newton, pero implementado en el hardware, así que es mucho más rápido que en Java.También, el Método de Newton todavía se requiere el uso de dobles. - Modificado el método de Newton, que utiliza un par de trucos para que sólo se entero de que la matemática era involucrados, requiere algunos hacks para evitar el desbordamiento (quiero esta función para trabajar con todos los positivos de 64 bits enteros), y fue aún más lento que
Math.sqrt(). - Binario chop fue aún más lento.Esto tiene sentido porque el binario picar en promedio, requieren de 16 pases para encontrar la raíz cuadrada de 64-bit número.
- De acuerdo a Juan pruebas, el uso de
ordeclaraciones es más rápido en C++ que el uso de unswitch, pero en Java y C# no parece haber ninguna diferencia entreoryswitch. - También traté de hacer una tabla de búsqueda (como privada estática de la matriz de 64 valores booleanos).Entonces, en lugar de cambiar o
ordeclaración, sólo quiero decir queif(lookup[(int)(n&0x3F)]) { test } else return false;.Para mi sorpresa, esta era (sólo un poco) más lento.Esto es debido a que límites de la matriz se comprueban en Java.
Solución
Descubrí un método que funciona ~ 35% más rápido que sus 6 bits + Carmack + código 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:
- Primero, filtra las respuestas obvias. Esto incluye números negativos y mirar los últimos 4 bits. (Descubrí que mirar los últimos seis no ayudó.) También respondo que sí para 0. (Al leer el código a continuación, 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; - Luego, verifique si es un módulo cuadrado 255 = 3 * 5 * 17. Debido a que es 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, por lo que utilizo trucos de bits que involucran 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 turnos).
Para verificar si el residuo es un cuadrado, busco la respuesta en una tabla calculada previamente.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.if( bad255[y] ) return false; // However, I just use a table of size 512 - Finalmente, intente calcular la raíz cuadrada utilizando un método similar a Lema de Hensel . (No creo que sea aplicable directamente, pero funciona con algunas modificaciones). Antes de hacerlo, divido todas las potencias de 2 con una búsqueda binaria:
En este punto, para que nuestro número sea un cuadrado, debe ser 1 mod 8.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;
La estructura básica del lema de Hensel es la siguiente. (Nota: código no probado; si no funciona, intente t = 2 u 8.)if((x & 7) != 1) return false;
La idea es que en cada iteración, agregue un bit en r, el & Quot; current & Quot; raíz cuadrada de x; cada raíz cuadrada es un módulo preciso con una potencia cada vez 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 los números de módulo, pero tenga cuidado, algunos números de módulo, 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 real, uso el siguiente bucle modificado: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 aceleración aquí se obtiene de tres maneras: valor de inicio precalculado (equivalente a ~ 10 iteraciones del bucle), salida anterior del bucle y omitiendo algunos valores t. Para la última parte, miro aint64 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) );z = r - x * x, y establezco que t sea la potencia más grande de 2 dividiendo z con un poco de truco. Esto me permite omitir los valores t que no habrían afectado el valor de r de todos modos. El valor de inicio precalculado en mi caso selecciona & Quot; positivo más pequeño & Quot; raíz cuadrada módulo 8192.
Incluso si este código no funciona más rápido para usted, espero que disfrute algunas de las ideas que contiene. El código completo y probado sigue, incluidas las tablas calculadas previamente.
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;
}Otros consejos
Llego bastante tarde a la fiesta, pero espero dar 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 captura 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 verificación de límites). Para un long uniformemente aleatorio, 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 se JIT-ed en una sola instrucción i86.
Después de eliminar los ceros finales, la tercera prueba maneja los números que terminan en 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 recurre a double aritmética. Como <=> tiene solo 53 bits de mantisa,
la conversión de <=> a <=> incluye redondeo para valores grandes. No obstante, la prueba es correcta (a menos que prueba está mal).
Intentar incorporar la idea mod255 no tuvo éxito.
Tendrás que hacer algunos 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 comprobació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 un & Quot; y. & Quot; Los cuadrados perfectos solo pueden terminar en 0, 1, 4 o 9 en la base 16, por lo que para el 75% de sus entradas (suponiendo que estén distribuidas uniformemente) puede evitar una llamada a la raíz cuadrada a cambio de un poco de giro de bits muy rápido.
Kip comparó el siguiente código que implementa el truco hexadecimal. Al probar los números del 1 al 100,000,000, este código se ejecutó 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 funcionó más lento que el original. Sin embargo, cuando eliminé la declaración de cambio, el truco hexadecimal una vez más hizo que el código fuera el doble de 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 switch tuvo poco efecto en el código C #.
Estaba pensando en los horribles momentos que pasé 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 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 utilizable e incluso podría ser más rápido, es de uno de los fenomenales juegos de software de identificación!
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
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 mucho, entonces esto es más o menos lo que recuerdo al leer el blog y al tomar el curso de Análisis numérico:
- el
* (long*) &yes básicamente una función de conversión rápida a larga, por lo que se pueden aplicar operaciones enteras en los bytes sin procesar. - la línea
0x5f3759df - (i >> 1);es un valor semilla precalculado para la función de aproximación. - el
* (float*) &iconvierte el valor nuevamente a punto flotante. - la línea
y = y * ( threehalfs - ( x2 * y * y ) )básicamente 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 & Quot; suficientemente buena & Quot ;, pero si no fuera por usted ... entonces podría agregar tanta iteración como necesite.
Esto debería ser más rápido porque reduce el número de operaciones de división realizadas en el enraizamiento cuadrado ingenuo a una simple división por 2 (en realidad, una operación de multiplicación * 0.5F) y lo reemplaza con un número fijo de operaciones de multiplicación.
No estoy seguro de si sería más rápido, o incluso preciso, pero podría usar Raíz cuadrada mágica de John Carmack , algoritmo para resolver la raíz cuadrada más rápido. Probablemente podría probar esto fácilmente para todos los posibles enteros de 32 bits y validar que realmente obtuvo los resultados correctos, ya que es solo una aproximación. Sin embargo, ahora que lo pienso, el uso de dobles también se está aproximando, así que no estoy seguro de cómo entraría en juego.
Si haces un corte binario para tratar de encontrar el " right " raíz cuadrada, puede detectar con bastante facilidad si el valor que tiene es lo suficientemente cercano 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 false -
n^2 - 2n + 1 < target < n^2: ídem -
target < n^2 - 2n + 1: corte binario en unn inferior
-
target > n^2 + 2n + 1: corte binario en untarget superior
(Lo sentimos, esto usa (2^x)^2 = 2^(2x) como su estimación actual, y <=> para el parámetro. ¡Disculpe la confusión!)
No sé si será más rápido o no, pero vale la pena intentarlo.
EDITAR: El corte binario no tiene que abarcar todo el rango de enteros, ya sea <=>, por lo que una vez que haya encontrado el bit establecido superior en su objetivo (que se puede hacer con un truco de giro de bits ; Olvidé exactamente cómo) puede obtener rápidamente una variedad de respuestas potenciales. Eso sí, un ingenuo corte binario solo llevará hasta 31 o 32 iteraciones.
Me encontré con mi propio análisis de varios de los algoritmos en este hilo y vino para arriba con algunos de los nuevos resultados.Usted puede ver los resultados anteriores en la edición de la historia de esta respuesta, pero no es exacta, ya que he cometido un error, y la pérdida de tiempo el análisis de varios algoritmos que no son tan cercanos.Sin embargo, tirando de las lecciones de varias respuestas, ahora tengo dos algoritmos que aplastar el "ganador" de este hilo.Aquí está el núcleo cosa que me hace diferente de 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 simple línea, que la mayoría del tiempo se añade una o dos muy rápida de instrucciones, simplifica en gran medida la switch-case declaración en una instrucción if.Sin embargo, puede aumentar el tiempo de ejecución si muchos de la prueba los números tienen un poder significativo de dos factores.
Los algoritmos de abajo son como sigue:
- Internet - Kip publicado responder
- Durron - Mi modificado respuesta con la de un paso de respuesta como una base
- DurronTwo - Mi modificado respuesta usando el pase de dos respuesta (por @JohnnyHeggheim), con algunas otras modificaciones.
Aquí se muestra un ejemplo en tiempo de ejecución si los números son generados 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í se muestra un ejemplo en tiempo de ejecución si se ejecuta en el primer millón anhela sólo:
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 se puede ver, DurronTwo qué mejor para grandes entradas, porque se pone a usar el truco de magia muy a menudo, pero recibe una paliza en comparación con el primer algoritmo y Math.sqrt porque los números son mucho más pequeñas.Mientras tanto, el más sencillo Durron es un gran ganador, ya que nunca se ha de dividir por 4, muchas, muchas veces en el primer millón de números.
Aquí 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 punto de referencia arnés:(Requiere Google pinza de 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: Me he hecho un nuevo algoritmo que es más rápido en algunos escenarios, más lento que en otros, he llegado a diferentes puntos de referencia basados en diferentes entradas.Si calculamos el modulo 0xFFFFFF = 3 x 3 x 5 x 7 x 13 x 17 x 241, podemos eliminar 97.82% de los números que no pueden ser cuadrados.Esto puede ser (más o menos), hecho en una sola línea, con 5 operaciones a nivel de bit:
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, tenemos que tener una tabla de búsqueda para residuos modulo 0xFFFFFF, que es alrededor de un 3 mb por archivo (en este caso almacenados como texto ascii decimal de los números, no es óptima, pero claramente mejorables con un ByteBuffer y así sucesivamente.Pero ya que es el precálculo, no importa tanto. Usted puede encontrar el archivo aquí (o generar tú 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;
}
Me lo carga en la 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.Derrotó Durron (versión uno) en cada prueba que me encontré.
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
Debería ser mucho más rápido usar Método de Newton para calcular el Integer 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 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 es no 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.
Quiero que esta función funcione con todos enteros con signo positivo de 64 bits
Math.sqrt() funciona con dobles como parámetros de entrada, por lo que no obtendrá resultados precisos para enteros mayores que 2 ^ 53 .
Solo para el registro, otro enfoque es utilizar la descomposición primaria. Si cada factor de la descomposición es par, entonces el número es un cuadrado perfecto. Entonces, lo que quiere es ver si un número puede descomponerse como un 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 divida el número de entrada. Si lo hace, divide el número por el cuadrado tanto como sea posible, para eliminar este cuadrado de la descomposición primaria. 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 mismo, 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.
Dado el sqrt de hoy en día hecho en hardware y la necesidad de calcular 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á durante 2 ^ 54, como dice mrzl en su respuesta.
Un problema entero merece una solución entera. Por lo tanto
Realice una búsqueda binaria en los enteros (no negativos) para encontrar el mayor entero t tal que t**2 <= n. Luego pruebe si r**2 = n exactamente. Esto lleva tiempo O (log n).
Si no sabe cómo buscar binariamente los enteros positivos porque el conjunto no tiene límites, es fácil. Empiezas calculando tu función creciente f (arriba de f(t) = t**2 - n) en potencias de dos. Cuando vea que se vuelve positivo, ha encontrado un límite superior. Entonces puede hacer una búsqueda binaria estándar.
Se ha señalado que los últimos d dígitos de un cuadrado perfecto solo pueden tomar ciertos valores. Los últimos b dígitos (en base n) de un número n % pow(b, d) son los mismos que el resto cuando m se divide entre n % m<=> , es decir. en notación C <=>.
Esto se puede generalizar a cualquier módulo <=>, es decir. <=> se puede usar para descartar que algunos porcentajes de números sean 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 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 versus una raíz cuadrada en su máquina, usar este módulo podría ser más rápido.
Por cierto, si Java tiene una manera de almacenar una matriz de bits empaquetada para la tabla de búsqueda, no la use. 110880 Las palabras de 32 bits no tienen mucha RAM en estos días y recuperar una palabra de máquina será más rápido que recuperar un solo bit.
Para el rendimiento, a menudo tiene que hacer algunos compromisos. Otros han expresado varios métodos, sin embargo, notó que el hack de Carmack fue más rápido hasta ciertos valores de N. Luego, debe verificar & Quot; n & Quot; y si es menor que ese número N, use el truco de Carmack, de lo contrario use algún otro método descrito en las respuestas aquí.
Esta es la implementación de Java más rápida que se me ocurrió, usando una combinación de técnicas sugeridas por otros en este hilo.
- Prueba Mod-256
- Prueba Inexact mod-3465 (evita la división de enteros a costa de algunos falsos positivos)
- Raíz cuadrada de punto flotante, redondear y comparar con el valor de entrada
También experimenté con estas modificaciones, pero no ayudaron al rendimiento:
- Prueba adicional mod-255
- 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, lo suficiente para hacerlo más lento que la función de raíz cuadrada de 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;
}
}
}
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 en la evaluación comparativa para producir un punto de referencia en el 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.
Debe deshacerse de la parte de 2 potencias de N desde el principio.
Segunda edición La expresión mágica para m debajo debería ser
m = N - (N & (N-1));
y no como está escrito
Fin de la segunda 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;
Primera 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 primera edición
Ahora continúa como siempre. De esta manera, cuando llegas a la parte de coma flotante, ya te has deshecho de todos los números cuya parte de 2 potencias es impar (aproximadamente la mitad), y luego solo consideras 1/8 de lo que queda. Es decir. ejecuta la parte de coma flotante en el 6% de los números.
Esta es una reelaboración de decimal a binario del antiguo algoritmo de 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 una solución de algo similar (por favor, no me rechace por codificar estilos / olores u O / O torpe: es el algoritmo lo que cuenta, y C ++ no es mi idioma de origen). En este caso, estamos buscando residuos == 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;
};
La llamada sqrt no es perfectamente precisa, como se ha mencionado, pero es interesante e instructivo que no elimina 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 Java no utiliza, creo, porque no se ajusta a IEEE.
Entonces, ¿por qué es lento? Debido a que Java en realidad está llamando a una rutina C a través de JNI, y en realidad es más lento hacerlo que llamar a una subrutina Java, que en sí es más lenta que hacerlo en línea. Esto es muy molesto, y Java debería haber encontrado una solución mejor, es decir, incorporar llamadas de biblioteca de punto flotante si fuera necesario. Oh bien.
En C ++, sospecho que todas las alternativas complejas perderían velocidad, pero no las he verificado 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. Use un solo valor largo como una matriz de bits, que no esté marcada en los límites. De esa manera, tiene una 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 a lo largo de la misma línea podrían reducir el tiempo aún más en promedio, pero cada vez que verifica, está intercambiando más pruebas por más eliminación, por lo que no puede avanzar mucho más en ese camino.
Ciertamente, en lugar de tener una prueba de negativo por separado, puede verificar los 6 bits altos de la misma manera.
Tenga en cuenta que todo lo que estoy haciendo es eliminar posibles cuadrados, pero cuando tengo un caso potencial tengo que llamar al original, en línea, isPerfectSquare.
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, por lo que como está firmado, debería usar & Gt; & Gt; & Gt; operador.
No hay necesidad intrínseca de verificar los límites de la matriz, pero el optimizador de Java tiene que resolver esto bastante rápido, 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 & Quot; offset & Quot ;. El código parece funcionar y pasa mi caso de prueba simple.
Simplemente reemplace su:
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);
}
Proyecto de Euler se menciona en las etiquetas y los muchos problemas que requieren números de cuenta de cheques >> 2^64.La mayoría de las optimizaciones se mencionó anteriormente no funcionan fácilmente cuando se trabaja con un 80 bytes del búfer.
He usado java BigInteger y una versión ligeramente modificada del método de Newton, uno de los que mejor trabaja con números enteros.El problema era que exacto de plazas n^2 convergente a (n-1) en lugar de n porque n^2-1 = (n-1)(n+1) y el error final fue sólo un paso por debajo de la final divisor y el algoritmo termina.Era fácil solución mediante la adición de uno al argumento original antes de calcular el error.(Agregue dos de raíces cúbicas, etc.)
Un buen atributo de este algoritmo es que se puede saber inmediatamente si el número es un cuadrado perfecto - el error final (no de la corrección) en el método de Newton será cero.Una simple modificación también le permite calcular rápidamente floor(sqrt(x)) en lugar de al entero más cercano.Esto es útil con varios problemas de Euler.
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 las 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
Primero prueba si tiene un residual cuadrado con un módulo de potencia de dos, luego prueba en función de un módulo final, luego usa Math.sqrt para hacer una prueba final. Se me ocurrió la idea desde la publicación superior e intenté extenderla. Agradezco cualquier comentario o sugerencia.
Actualización: Utilizando la prueba por un módulo, (modSq) y una base de módulo de 44352, mi prueba se ejecuta en el 96% del tiempo del de la actualización del OP para números de hasta 1,000,000,000 .
Teniendo en cuenta la longitud de bits general (aunque he usado un tipo específico aquí), traté de diseñar algo simplista como se muestra a continuación. Verificación simple y obvia para 0,1,2 o & Lt; 0 se requiere inicialmente. Lo siguiente es simple en el sentido de que no intenta usar ninguna función matemática existente. La mayor parte del operador puede ser reemplazado por operadores de bits. Sin embargo, no he probado con ningún dato de referencia. No soy experto en matemáticas ni en diseño de algoritmos informáticos en particular, me encantaría verte señalando el 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;
}
No sé si esto se ha mencionado antes. Pero encontré una solución aquí :
int result = (int)(floor(sqrt(b)) - ceil(sqrt(a)) + 1);
Si la velocidad es una preocupación, ¿por qué no dividir el conjunto de entradas más comúnmente usado y sus valores en una tabla de búsqueda y luego hacer cualquier algoritmo mágico optimizado que se le haya ocurrido para los casos excepcionales?
¡Debería ser posible empacar el 'no puede ser un cuadrado perfecto si los últimos X dígitos son N' mucho más eficientemente que eso! Usaré java ints de 32 bits y produciré suficientes datos para verificar los últimos 16 bits del número, es decir, 2048 valores int hexadecimales.
...
Ok. O me he topado con alguna teoría de números 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 bajo rendimiento en prettify.js; ver el historial de revisiones para ver.)
Aquí está 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 desea 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 micro-optimización, esta respuesta es mejor en términos de simplicidad y facilidad de mantenimiento. Si va a obtener números negativos, quizás desee usar Math.abs () en el argumento de número como el argumento Math.sqrt ().
En mi CPU Intel i7-4790 de 3.6Ghz, una ejecución de este algoritmo en 0 - 10,000,000 tomó un promedio de 35 - 37 nanosegundos por cálculo. Hice 10 corridas secuenciales, imprimiendo el tiempo promedio dedicado a cada uno de los diez millones de cálculos cuadrados. Cada ejecución total tardó un poco más de 600 ms en completarse.
Si está realizando un número menor de cálculos, los cálculos anteriores demoran un poco más.
Aquí hay una solución de divide y vencerás.
Si la raíz cuadrada de un número natural (number) es un número natural (solution), puede determinar fácilmente un rango para <=> basado en el número de dígitos de <=>:
- <=> tiene 1 dígito: <=> en rango = 1 - 4
- <=> tiene 2 dígitos: <=> en rango = 3 - 10
- <=> tiene 3 dígitos: <=> en rango = 10 - 40
- <=> tiene 4 dígitos: <=> en rango = 30 - 100
- <=> tiene 5 dígitos: <=> en rango = 100 - 400
¿Nota la repetición?
Puede usar este rango en un enfoque de búsqueda binaria para ver si hay un <=> para el cual:
number == solution * solution
Aquí está el código
Aquí está mi clase SquareRootChecker
public class SquareRootChecker {
private long number;
private long initialLow;
private long initialHigh;
public SquareRootChecker(long number) {
this.number = number;
initialLow = 1;
initialHigh = 4;
if (Long.toString(number).length() % 2 == 0) {
initialLow = 3;
initialHigh = 10;
}
for (long i = 0; i < Long.toString(number).length() / 2; i++) {
initialLow *= 10;
initialHigh *= 10;
}
if (Long.toString(number).length() % 2 == 0) {
initialLow /= 10;
initialHigh /=10;
}
}
public boolean checkSquareRoot() {
return findSquareRoot(initialLow, initialHigh, number);
}
private boolean findSquareRoot(long low, long high, long number) {
long check = low + (high - low) / 2;
if (high >= low) {
if (number == check * check) {
return true;
}
else if (number < check * check) {
high = check - 1;
return findSquareRoot(low, high, number);
}
else {
low = check + 1;
return findSquareRoot(low, high, number);
}
}
return false;
}
}
Y aquí hay un ejemplo sobre cómo usarlo.
long number = 1234567;
long square = number * number;
SquareRootChecker squareRootChecker = new SquareRootChecker(square);
System.out.println(square + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677489: true"
long notSquare = square + 1;
squareRootChecker = new SquareRootChecker(notSquare);
System.out.println(notSquare + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677490: false"
Si desea velocidad, dado que sus enteros son de tamaño finito, sospecho que la forma más rápida implicaría (a) dividir los parámetros por tamaño (por ejemplo, en categorías por conjunto de bits más grande), y luego verificar el valor contra una matriz de cuadrados perfectos dentro de ese rango.
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. Después de todo, es un método iterativo extremadamente truncado: el de Newton, con una muy buena primera suposición.
Con respecto a su mejor desempeño actual, veo dos micro optimizaciones:
- mover el cheque vs. 0 después del cheque usando mod255
- reorganiza los poderes de división de cuatro para omitir todos los controles para el 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;
}
Incluso 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; dudo mucho que los controles sean verdaderamente independientes, lo que hace que las cosas sean complicadas.
" 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 número entero). "
Las respuestas son impresionantes, pero no pude ver una verificación simple:
compruebe si el primer número a la derecha del largo es miembro del conjunto (0,1,4,5,6,9). Si no lo es, entonces no puede ser un "cuadrado perfecto".
ej.
4567 - no puede ser un cuadrado perfecto.
