java - metodo - raiz quadrada recursiva c




Maneira mais rápida de determinar se a raiz quadrada de um inteiro é um inteiro (20)

Eu estou procurando o caminho mais rápido para determinar se um valor long é um quadrado perfeito (ou seja, sua raiz quadrada é outro inteiro):

  1. Eu fiz isso da maneira mais fácil, usando a função Math.sqrt () interna, mas eu estou querendo saber se existe uma maneira de fazer isso mais rápido, restringindo-se ao domínio somente inteiro.
  2. Manter uma tabela de consulta é impraticável (uma vez que existem cerca de 2 31,5 inteiros cujo quadrado é menor que 2 63 ).

Aqui está a maneira muito simples e direta que estou fazendo agora:

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: Estou usando essa função em muitos problemas do Project Euler . Então, ninguém mais terá que manter esse código. E esse tipo de micro-otimização pode realmente fazer a diferença, já que parte do desafio é fazer todo algoritmo em menos de um minuto, e essa função precisará ser chamada milhões de vezes em alguns problemas.

Uma nova solução publicada pela A. Rex provou ser ainda mais rápida. Em uma corrida sobre os primeiros 1 bilhão de inteiros, a solução exigiu apenas 34% do tempo que a solução original usou. Enquanto o hack John Carmack é um pouco melhor para valores pequenos de n , o benefício comparado a essa solução é bem pequeno.

Aqui está a solução A. Rex, convertida para 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
};

Eu tentei as diferentes soluções apresentadas abaixo.

  • Depois de testes exaustivos, descobri que adicionar 0.5 ao resultado de Math.sqrt () não é necessário, pelo menos não na minha máquina.
  • O hack John Carmack foi mais rápido, mas deu resultados incorretos a partir de n = 410881. No entanto, como sugerido por BobbyShaftoe , podemos usar o hack Carmack para n <410881.
  • O método de Newton foi um pouco mais lento que o Math.sqrt() . Isto é provavelmente porque Math.sqrt() usa algo similar ao método de Newton, mas implementado no hardware, então é muito mais rápido do que em Java. Além disso, o método de Newton ainda exigia o uso de duplas.
  • Um método de Newton modificado, que usava alguns truques para envolver apenas matemática inteira, exigia alguns truques para evitar estouro (quero que essa função trabalhe com todos os inteiros positivos de 64 bits) e ainda era mais lenta que Math.sqrt()
  • O golpe binário foi ainda mais lento. Isso faz sentido porque o chop binário em média exigirá 16 passes para encontrar a raiz quadrada de um número de 64 bits.

A sugestão que mostrou melhorias foi feita por John D. Cook . Você pode observar que o último dígito hexadecimal (ou seja, os últimos 4 bits) de um quadrado perfeito deve ser 0, 1, 4 ou 9. Isso significa que 75% dos números podem ser imediatamente eliminados como possíveis quadrados. A implementação dessa solução resultou em uma redução de aproximadamente 50% no tempo de execução.

Trabalhando com a sugestão de John, investiguei propriedades dos últimos n bits de um quadrado perfeito. Analisando os últimos 6 bits, descobri que apenas 12 dos 64 valores são possíveis para os últimos 6 bits. Isso significa que 81% dos valores podem ser eliminados sem o uso de qualquer matemática. A implementação dessa solução gerou uma redução adicional de 8% no tempo de execução (comparado ao meu algoritmo original). A análise de mais de 6 bits resulta em uma lista de possíveis bits finais que é muito grande para ser prática.

Aqui está o código que eu usei, que é executado em 42% do tempo exigido pelo algoritmo original (baseado em uma corrida nos primeiros 100 milhões de inteiros). Para valores de n menores que 410881, ele é executado em apenas 29% do tempo exigido pelo 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 acordo com os testes de John, usar or instruções é mais rápido em C ++ do que usar um switch , mas em Java e C # parece não haver diferença entre or e switch .
  • Eu também tentei fazer uma tabela de pesquisa (como uma matriz estática privada de 64 valores booleanos). Então, ao invés de switch ou or statement, eu diria if(lookup[(int)(n&0x3F)]) { test } else return false; . Para minha surpresa, isso foi (apenas um pouco) mais lento. Não sei porquê. Isso ocorre porque os limites da matriz são verificados em Java .

