Il modo più veloce per determinare se la radice quadrata di un numero intero è un numero intero
https://stackoverflow.com/questions/295579
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Sto cercando il modo più veloce per determinare se un long valore è un quadrato perfetto (ovvero la sua radice quadrata è un altro numero intero):
- L'ho fatto in modo semplice, utilizzando il
Math.sqrt()integrato funzione, ma mi chiedo se c'è un modo per farlo più velocemente limitandoti al dominio solo intero. - Il mantenimento di una tabella di ricerca non è pratico (poiché ci sono circa 2 31.5 numeri interi il cui quadrato è inferiore a 2 63 ).
Ecco il modo molto semplice e diretto che sto facendo ora:
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: sto usando questa funzione in molti Project Euler . Quindi nessun altro dovrà mai mantenere questo codice. E questo tipo di micro-ottimizzazione potrebbe effettivamente fare la differenza, poiché parte della sfida è eseguire tutti gli algoritmi in meno di un minuto e questa funzione dovrà essere chiamata milioni di volte in alcuni problemi.
Ho provato le diverse soluzioni al problema:
- Dopo test approfonditi, ho scoperto che non è necessario aggiungere
0.5al risultato di Math.sqrt (), almeno non sulla mia macchina. - La radice quadrata inversa veloce era più veloce, ma ha dato risultati errati per n > = 410881. Tuttavia, come suggerito da BobbyShaftoe , possiamo usare l'hacker FISR per n < 410.881.
- Il metodo di Newton era un po 'più lento di
or. Ciò è probabilmente dovuto al fatto cheswitchutilizza qualcosa di simile al metodo di Newton, ma implementato nell'hardware, quindi è molto più veloce che in Java. Inoltre, il metodo di Newton richiedeva ancora l'uso del doppio. - Un metodo di Newton modificato, che utilizzava alcuni trucchi per coinvolgere solo la matematica dei numeri interi, richiedeva alcuni hack per evitare il trabocco (voglio che questa funzione funzioni con tutti i numeri interi con segno a 64 bit positivi), ed era ancora più lento
if(lookup[(int)(n&0x3F)]) { test } else return false;. - Il taglio binario era ancora più lento. Questo ha senso perché il taglio binario richiederà in media 16 passaggi per trovare la radice quadrata di un numero a 64 bit.
- Secondo i test di John, l'uso delle istruzioni <=> è più veloce in C ++ rispetto all'uso di <=>, ma in Java e C # non sembra esserci alcuna differenza tra <=> e <=>.
- Ho anche provato a creare una tabella di ricerca (come un array statico privato con 64 valori booleani). Quindi invece di switch o <=>, direi solo <=>. Con mia sorpresa, questo è stato (solo leggermente) più lento. Questo perché i limiti di array sono controllati in Java .
Soluzione
Ho scoperto un metodo che funziona ~ 35% più veloce del tuo codice 6bit + Carmack + sqrt, almeno con la mia CPU (x86) e il linguaggio di programmazione (C / C ++). I tuoi risultati possono variare, soprattutto perché non so come si svolgerà il fattore Java.
Il mio approccio è triplice:
- Innanzitutto, filtra le risposte ovvie. Questo include numeri negativi e guardando gli ultimi 4 bit. (Ho scoperto che guardare gli ultimi sei non mi è stato d'aiuto.) Rispondo anche sì per 0. (Nel leggere il codice qui sotto, nota che il mio input è
int64 x.)if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) ) return false; if( x == 0 ) return true; - Quindi, controlla se si tratta di un modulo quadrato 255 = 3 * 5 * 17. Poiché si tratta di un prodotto di tre numeri primi distinti, solo circa 1/8 dei residui mod 255 sono quadrati. Tuttavia, nella mia esperienza, chiamare l'operatore modulo (%) costa più del beneficio che si ottiene, quindi uso i trucchi per 255 = 2 ^ 8-1 per calcolare il residuo. (Nel bene o nel male, non sto usando il trucco di leggere i singoli byte da una parola, solo bit per bit e turni.)
Per verificare effettivamente se il residuo è un quadrato, cerco la risposta in una tabella pre-calcolata.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 - Infine, prova a calcolare la radice quadrata usando un metodo simile a il lemma di Hensel . (Non penso che sia applicabile direttamente, ma funziona con alcune modifiche.) Prima di farlo, divido tutti i poteri di 2 con una ricerca binaria:
A questo punto, affinché il nostro numero sia un quadrato, deve essere 1 mod 8.if((x & 4294967295LL) == 0) x >>= 32; if((x & 65535) == 0) x >>= 16; if((x & 255) == 0) x >>= 8; if((x & 15) == 0) x >>= 4; if((x & 3) == 0) x >>= 2;
La struttura di base del lemma di Hensel è la seguente. (Nota: codice non testato; se non funziona, prova t = 2 o 8.)if((x & 7) != 1) return false;
L'idea è che ad ogni iterazione, aggiungi un bit su r, il & Quot; corrente & Quot; radice quadrata di x; ogni radice quadrata è precisa modulo una potenza sempre maggiore di 2, vale a dire t / 2. Alla fine, r e t / 2-r saranno radici quadrate di x modulo t / 2. (Nota che se r è una radice quadrata di x, allora lo è anche -r. Questo vale anche per i numeri modulo, ma attenzione, modulo alcuni numeri, le cose possono avere anche più di 2 radici quadrate; in particolare, questo include poteri di 2. ) Poiché la nostra radice quadrata effettiva è inferiore a 2 ^ 32, a quel punto possiamo effettivamente verificare se r o t / 2-r sono radici quadrate reali. Nel mio codice attuale, utilizzo il seguente ciclo modificato: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.
Lo speedup qui si ottiene in tre modi: valore iniziale precompilato (equivalente a ~ 10 iterazioni del loop), uscita precedente del loop e salto di alcuni valori t. Per l'ultima parte, guardoint64 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 ho impostato t come la più grande potenza di 2 che divide z con un po 'di trucco. Questo mi permette di saltare t valori che non avrebbero comunque influenzato il valore di r. Il valore iniziale precompilato nel mio caso seleziona & Quot; il più piccolo & Quot positivo; radice quadrata modulo 8192.
Anche se questo codice non funziona più velocemente per te, spero che ti piacciano alcune delle idee che contiene. Segue il codice completo e testato, comprese le tabelle precompilate.
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;
}Altri suggerimenti
Sono in ritardo alla festa, ma spero di fornire una risposta migliore; più breve e (supponendo che il mio benchmark sia corretto) anche molto fast .
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;
}
Il primo test rileva rapidamente la maggior parte dei non quadrati. Utilizza una tabella di 64 elementi in un pacchetto lungo, quindi non ci sono costi di accesso all'array (controllo indiretto e limiti). Per un long uniformemente casuale, c'è una probabilità dell'81,25% di finire qui.
Il secondo test rileva tutti i numeri con un numero dispari di due nella loro fattorizzazione. Il metodo Long.numberOfTrailingZeros è molto veloce in quanto viene convertito in JIT in una singola istruzione i86.
Dopo aver lasciato cadere gli zeri finali, il terzo test gestisce i numeri che terminano con 011, 101 o 111 in binario, che non sono quadrati perfetti. Si preoccupa anche dei numeri negativi e gestisce anche 0.
Il test finale ricade su double aritmetica. Poiché <=> ha solo 53 bit di mantissa,
la conversione da <=> a <=> include arrotondamenti per valori elevati. Tuttavia, il test è corretto (a meno che prova è errata).
Cercare di incorporare l'idea mod255 non ha avuto successo.
Dovrai fare alcuni benchmark. Il miglior algoritmo dipenderà dalla distribuzione dei tuoi input.
Il tuo algoritmo potrebbe essere quasi ottimale, ma potresti voler fare un rapido controllo per escludere alcune possibilità prima di chiamare la tua routine radice quadrata. Ad esempio, guarda l'ultima cifra del tuo numero in esadecimale facendo un & Quot bit; e. & Quot; I quadrati perfetti possono terminare solo con 0, 1, 4 o 9 nella base 16, quindi per il 75% dei tuoi input (supponendo che siano distribuiti uniformemente) puoi evitare una chiamata alla radice quadrata in cambio di un po 'veloce twiddling.
Kip ha confrontato il seguente codice implementando il trucco esadecimale. Durante il test dei numeri da 1 a 100.000.000, questo codice ha funzionato due volte più velocemente dell'originale.
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 ho testato il codice analogo in C ++, in realtà ha funzionato più lentamente dell'originale. Tuttavia, quando ho eliminato l'istruzione switch, il trucco esadecimale rende ancora una volta il codice due volte più veloce.
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;
}
L'eliminazione dell'istruzione switch ha avuto scarso effetto sul codice C #.
Stavo pensando ai momenti orribili che ho trascorso nel corso di analisi numerica.
E poi ricordo che c'era questa funzione che girava intorno alla 'rete dal codice sorgente di 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;
}
Che sostanzialmente calcola una radice quadrata, usando la funzione di approssimazione di Newton (non ricordo il nome esatto).
Dovrebbe essere utilizzabile e potrebbe anche essere più veloce, proviene da uno dei fenomenali giochi del software id!
È scritto in C ++ ma non dovrebbe essere troppo difficile riutilizzare la stessa tecnica in Java una volta che hai avuto l'idea:
Inizialmente l'ho trovato su: http://www.codemaestro.com/reviews/9
Il metodo di Newton spiegato su wikipedia: http://en.wikipedia.org/wiki/Newton% 27s_method
Puoi seguire il link per ulteriori spiegazioni su come funziona, ma se non ti interessa molto, questo è più o meno quello che ricordo dalla lettura del blog e dal corso di analisi numerica:
-
* (long*) &yè fondamentalmente una funzione di conversione veloce in lunga, quindi le operazioni di numero intero possono essere applicate sui byte grezzi. - la
0x5f3759df - (i >> 1);riga è un valore seed precalcolato per la funzione di approssimazione. -
* (float*) &iconverte il valore in virgola mobile. - la
y = y * ( threehalfs - ( x2 * y * y ) )riga iterizza di nuovo basicamente il valore sulla funzione.
La funzione di approssimazione fornisce valori più precisi più si itera la funzione sul risultato. Nel caso di Quake, una iterazione è & Quot; abbastanza buono & Quot ;, ma se non fosse per te ... allora potresti aggiungere tutta l'iterazione di cui hai bisogno.
Questo dovrebbe essere più veloce perché riduce il numero di operazioni di divisione eseguite nel rooting del quadrato ingenuo fino a una divisione semplice di 2 (in realtà un'operazione di moltiplicazione * 0.5F) e la sostituisce con un numero fisso di operazioni di moltiplicazione.
Non sono sicuro che sarebbe più veloce o addirittura preciso, ma potresti usare Radice quadrata magica di John Carmack , algoritmo per risolvere più rapidamente la radice quadrata. Probabilmente potresti facilmente testarlo per tutti i possibili numeri interi a 32 bit e confermare che hai effettivamente ottenuto risultati corretti, in quanto è solo una approssimazione. Tuttavia, ora che ci penso, anche l'uso del doppio è approssimativo, quindi non sono sicuro di come entrerebbe in gioco.
Se si esegue un taglio binario per provare a trovare il " giusto " radice quadrata, puoi facilmente rilevare se il valore che hai è abbastanza vicino da dire:
(n+1)^2 = n^2 + 2n + 1
(n-1)^2 = n^2 - 2n + 1
Quindi, avendo calcolato n^2, le opzioni sono:
-
n^2 = target: fatto, ritorna vero -
n^2 + 2n + 1 > target > n^2: sei vicino, ma non è perfetto: return false -
n^2 - 2n + 1 < target < n^2: idem -
target < n^2 - 2n + 1: taglio binario su unn inferiore
-
target > n^2 + 2n + 1: taglio binario su untarget superiore
(Siamo spiacenti, questo utilizza (2^x)^2 = 2^(2x) come ipotesi corrente e <=> per il parametro. Chiedere scusa per la confusione!)
Non so se sarà più veloce o meno, ma vale la pena provare.
EDIT: il chop binario non deve accettare l'intero intervallo di numeri interi, neanche <=>, quindi una volta trovato il bit impostato in alto nel tuo target (che può essere fatto con un trucco a bit-twiddling ; Dimentico esattamente come) puoi ottenere rapidamente una serie di potenziali risposte. Intendiamoci, un ingenuo binario binario richiederà solo fino a 31 o 32 iterazioni.
Ho eseguito la mia analisi di alcuni degli algoritmi in questo thread e ho trovato alcuni nuovi risultati. Puoi vedere quei vecchi risultati nella cronologia delle modifiche di questa risposta, ma non sono accurati, poiché ho fatto un errore e ho perso tempo ad analizzare diversi algoritmi che non sono vicini. Tuttavia, traendo lezioni da diverse risposte, ora ho due algoritmi che schiacciano il & Quot; vincitore & Quot; di questa discussione. Ecco la cosa principale che faccio in modo diverso rispetto a tutti gli altri:
// 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;
Tuttavia, questa semplice riga, che la maggior parte delle volte aggiunge una o due istruzioni molto veloci, semplifica notevolmente l'istruzione switch-case in un'istruzione if. Tuttavia, può aumentare il tempo di esecuzione se molti dei numeri testati presentano significativi fattori di potenza di due.
Gli algoritmi seguenti sono i seguenti:
- Internet : la risposta postata da Kip
- Durazzo : la mia risposta modificata utilizzando la risposta a passaggio singolo come base
- DurronTwo - La mia risposta modificata utilizzando la risposta a due passaggi (di @JohnnyHeggheim), con alcune altre lievi modifiche.
Ecco un runtime di esempio se i numeri sono generati 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
Ed ecco un esempio di runtime se eseguito solo sul primo milione di long:
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
Come puoi vedere, DurronTwo fa meglio per input di grandi dimensioni, perché usa il trucco magico molto spesso, ma viene ostruito rispetto al primo algoritmo e Math.sqrt perché i numeri sono molto più piccoli. Nel frattempo, il più semplice Durron è un grande vincitore perché non deve mai dividere per 4 molte volte nei primi milioni di numeri.
Ecco 0xFFFFFF = 3 x 3 x 5 x 7 x 13 x 17 x 241:
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 + 0xFFFFFF
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 il mio cablaggio di riferimento: (richiede Google caliper 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);
}
}
AGGIORNAMENTO: ho creato un nuovo algoritmo che è più veloce in alcuni scenari, più lento in altri, ho ottenuto benchmark diversi basati su input diversi. Se calcoliamo il modulo + 0x1FFFFFE, possiamo eliminare il 97,82% dei numeri che non possono essere quadrati. Questo può essere (una specie di) fatto in una riga, con 5 operazioni bit a bit:
if (!goodLookupSquares[(int) ((n & 0xFFFFFFl) + ((n >> 24) & 0xFFFFFFl) + (n >> 48))]) return false;
L'indice risultante è 1) il residuo, 2) il residuo 0xFFFFFF o 3) il residuo ByteBuffer. Ovviamente, dobbiamo avere una tabella di ricerca per i residui modulo boolean, che è circa un file 3mb (in questo caso memorizzato come numeri decimali di testo ASCII, non ottimale ma chiaramente migliorabile con un <=> e così via. Ma dal momento che questo è il calcolo preliminare non importa così tanto. Puoi trovare il file qui ( o generalo tu stesso):
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 carico in un <=> array come questo:
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();
}
Esempio di runtime. Ha battuto <=> (versione uno) in ogni prova che ho eseguito.
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
Dovrebbe essere molto più veloce usare il metodo di Newton per calcolare Integer Square Root , quindi quadrare questo numero e verificare, come si fa nella soluzione corrente. Il metodo di Newton è la base della soluzione Carmack menzionata in alcune altre risposte. Dovresti essere in grado di ottenere una risposta più veloce poiché sei interessato solo alla parte intera della radice, consentendoti di interrompere prima l'algoritmo di approssimazione.
Un'altra ottimizzazione che puoi provare: se il Root digitale di un numero non finisce nel 1, 4, 7 o 9 il numero è non un quadrato perfetto. Questo può essere usato come un modo rapido per eliminare il 60% degli input prima di applicare l'algoritmo radice quadrata più lento.
Voglio che questa funzione funzioni con tutti numeri interi con segno a 64 bit positivi
Math.sqrt() funziona con i doppi come parametri di input, quindi non otterrai risultati accurati per numeri interi superiori a 2 ^ 53 .
Solo per la cronaca, un altro approccio consiste nell'utilizzare la decomposizione primaria. Se ogni fattore di decomposizione è pari, il numero è un quadrato perfetto. Quindi quello che vuoi è vedere se un numero può essere scomposto come prodotto di quadrati di numeri primi. Naturalmente, non è necessario ottenere una tale scomposizione, solo per vedere se esiste.
Prima costruisci una tabella di quadrati di numeri primi che sono inferiori a 2 ^ 32. Questo è molto più piccolo di una tabella di tutti i numeri interi fino a questo limite.
Una soluzione sarebbe quindi questa:
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;
}
}
Suppongo sia un po 'enigmatico. Ciò che fa è verificare in ogni passaggio che il quadrato di un numero primo divida il numero di input. In tal caso, divide il numero per il quadrato il più a lungo possibile, per rimuovere questo quadrato dalla decomposizione primaria. Se con questo processo arrivassimo a 1, allora il numero di input era una decomposizione del quadrato dei numeri primi. Se il quadrato diventa più grande del numero stesso, allora non c'è modo che questo quadrato, o qualsiasi quadrato più grande, possa dividerlo, quindi il numero non può essere una scomposizione di quadrati di numeri primi.
Dato lo sqrt di oggi fatto in hardware e la necessità di calcolare i numeri primi qui, immagino che questa soluzione sia molto più lenta. Ma dovrebbe dare risultati migliori della soluzione con sqrt che non funzionerà su 2 ^ 54, come dice mrzl nella sua risposta.
Un problema intero merita una soluzione intera. Così
Esegui una ricerca binaria sugli interi (non negativi) per trovare l'intero più grande t tale che t**2 <= n. Quindi verifica se r**2 = n esattamente. Questo richiede tempo O (log n).
Se non sai come cercare binariamente gli interi positivi perché l'insieme non ha limiti, è facile. Si inizia calcolando la funzione crescente f (sopra f(t) = t**2 - n) con potenze di due. Quando lo vedi diventare positivo, hai trovato un limite superiore. Quindi puoi fare una ricerca binaria standard.
È stato sottolineato che le ultime d cifre di un quadrato perfetto possono assumere solo determinati valori. Le ultime b cifre (nella base n) di un numero n % pow(b, d) sono le stesse del resto quando m è diviso per n % m<=> , vale a dire. nella notazione C <=>.
Questo può essere generalizzato a qualsiasi modulo <=>, cioè. <=> può essere utilizzato per escludere una percentuale di numeri dall'essere quadrati perfetti. Il modulo attualmente in uso è 64, che consente 12, ovvero. 19% dei resti, come possibili quadrati. Con un po 'di codice ho trovato il modulo 110880, che consente solo il 2016, vale a dire. 1,8% dei resti come quadrati possibili. Quindi, a seconda del costo di un'operazione di un modulo (ad es. Divisione) e di una ricerca della tabella rispetto a una radice quadrata sulla tua macchina, l'utilizzo di questo modulo potrebbe essere più veloce.
A proposito, se Java ha un modo per memorizzare un array compresso di bit per la tabella di ricerca, non usarlo. 110880 parole a 32 bit non sono molta RAM in questi giorni e il recupero di una parola macchina sarà più veloce del recupero di un singolo bit.
Per le prestazioni, molto spesso devi fare alcune cose. Altri hanno espresso vari metodi, tuttavia, hai notato che l'hack di Carmack era più veloce fino a determinati valori di N. Quindi, dovresti controllare & Quot; n & Quot; e se è inferiore a quel numero N, usa l'hack di Carmack, altrimenti usa qualche altro metodo descritto nelle risposte qui.
Questa è l'implementazione Java più veloce che ho potuto inventare, usando una combinazione di tecniche suggerite da altri in questo thread.
- Test Mod-256
- Test inesatto mod-3465 (evita la divisione intera al costo di alcuni falsi positivi)
- Radice quadrata a virgola mobile, arrotondata e confrontata con il valore di input
Ho anche sperimentato queste modifiche ma non hanno aiutato le prestazioni:
- Test mod-255 aggiuntivo
- Divisione del valore di input per potenze di 4
- Radice quadrata inversa veloce (per funzionare con valori elevati di N necessita di 3 iterazioni, abbastanza per renderla più lenta della funzione hardware radice quadrata.)
public class SquareTester {
public static boolean isPerfectSquare(long n) {
if (n < 0) {
return false;
} else {
switch ((byte) n) {
case -128: case -127: case -124: case -119: case -112:
case -111: case -103: case -95: case -92: case -87:
case -79: case -71: case -64: case -63: case -60:
case -55: case -47: case -39: case -31: case -28:
case -23: case -15: case -7: case 0: case 1:
case 4: case 9: case 16: case 17: case 25:
case 33: case 36: case 41: case 49: case 57:
case 64: case 65: case 68: case 73: case 81:
case 89: case 97: case 100: case 105: case 113:
case 121:
long i = (n * INV3465) >>> 52;
if (! good3465[(int) i]) {
return false;
} else {
long r = round(Math.sqrt(n));
return r*r == n;
}
default:
return false;
}
}
}
private static int round(double x) {
return (int) Double.doubleToRawLongBits(x + (double) (1L << 52));
}
/** 3465<sup>-1</sup> modulo 2<sup>64</sup> */
private static final long INV3465 = 0x8ffed161732e78b9L;
private static final boolean[] good3465 =
new boolean[0x1000];
static {
for (int r = 0; r < 3465; ++ r) {
int i = (int) ((r * r * INV3465) >>> 52);
good3465[i] = good3465[i+1] = true;
}
}
}
La seguente semplificazione della soluzione di maaartinus sembra radere qualche punto percentuale dal tempo di esecuzione, ma non sono abbastanza bravo nel benchmarking per produrre un benchmark di cui mi posso fidare:
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;
}
Vale la pena verificare come omettere il primo test,
if (goodMask << x >= 0) return false;
inciderebbe sulle prestazioni.
Dovresti sbarazzarti della parte 2-power di N fin dall'inizio.
2a modifica L'espressione magica per m sotto dovrebbe essere
m = N - (N & (N-1));
e non come scritto
Fine della seconda modifica
m = N & (N-1); // the lawest bit of N
N /= m;
byte = N & 0x0F;
if ((m % 2) || (byte !=1 && byte !=9))
return false;
1a modifica:
Miglioramento minore:
m = N & (N-1); // the lawest bit of N
N /= m;
if ((m % 2) || (N & 0x07 != 1))
return false;
Fine della prima modifica
Ora continua come al solito. In questo modo, quando arrivi alla parte in virgola mobile, ti sei già sbarazzato di tutti i numeri la cui parte a 2 potenze è dispari (circa la metà), e quindi consideri solo 1/8 di ciò che rimane. Cioè esegui la parte in virgola mobile sul 6% dei numeri.
Questa è una rielaborazione dal decimale al binario del vecchio algoritmo del calcolatore Marchant (scusate, non ho un riferimento), in Ruby, adattato specificamente per questa domanda:
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
Ecco un riassunto di qualcosa di simile (per favore non votarmi per stile / odori di codifica o O / O goffo - è l'algoritmo che conta, e C ++ non è la mia lingua madre). In questo caso, stiamo cercando 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 chiamata sqrt non è perfettamente accurata, come è stato menzionato, ma è interessante e istruttivo che non soffia via le altre risposte in termini di velocità. Dopotutto, la sequenza delle istruzioni del linguaggio assembly per un sqrt è minuscola. Intel ha un'istruzione hardware, che non è utilizzata da Java credo perché non conforme a IEEE.
Quindi perché è lento? Poiché Java sta effettivamente chiamando una routine C tramite JNI, ed è in realtà più lento farlo che chiamare una subroutine Java, che a sua volta è più lenta del farlo in linea. Questo è molto fastidioso e Java avrebbe dovuto trovare una soluzione migliore, ovvero compilare chiamate in libreria in virgola mobile se necessario. Oh bene.
In C ++, sospetto che tutte le alternative complesse perderebbero velocità, ma non le ho controllate tutte. Quello che ho fatto, e ciò che le persone Java troveranno utili, è un semplice hack, un'estensione del test sui casi speciali suggerito da A. Rex. Utilizzare un singolo valore lungo come array di bit, che non è controllato dai limiti. In questo modo, hai una ricerca booleana a 64 bit.
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 routine isPerfectSquare5 viene eseguita in circa 1/3 del tempo sulla mia macchina core2 duo. Ho il sospetto che ulteriori modifiche lungo le stesse linee potrebbero ridurre ulteriormente i tempi in media, ma ogni volta che controlli, stai scambiando più test per più eliminando, quindi non puoi andare troppo oltre su quella strada.
Certamente, piuttosto che avere un test separato per negativo, è possibile controllare i 6 bit alti allo stesso modo.
Nota che tutto ciò che sto facendo è eliminare possibili quadrati, ma quando ho un caso potenziale devo chiamare l'originale isPerfectSquare in linea.
La routine init2 viene chiamata una volta per inizializzare i valori statici di pp1 e pp2. Nota che nella mia implementazione in C ++, sto usando unsigned long long, quindi dato che sei firmato, dovresti usare & Gt; & Gt; & Gt; operatore.
Non è necessario intrinsecamente controllare i limiti dell'array, ma l'ottimizzatore Java deve capire queste cose abbastanza rapidamente, quindi non me ne incolpo.
Mi piace l'idea di utilizzare un metodo quasi corretto su alcuni degli input. Ecco una versione con & Quot; offset & Quot ;. Il codice sembra funzionare e passa il mio semplice test case.
Sostituisci semplicemente il tuo:
if(n < 410881L){...}
codice con questo:
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);
}
Il Project Euler è menzionato nei tag e molti dei problemi in esso contenuti richiedono il controllo dei numeri > > 2^64. La maggior parte delle ottimizzazioni sopra menzionate non funzionano facilmente quando si lavora con un buffer da 80 byte.
Ho usato java BigInteger e una versione leggermente modificata del metodo di Newton, che funziona meglio con i numeri interi. Il problema era che i quadrati esatti n^2 convergevano in (n-1) anziché n perché n^2-1 = (n-1)(n+1) e l'errore finale era solo un gradino sotto il divisore finale e l'algoritmo è terminato. È stato facile risolvere aggiungendo uno all'argomento originale prima di calcolare l'errore. (Aggiungine due per le radici del cubo, ecc.)
Un bel attributo di questo algoritmo è che puoi immediatamente dire se il numero è un quadrato perfetto - l'errore finale (non la correzione) nel metodo di Newton sarà zero. Una semplice modifica consente inoltre di calcolare rapidamente floor(sqrt(x)) anziché il numero intero più vicino. Questo è utile con diversi problemi di Eulero.
Ho controllato tutti i possibili risultati quando si osservano gli ultimi n bit di un quadrato. Esaminando successivamente più bit, è possibile eliminare fino a 5 / 6th di input. In realtà l'ho progettato per implementare l'algoritmo di fattorizzazione di Fermat, ed è molto veloce 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;
}
L'ultimo bit di pseudocodice può essere utilizzato per estendere i test per eliminare più valori. I test sopra riportati sono per k = 0, 1, 2, 3
Prima verifica se ha un residuo quadrato con moduli di potenza di due, quindi verifica in base a un modulo finale, quindi utilizza Math.sqrt per eseguire un test finale. Mi è venuta l'idea dal primo post e ho cercato di estenderla. Apprezzo qualsiasi commento o suggerimento.
Aggiornamento: utilizzando il test di un modulo, (modSq) e una base di moduli di 44352, il mio test viene eseguito nel 96% del tempo di quello nell'aggiornamento dell'OP per numeri fino a 1.000.000.000 .
Considerando la lunghezza generale dei bit (anche se qui ho usato un tipo specifico), ho provato a progettare un algo semplicistico come di seguito. Inizialmente è richiesto un controllo semplice ed evidente per 0,1,2 o & Lt; 0. Di seguito è semplice nel senso che non tenta di utilizzare alcuna funzione matematica esistente. La maggior parte dell'operatore può essere sostituita con operatori bit-saggi. Non ho ancora testato con nessun dato di riferimento. Non sono esperto di matematica o di progettazione di algoritmi informatici in particolare, mi piacerebbe vederti evidenziare un problema. So che ci sono molte possibilità di miglioramento 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;
}
Non so se questo è stato menzionato prima. Ma ho trovato una soluzione qui :
int result = (int)(floor(sqrt(b)) - ceil(sqrt(a)) + 1);
Se la velocità è un problema, perché non partizionare il set di input più comunemente usato e i loro valori in una tabella di ricerca e fare qualunque algoritmo magico ottimizzato che hai inventato per casi eccezionali?
Dovrebbe essere possibile impacchettare 'non può essere un quadrato perfetto se le ultime X cifre sono N' in modo molto più efficiente di così! Userò java a 32 bit ints e produrrò abbastanza dati per controllare gli ultimi 16 bit del numero: sono 2048 valori int esadecimali.
...
Ok. O mi sono imbattuto in una teoria dei numeri che è un po 'al di là di me, oppure c'è un bug nel mio codice. In ogni caso, ecco il codice:
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 qui ci sono i risultati:
(a cura di: elided per prestazioni scadenti in prettify.js; vedere la cronologia delle revisioni per vedere.)
Ecco il modo più semplice e conciso, anche se non so come si paragona in termini di cicli della CPU. Funziona alla grande se vuoi solo sapere se la radice è un numero intero. Se ti interessa davvero che sia un numero intero, puoi anche capirlo. Ecco una funzione semplice (e pura):
public static boolean isRootWhole(double number) {
return Math.sqrt(number) % 1 == 0;
}
Se non hai bisogno di micro-ottimizzazione, questa risposta è migliore in termini di semplicità e manutenibilità. Se otterrai numeri negativi, forse vorrai usare Math.abs () sull'argomento numero come argomento Math.sqrt ().
Sulla mia CPU Intel i7-4790 da 3,6 Ghz, una corsa di questo algoritmo su 0 - 10.000.000 ha richiesto una media di 35 - 37 nanosecondi per calcolo. Ho eseguito 10 sequenze sequenziali, stampando il tempo medio trascorso su ciascuno dei dieci milioni di calcoli sqrt. Il completamento di ciascuna corsa totale ha richiesto poco più di 600 ms.
Se si esegue un numero inferiore di calcoli, i calcoli precedenti richiedono un po 'più di tempo.
Ecco una soluzione di divisione e conquista.
Se la radice quadrata di un numero naturale (number) è un numero naturale (solution), puoi facilmente determinare un intervallo per <=> in base al numero di cifre di <=>:
- <=> ha 1 cifra: <=> nell'intervallo = 1 - 4
- <=> ha 2 cifre: <=> nell'intervallo = 3 - 10
- <=> ha 3 cifre: <=> nell'intervallo = 10 - 40
- <=> ha 4 cifre: <=> nell'intervallo = 30 - 100
- <=> ha 5 cifre: <=> nell'intervallo = 100 - 400
Notare la ripetizione?
Puoi utilizzare questo intervallo in un approccio di ricerca binaria per vedere se esiste un <=> per il quale:
number == solution * solution
Ecco il codice
Ecco la mia classe SquareRootChecker
public class SquareRootChecker {
private long number;
private long initialLow;
private long initialHigh;
public SquareRootChecker(long number) {
this.number = number;
initialLow = 1;
initialHigh = 4;
if (Long.toString(number).length() % 2 == 0) {
initialLow = 3;
initialHigh = 10;
}
for (long i = 0; i < Long.toString(number).length() / 2; i++) {
initialLow *= 10;
initialHigh *= 10;
}
if (Long.toString(number).length() % 2 == 0) {
initialLow /= 10;
initialHigh /=10;
}
}
public boolean checkSquareRoot() {
return findSquareRoot(initialLow, initialHigh, number);
}
private boolean findSquareRoot(long low, long high, long number) {
long check = low + (high - low) / 2;
if (high >= low) {
if (number == check * check) {
return true;
}
else if (number < check * check) {
high = check - 1;
return findSquareRoot(low, high, number);
}
else {
low = check + 1;
return findSquareRoot(low, high, number);
}
}
return false;
}
}
Ed ecco un esempio su come usarlo.
long number = 1234567;
long square = number * number;
SquareRootChecker squareRootChecker = new SquareRootChecker(square);
System.out.println(square + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677489: true"
long notSquare = square + 1;
squareRootChecker = new SquareRootChecker(notSquare);
System.out.println(notSquare + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677490: false"
Se vuoi la velocità, dato che i tuoi numeri interi sono di dimensioni finite, sospetto che il modo più veloce implicherebbe (a) il partizionamento dei parametri per dimensione (ad esempio in categorie per set di bit più grande), quindi controllando il valore su un array di quadrati perfetti all'interno di quell'intervallo.
Per quanto riguarda il metodo Carmac, sembra che sarebbe abbastanza semplice iterare ancora una volta, il che dovrebbe raddoppiare il numero di cifre dell'accuratezza. Dopotutto, è un metodo iterativo estremamente troncato: quello di Newton, con un'ottima prima ipotesi.
Per quanto riguarda il tuo meglio attuale, vedo due micro-ottimizzazioni:
- sposta il segno di spunta su 0 dopo il controllo usando mod255
- riorganizza i poteri di divisione di quattro per saltare tutti i controlli per il solito caso (75%).
cioè:
// 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;
}
Ancora meglio potrebbe essere un semplice
while ((n & 0x03L) == 0) n >>= 2;
Ovviamente, sarebbe interessante sapere quanti numeri vengono abbattuti ad ogni checkpoint - dubito piuttosto che i controlli siano veramente indipendenti, il che rende le cose difficili.
" Sto cercando il modo più veloce per determinare se un valore lungo è un quadrato perfetto (cioè la sua radice quadrata è un altro numero intero). "
Le risposte sono impressionanti, ma non sono riuscito a vedere un semplice controllo:
controlla se il primo numero a destra del lungo è un membro dell'insieme (0,1,4,5,6,9). In caso contrario, non può essere un "quadrato perfetto".
ad es.
4567 - non può essere un quadrato perfetto.
