java - que - raiz cuadrada ejemplos




La forma más rápida de determinar si la raíz cuadrada de un entero es un entero (20)

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.


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.


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

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 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).


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.


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.


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

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.


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.







perfect-square