Eu quero essa função para trabalhar com todos os inteiros positivos assinados de 64 bits

Math.sqrt()funciona com duplas como parâmetros de entrada, para que você não obtenha resultados precisos para números inteiros maiores que 2 ^ 53 .


Método de Newton com aritmética inteira

Se você deseja evitar operações não inteiras, você pode usar o método abaixo. Basicamente, ele usa o método de Newton modificado para aritmética inteira.

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

Essa implementação não pode competir com soluções que usam Math.sqrt. No entanto, seu desempenho pode ser melhorado usando os mecanismos de filtragem descritos em alguns dos outros posts.


Você terá que fazer alguns benchmarking. O melhor algoritmo dependerá da distribuição de suas entradas.

Seu algoritmo pode ser quase ideal, mas você pode querer fazer uma verificação rápida para descartar algumas possibilidades antes de chamar sua rotina de raiz quadrada. Por exemplo, olhe o último dígito do seu número em hexadecimal, fazendo um pouco "e". Quadrados perfeitos só podem terminar em 0, 1, 4 ou 9 na base 16, portanto, para 75% de suas entradas (supondo que sejam distribuídas uniformemente), você pode evitar uma chamada à raiz quadrada em troca de um pouco de movimento rápido.

Kip comparou o seguinte código ao implementar o truque hexadecimal. Ao testar números de 1 a 100.000.000, esse código foi executado duas vezes mais rápido que o 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;
    }
}

Quando eu testei o código análogo em C ++, ele realmente correu mais lento que o original. No entanto, quando eliminei a instrução switch, o truque hexadecimal novamente tornou o código duas vezes mais 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;
}

Eliminar a instrução switch teve pouco efeito no código C #.


"Estou procurando a maneira mais rápida de determinar se um valor longo é um quadrado perfeito (ou seja, sua raiz quadrada é outro inteiro)."

As respostas são impressionantes, mas não consegui ver uma simples verificação:

verifique se o primeiro número à direita do longo é um membro do conjunto (0,1,4,5,6,9). Se não for, então não pode ser um "quadrado perfeito".

por exemplo.

4567 - não pode ser um quadrado perfeito.


Esta é a implementação Java mais rápida que eu poderia criar, usando uma combinação de técnicas sugeridas por outras pessoas neste segmento.

  • Teste Mod-256
  • Teste mod-3465 inexata (evita a divisão inteira ao custo de alguns falsos positivos)
  • Raiz quadrada de ponto flutuante, arredonda e compara com o valor de entrada

Eu também experimentei essas modificações, mas elas não ajudaram no desempenho:

  • Teste adicional de mod-255
  • Dividindo o valor de entrada por potências de 4
  • Raiz Quadrada Inversa Rápida (para trabalhar com valores altos de N, precisa de 3 iterações, o suficiente para torná-la mais lenta que a função raiz quadrada do 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;
        }
    }

}

Eu estava pensando sobre os tempos horríveis que passei no curso de Análise Numérica.

E então eu lembro, havia essa função circulando em torno da 'net do código fonte do 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 basicamente calcula uma raiz quadrada, usando a função de aproximação de Newton (não consigo lembrar o nome exato).

Deve ser utilizável e pode até ser mais rápido, é de um dos jogos fenomenais de software de id!

Está escrito em C ++, mas não deve ser muito difícil reutilizar a mesma técnica em Java quando você tiver a idéia:

Eu encontrei originalmente em: http://www.codemaestro.com/reviews/9

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

