maneira mais rápida para determinar se a raiz quadrada de um inteiro é um inteiro
https://stackoverflow.com/questions/295579
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu estou procurando a maneira mais rápida para determinar se um valor long é um quadrado perfeito (ou seja, sua raiz quadrada é outro inteiro):
- Eu fiz o caminho mais fácil, usando o built-in
Math.sqrt()função, mas eu estou querendo saber se existe uma maneira de fazê-lo mais rápido, restringindo-se ao domínio somente inteiro. - A manutenção de uma tabela de pesquisa é impraticável (desde há cerca de 2 31,5 inteiros cujo quadrado é inferior a 2 63 ).
Aqui é a maneira muito simples e direta que eu 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;
}
Nota: eu estou usando esta função em problemas muitas Projeto Euler . Então, ninguém mais terá que manter este código. E este tipo de micro-otimização poderia realmente fazer a diferença, uma vez que parte do desafio é fazer cada algoritmo em menos de um minuto, e esta função terá de ser chamado de milhões de vezes em alguns problemas.
Eu tentei diferentes soluções para o problema:
- Após o teste exaustivo, verificou que adicionando
0.5para o resultado de Math.sqrt () não é necessário, pelo menos, não na minha máquina. - raiz rápido inverso do quadrado foi mais rápido, mas deu resultados incorretos para n> = 410881 . no entanto, como sugerido por BobbyShaftoe , podemos usar o hack FISR para n <410.881.
- O método de Newton era um bom bocado mais lento do que
Math.sqrt(). Isto é provavelmente porqueMath.sqrt()usa algo semelhante ao método de Newton, mas implementado no hardware por isso é muito mais rápido do que em Java. Além disso, o método de Newton ainda necessário o uso de duplas. - A modificado o método de Newton, que usou alguns truques para que apenas inteiro matemática estava envolvido, necessário alguns hacks para estouro evitar (Eu quero essa função para trabalhar com todos os inteiros positivos de 64 bits assinados), e ainda mais lento do que era
Math.sqrt(). - Binary chop foi ainda mais lento. Isso faz sentido porque o chop binário será, em média, exigem 16 passes para encontrar a raiz quadrada de um número de 64 bits.
- De acordo com testes de John, usando declarações
oré mais rápido em C ++ do que usar umswitch, mas em Java e C # parece haver nenhuma diferença entreoreswitch. - Eu também tentei fazer uma tabela de pesquisa (como uma matriz estática privada de 64 valores booleanos). Então, em vez de qualquer switch ou
ordeclaração, gostaria apenas de dizerif(lookup[(int)(n&0x3F)]) { test } else return false;. Para minha surpresa, este foi (ligeiramente) mais lento. Isso ocorre porque limites de matriz são verificados em Java .
Solução
Eu descobri um método que funciona ~ 35% mais rápido que seu 6bits + Carmack + código sqrt, pelo menos com o meu CPU (x86) e linguagem de programação (C / C ++). Os resultados podem variar, especialmente porque eu não sei como o fator de Java vai jogar fora.
A minha abordagem é triplo:
- Em primeiro lugar, filtrar respostas óbvias. Isso inclui os números negativos e olhando para os últimos 4 bits. (Eu encontrei olhando para os últimos seis não ajuda.) Eu também responder sim para 0. (Ao ler o código abaixo, nota que a minha entrada é
int64 x.)if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) ) return false; if( x == 0 ) return true; - Em seguida, verificar se é um módulo quadrado 255 = 3 * 5 * 17. Porque que é um produto de três números primos distintos, apenas cerca de 1/8 dos resíduos mod 255 são quadrados. No entanto, na minha experiência, chamando o operador módulo (%) custa mais do que o benefício fica, então eu usar truques bit envolvendo 255 = 2 ^ 8-1 para calcular o resíduo. (Para melhor ou pior, eu não estou usando o truque de ler bytes individuais fora de uma palavra, apenas bit a bit-e e turnos.)
Para verificar realmente se o resíduo é um quadrado, eu olho para a resposta em uma tabela pré-computadas.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, tente calcular a raiz quadrada usando um método semelhante ao de Hensel lema . (Eu não acho que é aplicável directamente, mas funciona com algumas modificações.) Antes de fazer isso, divido todas potências de 2 com uma pesquisa binária:
Neste ponto, para o nosso número para ser um quadrado, ele deve ser um 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;
A estrutura básica do lema de Hensel é o seguinte. (Nota: código não testado e, se ele não funcionar, tente t = 2 ou 8.)if((x & 7) != 1) return false;
A ideia é que a cada iteração, você adicionar um pouco para r, o "atual" raiz quadrada de x; cada raiz quadrada é preciso um módulo de energia cada vez maior de 2, ou seja, t / 2. No final, r e t / 2-r será raízes quadradas de x modulo t / 2. (Note que se r é uma raiz quadrada de x, então é assim -r Isto é verdade mesmo números modulo, mas cuidado, modulo alguns números, as coisas podem ter ainda mais de 2 raízes quadradas;. Notavelmente, isso inclui potências de 2. ) Porque a nossa raiz quadrada real é inferior a 2 ^ 32, em que ponto nós podemos realmente apenas verificar se r ou t / 2-r são raízes quadradas reais. No meu código real, eu uso o seguinte circuito 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.
O aumento de velocidade aqui é obtido de três formas: valor inicial precomputed (equivalente a ~ 10 iterações do ciclo), sair mais cedo do loop, e pular alguns valores t. Para a última parte, eu olho paraint64 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 * xe conjunto de t para ser a maior potência de 2 divisória z com um truque pouco. Isso me permite ignorar valores de t que não teria afetado o valor de r de qualquer maneira. O valor inicial pré-computadas no meu caso escolhe o "menor positivo" raiz quadrada módulo 8192.
Mesmo se este código não funciona mais rápido para você, espero que você aproveite algumas das idéias que ele contém. código completo, testado segue, incluindo as tabelas pré-computadas.
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;
}Outras dicas
Eu sou muito atrasado para a festa, mas eu espero dar uma resposta melhor; mais curta e (assumindo que o meu referência é correto), também muito mais 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;
}
O primeiro teste pega a maioria dos não-quadrados rapidamente. Ele usa uma tabela de 64 itens, embalado em um longo, por isso não há custo de acesso de matriz (indirecta e barrancos cheques). Para uma long uniformemente aleatório, há uma probabilidade de 81,25% de acabar aqui.
O segundo teste de captura todos os números tendo um número ímpar de pares na sua fatoração. O método Long.numberOfTrailingZeros é muito rápido quanto ele ganha JIT-ed em uma única instrução i86.
Depois de largar os zeros finais, os números alças terceiro teste terminando com 011, 101, ou 111 em binário, que há quadrados perfeitos. Ele também se preocupa com números negativos e também lida com 0.
O teste final cai de volta à aritmética double. Como double tem apenas 53 bits de mantissa,
a conversão de long para double inclui arredondamento para valores grandes. No entanto, o teste está correto (a menos que o prova é errado).
Tentando incorporar a idéia mod255 não foi bem sucedido.
Você vai ter que fazer alguma benchmarking. O melhor algoritmo vai 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 para o último dígito do seu número em hexadecimal, fazendo um pouco sábio "e". quadrados perfeitos só pode terminar em 0, 1, 4 ou 9 em base 16, Portanto, para 75% de suas entradas (assumindo que eles estão uniformemente distribuídos) você pode evitar uma chamada para a raiz quadrada em troca de algum twiddling pouco muito rápido.
Kip aferido o seguinte código implementando o truque hex. Ao testar números de 1 a 100.000.000, este código correu 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áloga em C ++, ele realmente correu mais lento do que o original. No entanto, quando eliminou a instrução switch, o truque hex, mais uma vez tornar 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;
}
A eliminação da instrução switch teve pouco efeito sobre o código C #.
Eu estava pensando sobre os momentos horríveis que passei em Análise Numérica curso.
E então eu me lembro, houve esta função circulando em torno da 'net a partir do código fonte 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;
}
O 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 de jogo da id Software fenomenal!
Ele é escrito em C ++, mas não deve ser muito difícil de reutilizar a mesma técnica em Java uma vez que você começa a idéia:
Eu originalmente encontrado em: http://www.codemaestro.com/reviews/9
O método de Newton explicou na wikipedia: http://en.wikipedia.org/wiki/Newton% 27s_method
Você pode seguir o link para obter mais explicação de como ele funciona, mas se você não se importam muito, então este é aproximadamente o que eu me lembro de ler o blog e de tomar a Análise Numérica curso:
- o
* (long*) &yé basicamente um rápido converter-se longa função para operações com números inteiros podem ser aplicados sobre os bytes crus. - a linha
0x5f3759df - (i >> 1);é um valor de semente pré-calculado para a função de aproximação. - o
* (float*) &iconverte o valor de volta para ponto flutuante. - a linha
y = y * ( threehalfs - ( x2 * y * y ) )bascially repete o valor sobre a função novamente.
A função de aproximação dá valores mais precisos quanto mais você iterar a função sobre o resultado. No caso de Quake, uma iteração é "suficientemente bom", mas se não fosse por você ... então você pode adicionar tanto iteração como você precisa.
Esta deve ser mais rápido porque ele reduz o número de operações de divisão feitos no enraizamento quadrado ingênuo para baixo para uma divisão simples por 2 (na verdade uma operação de multiplicação * 0.5F) e substituí-lo com um número fixo alguns de multiplicação operações em seu lugar.
Eu não tenho certeza se seria mais rápido, ou mesmo precisa, mas você poderia usar mágica raiz quadrada de John Carmack , algoritmo para resolver a raiz quadrada mais rápido. Você provavelmente poderia facilmente testar isso para todos os possíveis números inteiros de 32 bits e validar que você realmente tem resultados corretos, como é apenas um appoximation. No entanto, agora que penso nisso, utilizando duplos está aproximando também, então eu não sei como isso iria entrar em jogo.
Se você fizer uma costeleta de binário para tentar encontrar a raiz quadrada "certo", você pode facilmente detectar se o valor que você tem é perto o suficiente para dizer a:
(n+1)^2 = n^2 + 2n + 1
(n-1)^2 = n^2 - 2n + 1
n^2 Assim, tendo calculado, as opções são:
-
n^2 = target: feito, retornar true -
n^2 + 2n + 1 > target > n^2: você está perto, mas não é perfeito: return false -
n^2 - 2n + 1 < target < n^2: ditto -
target < n^2 - 2n + 1: Costeleta de binário em umnmenor -
target > n^2 + 2n + 1: Costeleta de binário em umnsuperior
(Desculpe, isso usa n como seu palpite atual, e target para o parâmetro. Peço desculpas pela confusão!)
Eu não sei se isso vai ser mais rápido ou não, mas vale a pena uma tentativa.
EDIT: A costeleta binária não tem que tomar em toda a gama de números inteiros, ou (2^x)^2 = 2^(2x), portanto, uma vez que você encontrou o bit set top em seu alvo (o que pode ser feito com um truque-girando bit; I esquecer exatamente como) você pode rapidamente obter uma gama de respostas possíveis. Lembre-se, uma costeleta binária ingênuo é ainda só vai levar até 31 ou 32 iterações.
Eu corri minha própria análise de vários dos algoritmos neste segmento e veio com alguns novos resultados. Você pode ver aquelas velhas resultados no histórico de edições desta resposta, mas eles não são precisos, como eu cometi um erro, e desperdício de tempo analisando vários algoritmos que não são próximos. No entanto, tirando lições de várias respostas diferentes, agora tenho dois algoritmos que esmagam o "vencedor" deste segmento. Aqui é a coisa principal que eu faria diferente do que todos os outros:
// 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;
No entanto, esta linha simples, que na maioria das vezes acrescenta uma ou duas instruções muito rápido, simplifica bastante a declaração switch-case em uma instrução if. No entanto, ele pode adicionar ao tempo de execução se muitos dos números testados têm significativos fatores potência de dois.
Os algoritmos abaixo são as seguintes:
- Internet - resposta postada de Kip
- Durron - A minha resposta modificada usando a resposta de uma passagem como base
- DurronTwo -. Minha resposta modificada usando a resposta de duas passagens (por @JohnnyHeggheim), com algumas outras pequenas modificações
Aqui é um tempo de execução de exemplo, se os números são gerados 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
E aqui é um tempo de execução de amostra se for executado no primeiro milhão anseia apenas:
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 você pode ver, DurronTwo faz melhor para grandes entradas, porque ele começa a usar o truque de mágica muito, muito frequentemente, mas fica derrotado em comparação com o primeiro algoritmo e Math.sqrt porque os números são muito menores. Enquanto isso, o Durron mais simples é um grande vencedor porque nunca tem que dividir por 4 muitas e muitas vezes nos primeiros milhões de números.
Aqui 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;
}
E 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;
}
E a minha referência arnês: (Requer Google pinça 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);
}
}
UPDATE: Eu fiz um novo algoritmo que é mais rápido em alguns cenários, mais lento em outros, eu comecei diferentes benchmarks baseados em diferentes entradas. Se calcularmos módulo 0xFFFFFF = 3 x 3 x 5 x 7 x 13 x 17 x 241, podemos eliminar 97,82% de números que não podem ser quadrados. Isso pode ser (tipo de) feito em uma linha, com operações bit a bit 5:
if (!goodLookupSquares[(int) ((n & 0xFFFFFFl) + ((n >> 24) & 0xFFFFFFl) + (n >> 48))]) return false;
O índice resultante é ou 1) do resíduo, 2) o resíduo + 0xFFFFFF, ou 3) o + 0x1FFFFFE resíduo. Claro, precisamos ter uma tabela de pesquisa de resíduos modulo 0xFFFFFF, que é sobre um arquivo de 3MB (neste caso armazenados como números de texto ASCII decimais, não ideal, mas claramente improvable com um ByteBuffer e assim por diante. Mas uma vez que é precalculation-lo não importa tanto. Você pode encontrar o arquivo aqui (ou gerar-lo sozinho ):
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;
}
eu carregá-lo em uma matriz boolean assim:
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();
}
Exemplo de execução. Bateu Durron (versão uma) em cada ran julgamento I.
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
Deve ser muito mais rápido de usar de Newton método para calcular o Integer Raiz quadrada , então quadrada este número e verificação, como você faz em sua solução atual. O método de Newton é a base para a solução Carmack mencionado em algumas outras respostas. Você deve ser capaz de obter uma resposta mais rápida desde que você está interessado apenas na parte inteira da raiz, o que lhe permite parar o algoritmo de aproximação mais cedo.
Outra otimização que você pode tentar: Se o Digital Root de um número não termina no 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 mais lento quadrado.
Eu quero essa função para trabalhar com todos inteiros de 64-bit assinados positivos
Math.sqrt() trabalha com duplas como parâmetros de entrada, para que você não vai obter resultados precisos para inteiros maiores do que 2 ^ 53 .
Apenas para o registro, outra abordagem é usar a decomposição prime. Se todos os fatores da decomposição é ainda, 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 dos quadrados dos números primos. Claro, você não precisa obter uma decomposição, só para ver se ele existir.
Primeiro construir uma tabela de quadrados de números primos que são mais baixos do que 2 ^ 32. Isto é muito menor do que uma tabela de todos os inteiros até este limite.
A solução, então, seria 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ática. O que ele faz é verificar em cada passo que o quadrado de um número primo dividir o número de entrada. Se isso acontecer, então ele divide o número pelo quadrado, enquanto é possível, para remover esta praça a partir da decomposição prime. Se por este processo, chegamos a 1, então o número de entrada era uma decomposição da praça de números primos. Se a praça torna-se maior do que o próprio número, então não há nenhuma maneira esta praça, ou quaisquer praças maiores, pode dividi-lo, de modo que o número não pode ser uma decomposição dos quadrados dos números primos.
Dada hoje em dia sqrt feito em hardware e a necessidade de calcular números primos aqui, eu acho que esta solução é muito mais lento. Mas deve dar melhores resultados do que solução com sqrt que não vai funcionar mais de 2 ^ 54, como diz mrzl em sua resposta.
Um problema inteiro merece uma solução inteiro. Assim
Do binário pesquisar sobre os inteiros (não-negativas) para encontrar o maior inteiro t tal que t**2 <= n. teste, em seguida, se r**2 = n exatamente. Isto leva tempo O (N log N).
Se você não sabe como binário procurar os inteiros positivos porque o conjunto é ilimitado, é fácil. Você começando pelo cálculo de sua função crescente f (acima f(t) = t**2 - n) em potências de dois. Quando você vê-lo tornar-se positivo, você encontrou um limite superior. Então você pode fazer busca binária padrão.
Tem sido salientado que os últimos dígitos d de um quadrado perfeito só pode assumir certos valores. Os últimos dígitos d (em b de base) de uma n número é o mesmo que o restante quando n é dividido por b d , isto é. em C n % pow(b, d) notação.
Isto pode ser generalizada para qualquer m módulo, ie. n % m pode ser usado para descartar alguma porcentagem de números de ser quadrados perfeitos. O módulo que você está usando é de 64, que permite que 12, ou seja. 19% de resíduos, como possíveis quadrados. Com um pouco de codificação I encontrado o módulo de 110.880, que permite que apenas 2,016, isto é. 1,8% de remanescentes como possíveis quadrados. Então, dependendo do custo de uma operação de módulo (ou seja. Divisão) e uma pesquisa de tabela versus uma raiz quadrada em sua máquina, usando este módulo pode ser mais rápido.
Pela maneira, se Java tem uma maneira de armazenar uma matriz embalado de bits para a tabela de referência, não usá-lo. 110880 palavras de 32 bits não é muito RAM estes dias e buscar uma palavra máquina vai ser mais rápido do que buscar um único bit.
Para obter o desempenho, você muitas vezes tem que fazer algumas compromsies. Outros expressaram vários métodos, no entanto, você anotou corte de Carmack foi mais rápido até determinados valores de N. Em seguida, você deve verificar o "n" e se é menor do que o número N, corte uso do Carmack, use então algum outro método descrito nas respostas aqui.
Esta é a implementação Java mais rápido que eu poderia vir acima com, usando uma combinação de técnicas sugeridas por outros nesta discussão.
- Mod-256 test
- Inexact MOD-3465 de teste (evita inteiros divisão ao custo de alguns falsos positivos)
- de ponto flutuante raiz quadrado, redondo e comparar com valor de entrada
Eu também experimentei com essas modificações, mas eles não o fizeram desempenho ajuda:
- adicionais mod-255 test
- Dividindo o valor de entrada por potências de 4
- rápido Inverse Raiz quadrada (de trabalho para altos valores de N que necessita 3 iterações, o suficiente para torná-lo mais lento do que a função raiz quadrada 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;
}
}
}
A seguir simplificação da solução das maaartinus parece barbear alguns pontos percentuais fora do tempo de execução, mas eu não sou bom o suficiente para o benchmarking para produzir um ponto de referência que posso confiar em:
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;
}
Seria vale a pena conferir como omitindo o primeiro teste,
if (goodMask << x >= 0) return false;
afetaria o desempenho.
Você deve se livrar da parte 2-poder da N desde o início.
2 Editar 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, pelo tempo que você chegar à parte de ponto flutuante, você já se livrou de todos os números cuja 2-parte potência é estranho (cerca de metade), e então você considerar apenas 1/8 do que está à esquerda. Ou seja, você executar a parte de ponto flutuante em 6% dos números.
Este é um retrabalho de decimal para binário do velho Marchant calculadora algoritmo (desculpe, eu não tenho uma referência), em Ruby, adaptado especificamente para esta pergunta:
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
Aqui está um exame de algo semelhante (por favor, não vote me para baixo para o estilo de codificação / cheiros ou desajeitado S / O - é o algoritmo que conta, e C ++ não é a minha língua materna). Neste caso, estamos procurando resíduo == 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;
};
A chamada sqrt não é perfeitamente precisa, como já foi mencionado, mas é interessante e instrutivo que não soprar as outras respostas em termos de velocidade. Afinal, a sequência de instruções em linguagem assembly para um sqrt é pequena. Intel tem uma instrução de hardware, o que não é usado por Java Eu acredito porque não se conforma com IEEE.
Então porque é lento? Como o Java é realmente chamar uma rotina C através de JNI, e é realmente mais lento para fazer isso do que chamar uma sub-rotina Java, que em si é mais lento do que fazê-lo em linha. Isso é muito irritante, e Java deve ter chegar a uma solução melhor, construção ou seja, chamadas de biblioteca ponto, se necessário flutuante. Oh bem.
Em C ++, eu suspeito que todas as alternativas complexas perderia em velocidade, mas eu não ter verificado todos eles. O que eu fiz, eo que as pessoas Java vai encontrar útil, é um hack simples, uma extensão do caso especial de testes sugerido por A. Rex. Use um único valor a longo como uma matriz de bits, que não é limites marcada. Dessa forma, você tem 64 bits de pesquisa booleana.
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;
}
O isPerfectSquare5 rotina é executado em cerca de 1/3 do tempo na minha máquina duo core2. Eu suspeito que alguns ajustes ao longo das mesmas linhas poderiam reduzir o tempo ainda mais, em média, mas cada vez que você verificar, você está negociando fora de mais testes para mais eliminando, assim você não pode ir muito mais longe nessa estrada.
Com certeza, ao invés de ter um teste separado para negativo, você pode verificar as altas 6 bits da mesma forma.
Note que tudo que eu estou fazendo é eliminar possíveis quadrados, mas quando eu tenho um caso potencial que eu tenho que chamar o original, inlined isPerfectSquare.
A rotina inic2 é chamado uma vez para inicializar os valores estáticos de PP1 e PP2. Note-se que na minha aplicação em C ++, eu estou usando unsigned long long, assim desde que você está conectado, você teria que usar o operador >>>.
Não há necessidade intrínseca de limites verificar a matriz, mas otimizador de Java tem que figurar para fora este material muito rapidamente, então eu não os culpo por isso.
Eu gosto da idéia de usar um método quase correta sobre alguma da entrada. Aqui está uma versão com uma maior "compensar". O código parece funcionar e passa o meu caso de teste simples.
Basta substituir o seu:
if(n < 410881L){...}
código com esta:
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);
}
Project Euler é mencionado nas tags e muitos dos problemas em que exigem a verificação números >> 2^64. A maioria das otimizações mencionados acima não funcionam facilmente quando você está trabalhando com um buffer de 80 bytes.
Eu costumava java BigInteger e uma versão ligeiramente modificada do método de Newton, que funciona melhor com números inteiros. O problema era que praças exatas n^2 convergiram para (n-1) vez de n porque n^2-1 = (n-1)(n+1) eo erro final foi apenas um passo abaixo do divisor final e o algoritmo terminada. Era fácil correção, adicionando um para o argumento original antes de calcular o erro. (Adicione dois para raízes cúbicas, etc.)
Um atributo agradável deste algoritmo é que você pode dizer imediatamente se o número é um quadrado perfeito - o erro final (não correção) no método de Newton será zero. Uma simples modificação também permite floor(sqrt(x)) calcular rapidamente, em vez do número inteiro mais próximo. Isso é útil com vários problemas de Euler.
Eu chequei todos os possíveis resultados quando os últimos n bits de um quadrado é observado. Por sucessivamente examinar mais bits, até 5/6 de entradas podem ser eliminados. Eu realmente projetou este 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;
}
A última pouco de pseudocódigo pode ser usado para estender os testes para eliminar mais valores. Os testes acima são para k = 0, 1, 2, 3
primeiros testes se tem um residual quadrado com módulos de potência de dois, então ele testa com base em um módulo final, em seguida, ele usa o Math.sqrt para fazer um teste final. Eu vim com a idéia do topo post, e tentou estender sobre ela. Eu aprecio quaisquer comentários ou sugestões.
Update: Usando o teste de um módulo, (modSq) e uma base módulo de 44352, minhas corridas de teste em 96% do tempo de um em atualização do OP para números até 1,000,000,000 .
Considerando por comprimento de bits geral (apesar de eu ter tipo específico usado aqui), eu tentei criar algo simplista como abaixo. verificação simples e óbvia para 0,1,2 ou <0 é necessária inicialmente. A seguir é simples no sentido de que ele não tenta usar quaisquer funções matemáticas existentes. A maior parte do operador pode ser substituído por operadores bit a bit. Eu não testei com qualquer dado ponto de referência embora. Não sou nem especialista em matemática ou projeto de algoritmos de computador em particular, eu gostaria de vê-lo apontando problema. Eu sei que há muitas chances de melhoria lá.
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;
}
Eu não sei se isso foi mencionado antes. Mas eu encontrei uma solução aqui :
int result = (int)(floor(sqrt(b)) - ceil(sqrt(a)) + 1);
Se a velocidade é uma preocupação, porque não partição fora do conjunto mais comumente usado de entradas e seus valores para uma tabela de pesquisa e, em seguida, fazer o que for otimizado algoritmo de mágica que você tem vir para cima com para os casos excepcionais?
Deve ser possível embalar o 'não pode ser um quadrado perfeito se os dígitos última X são N' muito mais eficientemente do que isso! Vou usar Java de 32 ints bit, e produzir dados suficientes para verificar os últimos 16 bits do número -. Que é 2048 valores hexadecimal int
...
Ok. Ou eu tenho que correr em alguma teoria número que é 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:. Elidida por mau desempenho em prettify.js; Ver histórico de revisão para ver)
Aqui é a maneira mais simples e concisa, embora eu não sei como ele se compara em termos de ciclos de CPU. Isso funciona muito bem se você só gostaria de saber se a raiz é um número inteiro. Se você realmente se importa se ele é um inteiro, você também pode descobrir isso. Aqui é uma simples (e puro) função:
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ê vai ter números negativos, talvez você vai querer usar Math.abs () sob o argumento de número como argumento Math.sqrt ().
No meu 3.6GHz Intel i7-4790 CPU, uma corrida deste algoritmo em 0 - 10.000.000 teve uma média de 35 - 37 nanossegundos por cálculo. Eu fiz 10 execuções sequenciais, imprimindo o tempo médio gasto em cada um dos dez milhões de cálculos sqrt. Cada total de funcionamento levou apenas um pouco mais de 600 ms para ser concluído.
Se você estiver executando um menor número de cálculos, os cálculos anteriores demorar um pouco mais.
Aqui é uma solução de dividir e conquistar.
Se a raiz quadrada de um número natural (number) é um número natural (solution), você pode facilmente determinar um intervalo para solution com base no número de dígitos de number:
-
numbertem 1 dígito:solutionna faixa = 1-4 -
numbertem 2 dígitos:solutionna faixa = 3 - 10 -
numbertem 3 dígitos:solutionna faixa = 10 - 40 -
numbertem 4 dígitos:solutionna faixa = 30 - 100 -
numbertem 5 dígitos:solutionna faixa = 100 - 400
Observe a repetição?
Você pode usar este intervalo em uma abordagem de busca binária para ver se há uma solution para as quais:
number == solution * solution
Aqui está o código
Aqui está o meu SquareRootChecker classe
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;
}
}
E aqui está um exemplo de como usá-lo.
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"
Se você quer velocidade, uma vez que seus números inteiros são de tamanho finito, eu suspeito que a maneira mais rápida envolveria (a) particionar os parâmetros de tamanho (por exemplo, em categorias de maior conjunto bit), em seguida, verificar o valor contra um array de quadrados perfeitos dentro desse intervalo.
Em relação ao método Carmac, parece que seria muito fácil apenas para iterate mais uma vez, que deve dobrar o número de dígitos de precisão. É, afinal, um método iterativo extremamente truncado -. Newton, com um muito bom primeiro palpite
Quanto à sua atual melhor, vejo dois micro-otimizações:
- mover o cheque vs. 0 após a verificação usando mod255
- reorganizar a divisão fora poderes de quatro para ignorar todas as verificações para o (75%) caso usual.
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;
}
Mesmo melhor pode ser um simples
while ((n & 0x03L) == 0) n >>= 2;
Obviamente, seria interessante saber quantos números se abatidos em cada ponto de verificação -. Eu duvido os cheques são verdadeiramente independente, o que torna as coisas complicadas
"Eu estou procurando a maneira mais rápida para determinar se um valor longo é um quadrado perfeito (ou seja, sua raiz quadrada é outro inteiro)."
As respostas são impressionantes, mas não conseguiu ver uma verificação simples:
Verifique se o primeiro número à direita do tempo que um membro do conjunto (0,1,4,5,6,9). Se não for, então não pode, eventualmente, ser um 'quadrado perfeito'.
por exemplo.
4567 -. Não pode ser um quadrado perfeito