Você pode seguir o link para mais explicações de como funciona, mas se você não se importa muito, então é mais ou menos o que eu lembro de ler o blog e de fazer o curso de Análise Numérica:

  • a * (long*) &yé basicamente uma função de conversão-para-longa rápido as operações de modo inteiro pode ser aplicado sobre os bytes brutos.
  • a 0x5f3759df - (i >> 1);linha é um valor de semente pré-calculado para a função de aproximação.
  • o * (float*) &iconverte o valor de volta para o ponto flutuante.
  • a y = y * ( threehalfs - ( x2 * y * y ) )linha basicamente repete o valor sobre a função novamente.

A função de aproximação fornece valores mais precisos quanto mais você iterar a função sobre o resultado. No caso de Quake, uma iteração é "boa o suficiente", mas se não fosse por você ... então você poderia adicionar tanta iteração quanto fosse necessário.

Isso deve ser mais rápido porque reduz o número de operações de divisão feitas em enraizamento quadrado ingênuo para uma divisão simples por 2 (na verdade, uma * 0.5Foperação de multiplicação) e substitui-o por um número fixo de operações de multiplicação.


Se a velocidade é uma preocupação, por que não dividir o conjunto de entradas mais comumente usado e seus valores em uma tabela de consulta e, em seguida, fazer o algoritmo de otimização mágica que você criou para os casos excepcionais?


Se você fizer um binário para tentar encontrar a raiz quadrada "direita", você pode facilmente detectar se o valor que você tem é próximo o suficiente para dizer:

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

Então, tendo calculado n^2, as opções são:

  • n^2 = target : feito, retorno verdadeiro
  • n^2 + 2n + 1 > target > n^2 : você está perto, mas não é perfeito: retorne falso
  • n^2 - 2n + 1 < target < n^2 : idem
  • target < n^2 - 2n + 1 : chop binário em um menor n
  • target > n^2 + 2n + 1 : chop binário em um maior n

(Desculpe, isso usa ncomo seu palpite atual, e targetpara o parâmetro. Peça desculpas pela confusão!)

Eu não sei se isso será mais rápido ou não, mas vale a pena tentar.

EDIT: O binário binário não tem que ter em toda a gama de números inteiros, (2^x)^2 = 2^(2x)então, uma vez que você encontrou o bit top set em seu alvo (o que pode ser feito com um truque de bit-twiddling; eu esqueço exatamente como) você pode obter rapidamente uma série de possíveis respostas. Lembre-se, um bife binário ingênuo ainda vai levar até 31 ou 32 iterações.


Você deve se livrar da parte de 2 potências de N desde o começo.

2nd Edit A expressão mágica para m abaixo deve ser

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

e não como está escrito

Fim da 2ª edição

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

1ª edição:

Melhoria Menor:

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

Fim da 1ª edição

Agora continue como de costume. Desta forma, quando você chegar à parte de ponto flutuante, você já se livrou de todos os números cuja parte de 2-power é ímpar (cerca de metade), e então você considera apenas 1/8 do que sobrou. Ou seja, você executa a parte de ponto flutuante em 6% dos números.


Estou muito atrasado para a festa, mas espero fornecer uma resposta melhor; mais curto e (supondo que meu benchmark esteja correto) também muito faster .

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

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

O primeiro teste detecta a maioria dos não quadrados rapidamente. Ele usa uma tabela de 64 itens empacotada em um longo período, portanto não há custo de acesso à matriz (verificação indireta e de limites). Por um tempo uniformemente aleatório, há uma probabilidade de 81,25% de terminar aqui.

O segundo teste pega todos os números com um número ímpar de dois em sua fatoração. O método Long.numberOfTrailingZeros é muito rápido, pois torna o JIT-ed em uma única instrução i86.

Depois de eliminar os zeros à direita, o terceiro teste manipula números que terminam com 011, 101 ou 111 em binário, que não são quadrados perfeitos. Ele também se preocupa com números negativos e também lida com 0.

O teste final recai na double aritmética. Como o double tem apenas 53 bits de mantissa, a conversão de long para double inclui arredondamentos para valores grandes. No entanto, o teste está correto (a menos que a proof esteja errada).

Tentar incorporar a ideia do mod255 não foi bem sucedido.


Apenas para registro, outra abordagem é usar a decomposição principal. Se cada fator da decomposição for par, então o número é um quadrado perfeito. Então, o que você quer é ver se um número pode ser decomposto como um produto de quadrados de números primos. Claro, você não precisa obter tal decomposição, apenas para ver se existe.

Primeiro construa uma tabela de quadrados de números primos que sejam menores que 2 ^ 32. Isso é muito menor que uma tabela de todos os inteiros até esse limite.

Uma solução seria então assim:

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

Eu acho que é um pouco enigmático. O que ele faz é verificar em cada etapa que o quadrado de um número primo divide o número de entrada. Se isso acontecer, ele divide o número pelo quadrado, desde que seja possível, para remover esse quadrado da decomposição principal. Se por este processo chegamos a 1, então o número de entrada era uma decomposição do quadrado dos números primos. Se o quadrado se torna maior do que o próprio número, então não há como este quadrado, ou qualquer quadrado maior, poder dividi-lo, de modo que o número não pode ser uma decomposição de quadrados de números primos.

Dado hoje em dia 'sqrt feito em hardware e a necessidade de calcular números primos aqui, eu acho que esta solução é muito mais lenta. Mas deve dar melhores resultados do que a solução com o sqrt, que não funcionará em 2 ^ 54, como diz mrzl em sua resposta.


Aqui está a maneira mais simples e concisa, embora eu não saiba como ela se compara em termos de ciclos de CPU. Isso funciona muito bem se você deseja apenas saber se a raiz é um número inteiro. Se você realmente se importa se é um inteiro, você também pode descobrir isso. Aqui está uma função simples (e pura):

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

Se você não precisa de micro-otimização, esta resposta é melhor em termos de simplicidade e facilidade de manutenção. Se você estiver obtendo números negativos, talvez queira usar Math.abs () no argumento numérico como o argumento Math.sqrt ().

No meu CPU Intel i7-4790 de 3.6Ghz, uma execução deste algoritmo em 0 - 10.000.000 levou uma média de 35 - 37 nanossegundos por cálculo. Fiz 10 execuções sequenciais, imprimindo o tempo médio gasto em cada um dos dez milhões de cálculos sqrt. Cada corrida total levou um pouco mais de 600 ms para ser concluída.

Se você estiver executando um número menor de cálculos, os cálculos anteriores demorarão um pouco mais.


Deve ser muito mais rápido usar http://en.wikipedia.org/wiki/Newton%27s_method para calcular a raiz quadrada inteira , em seguida, esquadrar esse número e verificar, como você faz na sua solução atual. O método de Newton é a base para a solução Carmack mencionada em algumas outras respostas. Você deve ser capaz de obter uma resposta mais rápida, já que você está interessado apenas na parte inteira da raiz, permitindo que você pare o algoritmo de aproximação mais cedo.

Outra otimização que você pode tentar: Se a Raiz Digital de um número não terminar em 1, 4, 7 ou 9, o número não é um quadrado perfeito. Isso pode ser usado como uma maneira rápida de eliminar 60% de suas entradas antes de aplicar o algoritmo de raiz quadrada mais lenta.


Deveria ser possível empacotar o 'não pode ser um quadrado perfeito se os últimos X dígitos forem N' muito mais eficientemente que isto! Vou usar o java 32 bit ints e produzir dados suficientes para verificar os últimos 16 bits do número - são 2048 valores int hexadecimais.

...

Está bem. Ou eu encontrei uma teoria dos números que está um pouco além de mim, ou há um bug no meu código. Em todo caso, aqui está o 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("};");
}

e aqui estão os resultados:

(ed: elidiu por desempenho ruim em prettify.js; veja o histórico de revisões para ver.)


Eu não sei se isso foi mencionado antes. Mas eu encontrei uma solução here :

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

Eu verifiquei todos os resultados possíveis quando os últimos n bits de um quadrado são observados. Examinando sucessivamente mais bits, até 5/6 de entradas podem ser eliminadas. Na verdade, eu projetei isso para implementar o algoritmo de Fatoração de Fermat, e é muito rápido lá.

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

O último bit do pseudocódigo pode ser usado para estender os testes para eliminar mais valores. Os testes acima são para k = 0, 1, 2, 3

  • a é da forma (3 << 2k) - 1
  • b é da forma (2 << 2k)
  • c é da forma (2 << 2k + 2) - 1
  • d é da forma (2 << 2k - 1) * 10

    Primeiro testa se tem um residual quadrado com módulos de potência de dois, então testa baseado em um módulo final, então usa o Math.sqrt para fazer um teste final. Eu tive a ideia do primeiro lugar e tentei estender isso. Eu aprecio quaisquer comentários ou sugestões.

    Atualização: Usando o teste por um módulo, (modSq) e uma base de módulo de 44352, meu teste é executado em 96% do tempo do primeiro na atualização do OP para números de até 1.000.000.000.


  • Não tenho certeza se seria mais rápido, ou mesmo preciso, mas você poderia usar http://www.codemaestro.com/reviews/9 algoritmo http://www.codemaestro.com/reviews/9 , de http://www.codemaestro.com/reviews/9 , para resolver a raiz quadrada mais rapidamente. Você provavelmente poderia facilmente testar isso para todos os inteiros possíveis de 32 bits, e validar que você realmente obteve resultados corretos, já que é apenas uma aproximação. No entanto, agora que penso nisso, o uso de duplas também está se aproximando, então não tenho certeza de como isso entraria em cena.


    No que diz respeito ao método Carmac, parece que seria muito fácil apenas repetir uma vez mais, o que deveria duplicar o número de dígitos de precisão. É, afinal de contas, um método iterativo extremamente truncado - o de Newton, com um bom primeiro palpite.

    Em relação ao seu melhor atual, vejo duas micro-otimizações:

    • mova o cheque contra 0 após o cheque usando mod255
    • reorganize os poderes de divisão de quatro para pular todas as verificações para o caso normal (75%).

    Ou seja:

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

    Ainda melhor pode ser um simples

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

    Obviamente, seria interessante saber quantos números são descartados em cada checkpoint - eu duvido que as verificações sejam verdadeiramente independentes, o que torna as coisas difíceis.


    Para o desempenho, muitas vezes você tem que fazer algumas compromissos. Outros expressaram vários métodos, no entanto, você notou que o hack de Carmack era mais rápido até certos valores de N. Então, você deveria verificar o "n" e se for menor que esse número N, use o hack de Carmack, use outro método descrito nas respostas aqui.


    Tem sido apontado que os últimos ddígitos de um quadrado perfeito só podem assumir certos valores. Os últimos ddígitos (na base b) de um número né o mesmo que o restante quando né dividido por b d, ou seja. em notação C n % pow(b, d).

    Isto pode ser generalizado para qualquer módulo m, ie. n % mpode ser usado para descartar uma porcentagem de números de quadrados perfeitos. O módulo que você está usando atualmente é 64, o que permite 12, ou seja. 19% de restos, como possíveis praças. Com um pouco de codificação achei o módulo 110880, que permite apenas 2016, ou seja. 1,8% dos restos como possíveis praças. Portanto, dependendo do custo de uma operação de módulo (ou seja, divisão) e de uma pesquisa de tabela em relação a uma raiz quadrada em sua máquina, usar esse módulo pode ser mais rápido.

    Aliás, se o Java tiver uma maneira de armazenar uma matriz compactada de bits para a tabela de consulta, não a use. 110880 palavras de 32 bits não são muito RAM atualmente e buscar uma palavra de máquina será mais rápido do que buscar um único bit.







    perfect-square