Cara tercepat untuk menentukan apakah akar kuadrat bilangan bulat adalah bilangan bulat

1454

Saya mencari cara tercepat untuk menentukan apakah suatu longnilai adalah kuadrat sempurna (yaitu akar kuadratnya adalah bilangan bulat lain):

  1. Saya telah melakukannya dengan cara mudah, dengan menggunakan Math.sqrt() fungsi bawaan, tetapi saya bertanya-tanya apakah ada cara untuk melakukannya lebih cepat dengan membatasi diri Anda ke domain integer-only.
  2. Mempertahankan tabel pencarian tidak praktis (karena ada sekitar 2 31,5 bilangan bulat yang kuadratnya kurang dari 2 63 ).

Inilah cara yang sangat sederhana dan mudah yang saya lakukan sekarang:

public final static boolean isPerfectSquare(long n)
{
  if (n < 0)
    return false;

  long tst = (long)(Math.sqrt(n) + 0.5);
  return tst*tst == n;
}

Catatan: Saya menggunakan fungsi ini di banyak masalah Project Euler . Jadi tidak ada orang lain yang harus mempertahankan kode ini. Dan optimasi mikro semacam ini sebenarnya bisa membuat perbedaan, karena bagian dari tantangannya adalah melakukan setiap algoritma dalam waktu kurang dari satu menit, dan fungsi ini perlu disebut jutaan kali dalam beberapa masalah.

Saya sudah mencoba berbagai solusi untuk masalah ini:

  • Setelah pengujian menyeluruh, saya menemukan bahwa menambahkan 0.5ke hasil Math.sqrt () tidak diperlukan, setidaknya tidak pada mesin saya.
  • The cepat terbalik akar kuadrat lebih cepat, tapi itu memberi hasil yang salah untuk n> = 410881. Namun, seperti yang disarankan oleh BobbyShaftoe , kita dapat menggunakan hack FISR untuk n <410.881.
  • Metode Newton sedikit lebih baik daripada Math.sqrt(). Ini mungkin karena Math.sqrt()menggunakan sesuatu yang mirip dengan Metode Newton, tetapi diterapkan pada perangkat keras sehingga jauh lebih cepat daripada di Jawa. Juga, Metode Newton masih membutuhkan penggunaan ganda.
  • Metode Newton yang dimodifikasi, yang menggunakan beberapa trik sehingga hanya matematika bilangan bulat yang terlibat, diperlukan beberapa peretasan untuk menghindari overflow (Saya ingin fungsi ini bekerja dengan semua bilangan bulat bertanda positif 64-bit), dan masih lebih lambat daripada Math.sqrt().
  • Chop biner bahkan lebih lambat. Ini masuk akal karena memotong biner rata-rata akan memerlukan 16 lintasan untuk menemukan akar kuadrat dari angka 64-bit.
  • Menurut tes John, menggunakan orpernyataan lebih cepat di C ++ daripada menggunakan a switch, tetapi di Jawa dan C # tampaknya tidak ada perbedaan antara ordan switch.
  • Saya juga mencoba membuat tabel pencarian (sebagai array statis privat dari nilai 64 boolean). Maka alih-alih beralih atau orpernyataan, saya hanya akan mengatakan if(lookup[(int)(n&0x3F)]) { test } else return false;. Yang mengejutkan saya, ini (hanya sedikit) lebih lambat. Ini karena batas array diperiksa di Jawa .
java math optimization perfect-square Kip
sumber
21
Ini adalah kode Java, di mana int == 32 bit dan panjang == 64 bit, dan keduanya ditandatangani.
Kip
14
@ Shreevasta: Saya telah melakukan beberapa pengujian pada nilai-nilai besar (lebih besar dari 2 ^ 53), dan metode Anda memberikan beberapa positif palsu. Yang pertama ditemui adalah untuk n = 9007199326062755, yang bukan kuadrat sempurna tetapi dikembalikan sebagai satu.
Kip
37
Tolong jangan menyebutnya "John Carmack hack." Dia tidak datang dengan itu.
user9282
84
@ Mamama - Mungkin, tapi itu karena dia. Henry Ford tidak menciptakan mobil, Wright Bros. tidak menciptakan pesawat terbang, dan Galleleo bukan yang pertama kali mengetahui Bumi berputar mengelilingi matahari ... dunia terdiri dari penemuan curian (dan cinta).
Robert Fraser
4
Anda mungkin mendapatkan peningkatan kecepatan kecil di 'quickfail' dengan menggunakan sesuatu seperti ((1<<(n&15))|65004) != 0, daripada melakukan tiga pemeriksaan terpisah.
Nabb

Jawaban:

736

Saya menemukan metode yang bekerja ~ 35% lebih cepat dari kode 6bit + Carmack + sqrt Anda, setidaknya dengan CPU saya (x86) dan bahasa pemrograman (C / C ++). Hasil Anda dapat bervariasi, terutama karena saya tidak tahu bagaimana faktor Java akan dimainkan.

Pendekatan saya ada tiga:

  1. Pertama, filter jawaban yang jelas. Ini termasuk angka negatif dan melihat 4 bit terakhir. (Saya menemukan melihat enam yang terakhir tidak membantu.) Saya juga menjawab ya untuk 0. (Dalam membaca kode di bawah ini, perhatikan bahwa input saya adalah int64 x.) 
    if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) )
    return false;
if( x == 0 )
    return true;
  2. Selanjutnya, periksa apakah itu adalah modulo 255 = 3 * 5 * 17. Karena itu adalah produk dari tiga bilangan prima yang berbeda, hanya sekitar 1/8 residu mod 255 yang berbentuk bujur sangkar. Namun, dalam pengalaman saya, memanggil operator modulo (%) lebih mahal daripada manfaatnya, jadi saya menggunakan sedikit trik yang melibatkan 255 = 2 ^ 8-1 untuk menghitung residu. (Untuk lebih baik atau lebih buruk, saya tidak menggunakan trik membaca byte individu dari sebuah kata, hanya bitwise-and dan bergeser.) 
    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.
    Untuk benar-benar memeriksa apakah residu adalah kuadrat, saya mencari jawabannya di tabel yang sudah dihitung sebelumnya. 
    if( bad255[y] )
    return false;
// However, I just use a table of size 512
  3. Akhirnya, cobalah untuk menghitung akar kuadrat menggunakan metode yang mirip dengan lemma Hensel . (Saya tidak berpikir itu berlaku secara langsung, tetapi bekerja dengan beberapa modifikasi.) Sebelum melakukan itu, saya membagi semua kekuatan 2 dengan pencarian biner: 
    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;
    Pada titik ini, agar angka kita menjadi bujur sangkar, itu harus 1 mod 8. 
    if((x & 7) != 1)
    return false;
    Struktur dasar lemens Hensel adalah sebagai berikut. (Catatan: kode yang belum diuji; jika tidak berhasil, coba t = 2 atau 8.) 
    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.
    Idenya adalah bahwa pada setiap iterasi, Anda menambahkan satu bit ke r, akar kuadrat "saat ini" dari x; setiap root kuadrat adalah modulo akurat yang lebih besar dan lebih besar dari 2 daya, yaitu t / 2 Pada akhirnya, r dan t / 2-r akan menjadi akar kuadrat dari x modulo t / 2. (Perhatikan bahwa jika r adalah akar kuadrat dari x, maka demikian juga -r. Ini benar bahkan nomor modulo, tetapi berhati-hatilah, modulo beberapa angka, hal-hal dapat memiliki lebih dari 2 akar kuadrat; terutama, ini termasuk kekuatan 2. ) Karena akar kuadrat aktual kita kurang dari 2 ^ 32, pada titik itu kita dapat benar-benar memeriksa apakah r atau t / 2-r adalah akar kuadrat nyata. Dalam kode saya yang sebenarnya, saya menggunakan loop yang dimodifikasi berikut: 
    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) );
    Speedup di sini diperoleh dalam tiga cara: nilai awal yang dikomputasi (setara dengan ~ 10 iterasi loop), keluar sebelumnya dari loop, dan melewatkan beberapa nilai t. Untuk bagian terakhir, saya melihat z = r - x * x, dan mengatur t menjadi kekuatan terbesar dari 2 z membagi dengan sedikit trik. Ini memungkinkan saya untuk melewatkan nilai t yang tidak akan memengaruhi nilai r. Nilai awal yang dikomputasi dalam kasus saya memilih modulo 8192 akar kuadrat "positif terkecil".

Bahkan jika kode ini tidak bekerja lebih cepat untuk Anda, saya harap Anda menikmati beberapa ide yang terkandung di dalamnya. Kode lengkap dan teruji mengikuti, termasuk tabel prakomputasi.

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;
}
A. Rex
sumber
5
Wow! Saya akan mencoba mengonversikan ini ke Java dan melakukan perbandingan, serta memeriksa akurasi hasilnya. Saya akan memberi tahu Anda apa yang saya temukan.
Kip
79
Wow, ini indah. Saya pernah melihat Hensel mengangkat sebelumnya (menghitung akar polinomial modulo menjadi yang utama) tetapi saya bahkan tidak menyadari bahwa lemma dapat dengan hati-hati diturunkan hingga menghitung akar kuadrat angka; ini ... semangat :)
ShreevatsaR
3
@ nightcracker Tidak. 9 < 0 => false, 9&2 => 0, 9&7 == 5 => false, 9&11 == 8 => false.
primo
53
Maartinus memposting solusi 2x lebih cepat (dan jauh lebih pendek) di bawah, sedikit kemudian, yang sepertinya tidak mendapatkan banyak cinta.
Jason C
3
Sepertinya banyak keuntungan kecepatan dalam solusi yang berbeda diperoleh dengan menyaring kotak yang jelas. Adakah yang membandingkan situasi penyaringan melalui solusi Maartinus dan kemudian hanya menggunakan fungsi sqrt karena itu adalah fungsi bawaan?
user1914292
378

Saya sangat terlambat ke pesta, tetapi saya berharap dapat memberikan jawaban yang lebih baik; lebih pendek dan (dengan asumsi tolok ukur saya benar) juga jauh lebih cepat .

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

Tes pertama menangkap sebagian besar non-kotak dengan cepat. Ini menggunakan tabel 64-item yang dikemas dalam panjang, jadi tidak ada biaya akses array (tipuan dan cek batas). Untuk acak yang seragam long, ada kemungkinan 81,25% untuk berakhir di sini.

Tes kedua menangkap semua angka yang memiliki jumlah ganjil dari dua faktorisasi mereka. Metode Long.numberOfTrailingZerosini sangat cepat karena mendapat JIT-ed menjadi instruksi i86 tunggal.

Setelah menjatuhkan nol yang tertinggal, tes ketiga menangani angka yang berakhiran 011, 101, atau 111 dalam biner, yang bukan kotak yang sempurna. Ini juga peduli tentang angka negatif dan juga menangani 0.

Tes akhir jatuh kembali ke doublearitmatika. Karena doublehanya memiliki 53 bit mantissa, konversi dari longmenjadi doublepembulatan untuk nilai besar. Meskipun demikian, tes ini benar (kecuali buktinya salah).

Mencoba memasukkan ide mod255 tidak berhasil.

maaartinus
sumber
3
Penyamaran implisit dari nilai pergeseran itu agak ... jahat. Apakah Anda tahu mengapa itu ada dalam spesifikasi Java?
dfeuer
6
@ PDFer Saya kira ada dua alasan: 1. Bergeser lebih banyak tidak masuk akal. 2. Ini seperti HW bekerja dan siapa pun yang menggunakan operasi bitwise tertarik pada kinerja, jadi melakukan hal lain akan salah. - The goodMaskuji melakukannya, tetapi melakukannya sebelum pergeseran yang tepat. Jadi Anda harus mengulanginya, tetapi dengan cara ini lebih sederhana dan AFAIK sedikit lebih cepat dan sama-sama bagus.
maaartinus
3
@ PDFeuer Untuk tolok ukur, penting untuk memberikan jawaban ASAP, dan trailing zero count itu sendiri tidak memberikan jawaban; itu hanya langkah persiapan. i86 / amd64 melakukannya. Tidak tahu tentang CPU kecil di ponsel, tetapi yang terburuk, Java harus membuat instruksi AND untuk mereka, yang tentu saja lebih sederhana daripada sebaliknya.
maaartinus
2
@Sebastian Sebuah tes mungkin lebih baik: if ((x & (7 | Integer.MIN_VALUE)) != 1) return x == 0;.
maaartinus
4
"Karena ganda hanya memiliki 56 bit mantissa" -> Saya akan mengatakan itu lebih mungkin memiliki bit 53 . Juga
chux - Reinstate Monica
132

Anda harus melakukan pembandingan. Algoritma terbaik akan tergantung pada distribusi input Anda.

Algoritme Anda mungkin hampir optimal, tetapi Anda mungkin ingin melakukan pemeriksaan cepat untuk mengesampingkan beberapa kemungkinan sebelum memanggil rutin akar kuadrat Anda. Sebagai contoh, lihat digit terakhir nomor Anda dalam hex dengan melakukan sedikit-bijaksana "dan." Kuadrat sempurna hanya bisa berakhir pada 0, 1, 4, atau 9 di basis 16, Jadi untuk 75% dari input Anda (dengan asumsi mereka terdistribusi secara merata) Anda dapat menghindari panggilan ke root kuadrat dengan imbalan sedikit twiddling yang sangat cepat.

Kip membandingkan kode berikut ini dengan mengimplementasikan trik heks. Saat menguji angka 1 hingga 100.000.000, kode ini berlari dua kali lebih cepat dari aslinya.

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

Ketika saya menguji kode analog dalam C ++, itu sebenarnya berjalan lebih lambat dari aslinya. Namun, ketika saya menghilangkan pernyataan switch, trik hex sekali lagi membuat kode dua kali lebih cepat.

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

Menghilangkan pernyataan switch tidak banyak berpengaruh pada kode C #.

John D. Cook
sumber
itu cukup pintar ... tidak akan memikirkan itu
warren
Poin bagus tentang bit tambahan. Saya akan mencoba menggabungkan tes itu dengan beberapa komentar lain di sini.
PeterAllenWebb
3
Solusi luar biasa. Ingin tahu bagaimana Anda membuatnya? Apakah prinsip yang cukup mapan atau hanya sesuatu yang Anda tahu? : D
Jeel Shah
3
@ LarsH Tidak perlu menambahkan 0,5, lihat solusi saya untuk tautan ke buktinya.
maaartinus
2
@ JerryGoyal Tergantung pada kompiler dan nilai dari case. Dalam kompiler yang sempurna, sebuah switch selalu setidaknya secepat jika-lain. Tetapi kompiler tidak sempurna, jadi yang terbaik adalah mencobanya, seperti yang dilakukan John.
Fishinear
52

Saya berpikir tentang saat-saat mengerikan yang saya habiskan dalam kursus Analisis Numerik.

Dan kemudian saya ingat, ada fungsi ini berputar-putar di sekitar 'net dari kode Sumber 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;
}

Yang pada dasarnya menghitung akar kuadrat, menggunakan fungsi perkiraan Newton (tidak ingat nama persisnya).

Itu harus dapat digunakan dan bahkan mungkin lebih cepat, itu dari salah satu permainan perangkat lunak id fenomenal!

Ini ditulis dalam C ++ tetapi seharusnya tidak terlalu sulit untuk menggunakan kembali teknik yang sama di Jawa setelah Anda mendapatkan ide:

Saya awalnya menemukannya di: http://www.codemaestro.com/reviews/9

Metode Newton dijelaskan di wikipedia: http://en.wikipedia.org/wiki/Newton%27s_method

Anda dapat mengikuti tautan untuk penjelasan lebih lanjut tentang cara kerjanya, tetapi jika Anda tidak terlalu peduli, maka inilah kira-kira yang saya ingat dari membaca blog dan dari mengambil kursus Analisis Numerik:

  • pada * (long*) &ydasarnya adalah fungsi convert-to-long yang cepat sehingga operasi integer dapat diterapkan pada byte mentah.
  • yang 0x5f3759df - (i >> 1);garis adalah nilai benih pra-dihitung untuk fungsi pendekatan.
  • yang * (float*) &imengubah nilai kembali ke floating point.
  • yang y = y * ( threehalfs - ( x2 * y * y ) )garis bascially iterates nilai alih fungsi lagi.

Fungsi aproksimasi memberikan nilai yang lebih tepat semakin banyak Anda mengulangi fungsi dibandingkan hasilnya. Dalam kasus Quake, satu iterasi adalah "cukup baik", tetapi jika itu bukan untuk Anda ... maka Anda dapat menambahkan sebanyak iterasi yang Anda butuhkan.

Ini harus lebih cepat karena mengurangi jumlah operasi divisi yang dilakukan dalam rooting naif menjadi pembagian sederhana dengan 2 (sebenarnya * 0.5Foperasi multiply) dan menggantinya dengan beberapa operasi multiplikasi sebagai gantinya.

chakrit
sumber
9
Perlu dicatat bahwa ini mengembalikan 1 / sqrt (angka), bukan sqrt (angka). Saya telah melakukan beberapa pengujian, dan ini gagal dimulai pada n = 410881: rumus ajaib John Carmack mengembalikan 642.00104, ketika akar kuadrat sebenarnya adalah 641.
Kip
11
Anda dapat melihat kertas Chris Lomonts pada akar kuadrat terbalik cepat: lomont.org/Math/Papers/2003/InvSqrt.pdf Ini menggunakan teknik yang sama seperti di sini, tetapi dengan angka ajaib yang berbeda. Makalah ini menjelaskan mengapa angka ajaib dipilih.
4
Selain itu, beyond3d.com/content/articles/8 dan beyond3d.com/content/articles/15 memberi penjelasan tentang asal-usul metode ini. Ini sering dikaitkan dengan John Carmack, tetapi tampaknya kode aslinya (mungkin) ditulis oleh Gary Tarolli, Greg Walsh dan mungkin yang lain.
3
Anda juga tidak bisa mengetik float dan ints di Jawa.
Antimony
10
@Antimony siapa bilang? FloatToIntBits dan IntToFloatBits telah ada sejak java 1.0.2.
corsiKa
38

Saya tidak yakin apakah itu akan lebih cepat, atau bahkan akurat, tetapi Anda dapat menggunakan algoritma Magical Square Root dari John Carmack , untuk memecahkan akar kuadrat lebih cepat. Anda mungkin dapat dengan mudah menguji ini untuk semua kemungkinan integer 32 bit, dan memvalidasi bahwa Anda benar-benar mendapatkan hasil yang benar, karena itu hanya appoximation. Namun, sekarang saya berpikir tentang hal itu, menggunakan ganda hampir sama, jadi saya tidak yakin bagaimana itu akan ikut bermain.

Kibbee
sumber
10
Saya percaya trik Carmack tidak ada gunanya hari ini. Instruksi built-in sqrt jauh lebih cepat daripada biasanya, jadi Anda mungkin lebih baik hanya melakukan root kuadrat biasa dan menguji apakah hasilnya int. Seperti biasa, lakukan benchmark.
jalf
4
Istirahat ini dimulai pada n = 410881, rumus ajaib John Carmack mengembalikan 642.00104, ketika akar kuadrat sebenarnya adalah 641.
Kip
11
Saya baru-baru ini menggunakan trik Carmack dalam permainan Java dan itu sangat efektif, memberikan percepatan sekitar 40%, jadi itu masih berguna, setidaknya di Jawa.
finnw
3
@Robert Fraser Ya + 40% dalam keseluruhan frame rate. Gim ini memiliki sistem fisika partikel yang mengambil hampir semua siklus CPU yang tersedia, didominasi oleh fungsi akar kuadrat dan fungsi bulat-ke-terdekat-bilangan bulat (yang juga telah saya optimalkan menggunakan hack
twiddling yang
5
Tautan rusak.
Pixar
36

Jika Anda melakukan pemotongan biner untuk mencoba menemukan akar kuadrat "benar", Anda dapat dengan mudah mendeteksi jika nilai yang Anda miliki cukup dekat untuk mengatakan:

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

Jadi setelah dihitung n^2, opsinya adalah:

  • n^2 = target: selesai, kembali benar
  • n^2 + 2n + 1 > target > n^2 : Anda dekat, tetapi itu tidak sempurna: return false
  • n^2 - 2n + 1 < target < n^2 : ditto
  • target < n^2 - 2n + 1 : memotong biner di bagian bawah n
  • target > n^2 + 2n + 1 : memotong biner pada yang lebih tinggi n

(Maaf, ini digunakan nsebagai tebakan Anda saat ini, dan targetuntuk parameter. Mohon maaf atas kebingungan!)

Saya tidak tahu apakah ini akan lebih cepat atau tidak, tetapi patut dicoba.

EDIT: Chop biner tidak harus mengambil seluruh jajaran bilangan bulat, (2^x)^2 = 2^(2x)jadi, begitu Anda telah menemukan bit set teratas di target Anda (yang dapat dilakukan dengan trik sedikit-twiddling; saya lupa persis bagaimana) Anda dapat dengan cepat mendapatkan berbagai jawaban potensial. Pikiran Anda, memotong biner naif masih hanya akan memakan waktu hingga 31 atau 32 iterasi.

Jon Skeet
sumber
Uang saya ada pada pendekatan semacam ini. Hindari memanggil sqrt () karena menghitung root kuadrat penuh, dan Anda hanya perlu beberapa digit pertama.
PeterAllenWebb
3
Di sisi lain, jika floating point dilakukan di unit FP khusus, itu mungkin menggunakan semua jenis trik menyenangkan. Saya tidak akan suka bertaruh tanpa benchmark :) (Saya bisa mencobanya malam ini di C #, hanya untuk melihat ...)
Jon Skeet
8
Sqrts perangkat keras sebenarnya cukup cepat hari ini.
Adam Rosenfield
24

Saya menjalankan analisis saya sendiri dari beberapa algoritma di utas ini dan menghasilkan beberapa hasil baru. Anda dapat melihat hasil lama dalam riwayat edit jawaban ini, tetapi hasilnya tidak akurat, karena saya membuat kesalahan, dan membuang-buang waktu menganalisis beberapa algoritma yang tidak dekat. Namun, menarik pelajaran dari beberapa jawaban yang berbeda, saya sekarang memiliki dua algoritma yang menghancurkan "pemenang" utas ini. Inilah hal inti yang saya lakukan berbeda dari orang lain:

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

Namun, baris sederhana ini, yang sebagian besar waktu menambahkan satu atau dua instruksi yang sangat cepat, sangat menyederhanakan switch-casepernyataan menjadi satu jika pernyataan. Namun, ini dapat menambah runtime jika banyak angka yang diuji memiliki kekuatan dua faktor yang signifikan.

Algoritma di bawah ini adalah sebagai berikut:

  • Internet - Jawaban yang diposting Kip
  • Durron - Jawaban saya yang dimodifikasi menggunakan jawaban satu langkah sebagai dasar
  • DurronTwo - Jawaban saya yang dimodifikasi menggunakan jawaban dua-pass (oleh @JohnnyHeggheim), dengan beberapa modifikasi kecil lainnya.

Berikut ini adalah contoh runtime jika angka-angka tersebut dihasilkan menggunakan 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

Dan berikut ini contoh runtime jika dijalankan hanya pada satu juta long pertama:

 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

Seperti yang Anda lihat, DurronTwomelakukan lebih baik untuk input besar, karena bisa menggunakan trik sulap sangat sering, tetapi akan musnah dibandingkan dengan algoritma pertama dan Math.sqrtkarena jumlahnya jauh lebih kecil. Sementara itu, yang lebih simpel Durronadalah pemenang yang sangat besar karena tidak pernah harus membelah sebanyak 4 kali lipat dalam jutaan angka pertama.

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

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

Dan harness benchmark saya: (Membutuhkan 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);
    }
}

UPDATE: Saya telah membuat algoritma baru yang lebih cepat dalam beberapa skenario, lebih lambat dalam skenario lain, saya mendapatkan tolok ukur yang berbeda berdasarkan input yang berbeda. Jika kita menghitung modulo 0xFFFFFF = 3 x 3 x 5 x 7 x 13 x 17 x 241, kita bisa menghilangkan 97,82% dari angka yang tidak bisa kuadrat. Ini dapat (semacam) dilakukan dalam satu baris, dengan 5 operasi bitwise:

if (!goodLookupSquares[(int) ((n & 0xFFFFFFl) + ((n >> 24) & 0xFFFFFFl) + (n >> 48))]) return false;

Indeks yang dihasilkan adalah 1) residu, 2) residu + 0xFFFFFF, atau 3) residu + 0x1FFFFFE. Tentu saja, kita perlu memiliki tabel pencarian untuk residu modulo 0xFFFFFF, yaitu sekitar 3mb file (dalam hal ini disimpan sebagai angka desimal teks ascii, tidak optimal tetapi jelas tidak dapat diperbaiki dengan a ByteBufferdan sebagainya. Tapi karena itu perhitungan awal tidak jadi ' sangat penting. Anda dapat menemukan file di sini (atau menghasilkan sendiri):

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

Saya memuatnya ke dalam booleanarray seperti ini:

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

Contoh runtime. Itu mengalahkan Durron(versi satu) di setiap percobaan saya berlari.

 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
durron597
sumber
3
Tabel pencarian raksasa sepertinya bukan ide yang bagus. Kehilangan cache lebih lambat (~ 100 hingga 150 siklus) daripada instruksi sqrt perangkat keras x86 (~ 20 siklus). Dari segi throughput, Anda dapat mempertahankan banyak kesalahan cache yang luar biasa, tetapi Anda masih mengusir data berguna lainnya. Tabel pencarian besar hanya akan sepadan jika BANYAK lebih cepat daripada opsi lain, dan fungsi ini adalah faktor utama dalam kinerja seluruh program Anda.
Peter Cordes
1
@ SwissFrank: apakah kotak-sempurna memeriksa satu - satunya program Anda? Tabel pencarian dapat terlihat bagus di microbenchmark yang memanggilnya berulang kali dalam loop ketat, tetapi dalam program nyata yang memiliki data lain dalam set kerjanya, itu tidak baik.
Peter Cordes
1
Bitmap 0x1FFFFFE bit membutuhkan 4 mega- byte jika disimpan sebagai bitmap yang dikemas. L3 cache hit pada desktop Intel modern memiliki> 40 siklus latensi, dan lebih buruk pada Xeon besar; lebih lama dari perangkat keras sqrt + mul latency. Jika disimpan sebagai byte -map dengan 1 byte per nilai, sekitar 32 MB; lebih besar dari cache L3 apa pun kecuali Xeon banyak-inti di mana semua inti berbagi satu cache besar. Jadi jika data input Anda memiliki distribusi acak seragam pada rentang input yang cukup besar, Anda akan mendapatkan banyak cache L2 bahkan dalam loop yang ketat. (private per-core L2 pada Intel hanya 256k, dengan ~ 12 siklus latensi.)
Peter Cordes
1
@ SwissFrank: Oh, jika semua yang Anda lakukan adalah memeriksa root, maka ada potensi untuk ini dengan bitmap untuk mendapatkan hit L3. Saya sedang mencari latensi, tetapi banyak kesalahan bisa dalam penerbangan sekaligus, sehingga throughput berpotensi bagus. OTOH, sqrtpsthroughput SIMD atau bahkan sqrtpd(presisi ganda) tidak terlalu buruk pada Skylake, tetapi tidak jauh lebih baik daripada latensi pada CPU lama. Pokoknya 7-cpu.com/cpu/Haswell.html memiliki beberapa nomor percobaan yang bagus, dan halaman untuk CPU lainnya. Panduan mikroarch Agner Fog pdf memiliki beberapa nomor latensi cache untuk Intel dan AMD uarches: agner.org/optimize
Peter Cordes
1
Menggunakan x86 SIMD dari Java adalah masalah, dan saat Anda menambahkan biaya konversi int-> fp dan fp->, masuk akal bahwa bitmap bisa lebih baik. Anda memang membutuhkan doubleketelitian untuk menghindari pembulatan bilangan bulat di luar kisaran + -2 ^ 24 (sehingga bilangan bulat 32-bit bisa berada di luar itu), dan sqrtpdlebih lambat daripada sqrtpsserta hanya memproses setengah elemen sebanyak per elemen (per vektor SIMD) .
Peter Cordes
18

Seharusnya lebih cepat menggunakan metode Newton untuk menghitung Integer Square Root , lalu kuadratkan angka ini dan periksa, seperti yang Anda lakukan dalam solusi Anda saat ini. Metode Newton adalah dasar untuk solusi Carmack yang disebutkan dalam beberapa jawaban lain. Anda harus bisa mendapatkan jawaban yang lebih cepat karena Anda hanya tertarik pada bagian integer dari root, memungkinkan Anda untuk menghentikan algoritma aproksimasi lebih awal.

Pengoptimalan lain yang dapat Anda coba: Jika Digital Root suatu angka tidak berakhir pada 1, 4, 7, atau 9 angka itu bukan kuadrat sempurna. Ini dapat digunakan sebagai cara cepat untuk menghilangkan 60% dari input Anda sebelum menerapkan algoritma root square yang lebih lambat.

Bill the Lizard
sumber
1
Root digital secara komputasional setara dengan modulo, jadi harus dipertimbangkan bersama dengan metode modulo lainnya di sini, seperti mod 16 dan mod 255.
Christian Oudard
1
Apakah Anda yakin root digital setara dengan modulo? Tampaknya ada sesuatu yang sama sekali berbeda seperti yang dijelaskan oleh tautan. Perhatikan daftarnya 1,4,7,9 bukan 1,4,5,9.
Fractaly
1
Akar digital dalam sistem desimal setara dengan menggunakan modulo 9 (well dr (n) = 1 + ((n-1) mod 9); jadi sedikit pergeseran juga). Angka 0,1,4,5,9 untuk modulo 16, dan 0, 1, 4, 7 untuk modulo 9 - yang sesuai dengan 1, 4, 7, 9 untuk root digital.
Hans Olsson
16

Saya ingin fungsi ini bekerja dengan semua bilangan bulat bertanda positif 64-bit

Math.sqrt()bekerja dengan ganda sebagai parameter input, sehingga Anda tidak akan mendapatkan hasil yang akurat untuk bilangan bulat lebih besar dari 2 ^ 53 .

mrzl
sumber
5
Saya telah benar-benar menguji jawaban pada semua kuadrat sempurna yang lebih besar dari 2 ^ 53, serta semua angka dari 5 di bawah setiap kotak sempurna hingga 5 di atas setiap kotak sempurna, dan saya mendapatkan hasil yang benar. (Kesalahan pembulatan dikoreksi ketika saya membulatkan jawaban sqrt ke panjang, lalu kuadratkan nilai itu dan membandingkan)
Kip
2
@ Tip: Saya rasa saya sudah membuktikan bahwa itu berhasil .
maaartinus
Hasilnya tidak sepenuhnya akurat, tetapi lebih akurat dari yang Anda kira. Jika kita mengasumsikan setidaknya 15 digit akurat setelah konversi menjadi dua dan setelah akar kuadrat, maka itu cukup, karena kita membutuhkan tidak lebih dari 11: 10 digit untuk akar kuadrat 32-bit dan kurang dari 1 untuk tempat desimal, karena +0,5 putaran ke terdekat.
mwfearnley
3
Math.sqrt () tidak sepenuhnya akurat, tetapi tidak harus. Di posting pertama, tst adalah bilangan bulat dekat dengan sqrt (N). Jika N bukan kotak, maka tst * tst! = N, tidak peduli berapa nilai tst. Jika N adalah kuadrat sempurna, maka sqrt (N) <2 ^ 32, dan selama sqrt (N) dihitung dengan kesalahan <0,5, kami baik-baik saja.
gnasher729
13

Sebagai catatan, pendekatan lain adalah menggunakan dekomposisi utama. Jika setiap faktor dekomposisi genap, maka angkanya adalah kuadrat sempurna. Jadi yang Anda inginkan adalah melihat apakah suatu angka dapat diuraikan sebagai produk kuadrat bilangan prima. Tentu saja, Anda tidak perlu mendapatkan dekomposisi seperti itu, hanya untuk melihat apakah itu ada.

Pertama-tama buatlah sebuah kotak kuadrat dari bilangan prima yang lebih rendah dari 2 ^ 32. Ini jauh lebih kecil dari tabel semua bilangan bulat hingga batas ini.

Sebuah solusi akan menjadi seperti ini:

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

Saya kira itu agak samar. Apa yang dilakukannya adalah memeriksa di setiap langkah bahwa kuadrat dari bilangan prima membagi nomor input. Jika tidak maka itu membagi angka dengan kuadrat selama mungkin, untuk menghapus kuadrat ini dari dekomposisi utama. Jika dengan proses ini, kita sampai ke 1, maka nomor input adalah dekomposisi kuadrat dari bilangan prima. Jika kuadrat menjadi lebih besar dari angka itu sendiri, maka tidak mungkin kuadrat ini, atau kuadrat yang lebih besar, dapat membaginya, sehingga angka tersebut tidak dapat menjadi dekomposisi kuadrat dari bilangan prima.

Mengingat sqrt saat ini dilakukan dalam perangkat keras dan kebutuhan untuk menghitung bilangan prima di sini, saya kira solusi ini jauh lebih lambat. Tetapi harus memberikan hasil yang lebih baik daripada solusi dengan sqrt yang tidak akan bekerja lebih dari 2 ^ 54, seperti kata mrzl dalam jawabannya.

Cyrille Ka
sumber
1
divisi integer lebih lambat dari FP sqrt pada perangkat keras saat ini. Gagasan ini tidak memiliki peluang. >. <Bahkan pada tahun 2008, sqrtsdthroughput Core2 adalah satu per 6-58c. Ini idivadalah satu per 12-36 sepeda. (latensi mirip dengan throughput: tidak ada unit yang disalin).
Peter Cordes
sqrt tidak harus benar-benar akurat. Itu sebabnya Anda memeriksa dengan integer-mengkuadratkan hasilnya dan melakukan integer-bandingkan untuk memutuskan apakah integer input memiliki sqrt integer yang tepat.
Peter Cordes
11

Telah ditunjukkan bahwa ddigit terakhir dari bujur sangkar sempurna hanya dapat mengambil nilai-nilai tertentu. dDigit terakhir (dalam basis b) dari angka nsama dengan sisa ketika ndibagi dengan bd, yaitu. dalam notasi C n % pow(b, d).

Ini dapat digeneralisasi ke modulus apa pun m, yaitu. n % mdapat digunakan untuk mengesampingkan beberapa persentase angka dari menjadi kuadrat sempurna. Modulus yang Anda gunakan saat ini adalah 64, yang memungkinkan 12, yaitu. 19% dari sisa, kotak mungkin. Dengan sedikit pengkodean saya menemukan modulus 110880, yang memungkinkan hanya 2016, yaitu. 1,8% dari sisa kotak mungkin. Jadi tergantung pada biaya operasi modulus (mis. Divisi) dan pencarian tabel versus akar kuadrat pada mesin Anda, menggunakan modulus ini mungkin lebih cepat.

Omong-omong jika Java memiliki cara untuk menyimpan array bit yang dikemas untuk tabel pencarian, jangan gunakan itu. 110880 kata 32-bit tidak banyak RAM hari ini dan mengambil kata mesin akan lebih cepat daripada mengambil sedikit pun.

Hugh Allen
sumber
Bagus. Apakah Anda menyelesaikan ini secara aljabar atau dengan coba-coba? Saya bisa melihat mengapa ini sangat efektif - banyak tabrakan antara kotak yang sempurna, misalnya 333 ^ 2% 110880 == 3 ^ 2, 334 ^ 2% 110880 == 26 ^ 2, 338 ^ 2% 110880 == 58 ^ 2 .. .
finnw
IIRC itu brute force, tetapi perhatikan bahwa 110880 = 2 ^ 5 * 3 ^ 2 * 5 * 7 * 11, yang menghasilkan 6 * 3 * 2 * 2 * 2 - 1 = 143 pembagi yang tepat.
Hugh Allen
Saya menemukan bahwa karena keterbatasan pencarian, 44352 berfungsi lebih baik, dengan tingkat kelulusan 2,6%. Setidaknya dalam implementasi saya.
Fractaly
1
Divisi integer ( idiv) sama atau lebih buruk dalam biaya untuk FP sqrt ( sqrtsd) pada perangkat keras x86 saat ini. Juga, sama sekali tidak setuju dengan menghindari bitfield. Cache hit rate akan menjadi ton lebih baik dengan bitfield, dan pengujian bit di bitfield hanya satu atau dua instruksi lebih sederhana daripada menguji seluruh byte. (Untuk tabel kecil yang muat dalam cache bahkan sebagai non-bitfields, array byte akan lebih baik, bukan int 32bit. X86 memiliki akses byte tunggal dengan kecepatan yang sama dengan 32bit dword.)
Peter Cordes
11

Masalah bilangan bulat layak mendapatkan solusi bilangan bulat. Jadi

Lakukan pencarian biner pada bilangan bulat (non-negatif) untuk menemukan t bilangan bulat terbesar sehingga t**2 <= n. Kemudian uji apakah r**2 = ntepat. Ini membutuhkan waktu O (log n).

Jika Anda tidak tahu cara mencari biner bilangan bulat positif karena set tidak terikat, itu mudah. Anda mulai dengan menghitung fungsi Anda yang meningkat f (di atas f(t) = t**2 - n) dengan kekuatan dua. Ketika Anda melihatnya berubah positif, Anda telah menemukan batas atas. Kemudian Anda dapat melakukan pencarian biner standar.

Kolonel Panic
sumber
Sebenarnya waktu akan setidaknya O((log n)^2)karena perkalian bukan waktu konstan tetapi sebenarnya memiliki batas yang lebih rendah O(log n), yang menjadi jelas ketika bekerja dengan angka multi-presisi yang besar. Tetapi ruang lingkup wiki ini tampaknya 64-bit, jadi mungkin itu nbd.
10

Penyederhanaan solusi maaartinus berikut ini tampaknya mengurangi beberapa poin persentase dari runtime, tapi saya tidak cukup baik dalam membuat tolok ukur untuk menghasilkan tolok ukur yang dapat saya percayai:

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

Akan bermanfaat untuk memeriksa bagaimana menghilangkan tes pertama,

if (goodMask << x >= 0) return false;

akan mempengaruhi kinerja.

dfeuer
sumber
2
Hasilnya ada di sini . Menghapus tes pertama itu buruk karena memecahkan sebagian besar kasus dengan cukup murah. Sumbernya ada dalam jawaban saya (diperbarui).
maaartinus
9

Untuk kinerja, Anda seringkali harus melakukan beberapa kompromi. Yang lain telah mengungkapkan berbagai metode, namun, Anda mencatat hack Carmack lebih cepat hingga nilai-nilai N. tertentu. Kemudian, Anda harus memeriksa "n" dan jika kurang dari angka N itu, gunakan hack Carmack, atau gunakan beberapa metode lain yang dijelaskan dalam jawaban di sini.

BobbyShaftoe
sumber
Saya telah memasukkan saran Anda ke dalam solusi juga. Juga, pegangan yang bagus. :)
Kip
8

Ini adalah implementasi Java tercepat yang bisa saya buat, menggunakan kombinasi teknik yang disarankan oleh orang lain di utas ini.

  • Tes Mod-256
  • Tes mod-3465 tidak eksak (menghindari pembagian bilangan bulat dengan mengorbankan beberapa positif palsu)
  • Akar kuadrat poin mengambang, bulat dan bandingkan dengan nilai input

Saya juga bereksperimen dengan modifikasi ini tetapi mereka tidak membantu kinerja:

  • Tes mod-255 tambahan
  • Membagi nilai input dengan kekuatan 4
  • Fast Inverse Square Root (untuk mendapatkan nilai N yang tinggi diperlukan 3 iterasi, cukup untuk membuatnya lebih lambat daripada fungsi akar kuadrat perangkat keras.)

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

}
menemukan
sumber
7

Anda harus menyingkirkan bagian 2-daya N sejak awal.

Sunting ke-2 Ekspresi ajaib untuk m di bawah ini seharusnya

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

dan tidak seperti yang tertulis

Akhir dari edit ke-2

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

Edit 1:

Perbaikan kecil:

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

Akhir pengeditan 1

Sekarang lanjutkan seperti biasa. Dengan cara ini, pada saat Anda sampai ke bagian floating point, Anda sudah menyingkirkan semua angka yang bagian 2-kekuatannya ganjil (sekitar setengah), dan kemudian Anda hanya mempertimbangkan 1/8 dari apa yang tersisa. Yaitu Anda menjalankan bagian floating point pada 6% dari angka.

David Lehavi
sumber
7

Project Euler disebutkan dalam tag dan banyak masalah di dalamnya memerlukan memeriksa nomor >> 2^64. Sebagian besar optimasi yang disebutkan di atas tidak bekerja dengan mudah ketika Anda bekerja dengan buffer 80 byte.

Saya menggunakan java BigInteger dan versi yang sedikit dimodifikasi dari metode Newton, yang berfungsi lebih baik dengan bilangan bulat. Masalahnya adalah bahwa kotak yang tepat n^2konvergen (n-1)bukan nkarena n^2-1 = (n-1)(n+1)dan kesalahan terakhir hanya satu langkah di bawah pembagi akhir dan algoritma dihentikan. Mudah untuk memperbaikinya dengan menambahkan satu ke argumen asli sebelum menghitung kesalahan. (Tambahkan dua untuk akar pangkat tiga, dll.)

Salah satu atribut bagus dari algoritma ini adalah Anda dapat segera mengetahui apakah angka tersebut adalah kuadrat sempurna - kesalahan terakhir (bukan koreksi) dalam metode Newton akan menjadi nol. Modifikasi sederhana juga memungkinkan Anda menghitung dengan cepat, floor(sqrt(x))bukan bilangan bulat terdekat. Ini berguna dengan beberapa masalah Euler.

bgiles
sumber
1
Saya memikirkan hal yang sama tentang algoritma ini yang tidak diterjemahkan dengan baik ke buffer multi-presisi. Jadi saya pikir saya akan tetap di sini ... Saya benar-benar menemukan tes kuadrat probabilistik dengan kompleksitas asimptotik yang lebih baik untuk jumlah besar ..... di mana aplikasi teori bilangan tidak jarang menemukan diri mereka sendiri. Tapi tidak familiar dengan Project Euler ... terlihat menarik.
6

Ini pengerjaan ulang dari desimal ke biner dari algoritma kalkulator Marchant lama (maaf, saya tidak punya referensi), di Ruby, diadaptasi khusus untuk pertanyaan ini:

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

Berikut ini adalah hasil dari sesuatu yang serupa (tolong jangan pilih saya untuk gaya pengkodean / bau atau kikuk O / O - itu adalah algoritma yang diperhitungkan, dan C ++ bukan bahasa rumah saya). Dalam hal ini, kami sedang mencari residu == 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;
};
Brent.Longborough
sumber
Jumlah iterasi terlihat O (ln n), di mana n adalah panjang bit dari v, jadi saya ragu ini akan menghemat banyak untuk v yang lebih besar. Floating point sqrt lambat, mungkin 100-200 siklus, tetapi bilangan bulat matematika tidak bebas juga. Selusin iterasi dengan masing-masing 15 siklus, dan itu akan menjadi pembasuhan. Namun, +1 karena menarik.
Tadmas
Sebenarnya, saya percaya penambahan dan pengurangan bisa dilakukan oleh XOR.
Brent.Longborough
Itu adalah komentar bodoh - hanya penambahan yang dapat dilakukan oleh XOR; pengurangannya adalah aritmatika.
Brent.Longborough
1
Apakah benar-benar ada perbedaan substantif antara jangka waktu XOR dan penambahan?
Tadmas
1
@Tadmas: mungkin tidak cukup untuk melanggar aturan "optimalkan nanti". (:-)
Brent.Longborough
6

Panggilan sqrt tidak sepenuhnya akurat, seperti yang telah disebutkan, tetapi menarik dan bermanfaat bahwa itu tidak menerbangkan jawaban lain dalam hal kecepatan. Bagaimanapun, urutan instruksi bahasa rakitan untuk sqrt adalah kecil. Intel memiliki instruksi perangkat keras, yang tidak digunakan oleh Java, saya percaya karena tidak sesuai dengan IEEE.

Jadi mengapa ini lambat? Karena Java sebenarnya memanggil rutin C melalui JNI, dan itu sebenarnya lebih lambat untuk melakukannya daripada memanggil subrutin Java, yang itu sendiri lebih lambat daripada melakukannya secara inline. Ini sangat menjengkelkan, dan Java seharusnya memberikan solusi yang lebih baik, yaitu membangun panggilan pustaka floating point jika perlu. Baiklah.

Dalam C ++, saya menduga semua alternatif kompleks akan kehilangan kecepatan, tapi saya belum memeriksa semuanya. Apa yang saya lakukan, dan apa yang menurut orang Jawa bermanfaat, adalah peretasan sederhana, perpanjangan dari pengujian kasus khusus yang disarankan oleh A. Rex. Gunakan nilai panjang tunggal sebagai array bit, yang tidak dibatasi batasnya. Dengan begitu, Anda memiliki pencarian boolean 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;
}

IsPerfectSquare5 rutin berjalan sekitar 1/3 waktu pada mesin duo core2 saya. Saya menduga bahwa tweak lebih lanjut sepanjang garis yang sama dapat mengurangi waktu rata-rata lebih jauh, tetapi setiap kali Anda memeriksa, Anda menukar lebih banyak pengujian untuk lebih menghilangkan, sehingga Anda tidak bisa pergi terlalu jauh di jalan itu.

Tentu saja, daripada memiliki tes terpisah untuk negatif, Anda dapat memeriksa 6 bit tinggi dengan cara yang sama.

Perhatikan bahwa semua yang saya lakukan adalah menghilangkan kotak yang mungkin, tetapi ketika saya memiliki kasus potensial saya harus memanggil yang asli, isPerfectSquare inline.

Rutin init2 dipanggil sekali untuk menginisialisasi nilai statis pp1 dan pp2. Perhatikan bahwa dalam implementasi saya di C ++, saya menggunakan unsigned lama, jadi sejak Anda masuk, Anda harus menggunakan operator >>>.

Tidak ada kebutuhan intrinsik untuk memeriksa batas array, tetapi pengoptimal Java harus memecahkan masalah ini dengan cepat, jadi saya tidak menyalahkan mereka untuk itu.

hidrodog
sumber
3
Saya yakin Anda salah dua kali. 1. Intel sqrt sesuai dengan IEEE. Satu-satunya instruksi yang tidak sesuai adalah instruksi goniometrik untuk argumen lange. 2. Java menggunakan intrinsik untuk Math.sqrt, bukan JNI .
maaartinus
1
Apakah kamu tidak lupa untuk menggunakan pp2? Saya mengerti bahwa pp1ini digunakan untuk menguji enam bit paling tidak signifikan, tetapi saya tidak percaya bahwa menguji enam bit berikutnya masuk akal.
maaartinus
6

Saya suka ide untuk menggunakan metode yang hampir benar pada beberapa input. Ini adalah versi dengan "offset" yang lebih tinggi. Kode ini sepertinya berfungsi dan lolos dari test case sederhana saya.

Cukup ganti:

if(n < 410881L){...}

kode dengan yang ini:

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);
}
Jonny Heggheim
sumber
6

Mempertimbangkan panjang bit umum (meskipun saya telah menggunakan tipe spesifik di sini), saya mencoba merancang algo sederhana seperti di bawah ini. Diperlukan pemeriksaan sederhana dan jelas untuk 0,1,2 atau <0 pada awalnya. Mengikuti adalah sederhana dalam arti bahwa ia tidak mencoba menggunakan fungsi matematika yang ada. Sebagian besar operator dapat diganti dengan operator bit-wise. Saya belum diuji dengan data tanda bench. Saya bukan ahli dalam matematika atau desain algoritma komputer pada khususnya, saya akan senang melihat Anda menunjukkan masalah. Saya tahu ada banyak peluang peningkatan di sana.

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;  
}
nabam serbang
sumber
@ Tip: Ada masalah dengan browser saya.
nabam serbang
1
Anda perlu indentasi.
Steve Kuo
5

Saya memeriksa semua hasil yang mungkin ketika n bit terakhir dari sebuah persegi diamati. Dengan berturut-turut memeriksa lebih banyak bit, hingga 5/6 input dapat dihilangkan. Saya sebenarnya merancang ini untuk mengimplementasikan algoritma Fermat's Factorization, dan sangat cepat di sana.

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

Bit pseudocode terakhir dapat digunakan untuk memperluas tes untuk menghilangkan lebih banyak nilai. Tes di atas adalah untuk k = 0, 1, 2, 3

  • a is of form (3 << 2k) - 1
  • b adalah dari bentuk (2 << 2k)
  • c adalah dalam bentuk (2 << 2k + 2) - 1
  • d adalah dalam bentuk (2 << 2k - 1) * 10

    Pertama-tama menguji apakah ia memiliki residu kuadrat dengan moduli kekuatan dua, kemudian tes berdasarkan modulus akhir, kemudian menggunakan Math.sqrt untuk melakukan tes akhir. Saya datang dengan ide dari jabatan teratas, dan berusaha memperluasnya. Saya menghargai komentar atau saran.

    Pembaruan: Menggunakan tes dengan modulus, (modSq) dan basis modulus 44352, pengujian saya berjalan di 96% dari waktu yang ada di pembaruan OP untuk angka hingga 1.000.000.000.

    • Fraktal
    sumber
    2

    Ini adalah solusi membagi dan menaklukkan.

    Jika akar kuadrat dari angka alami ( number) adalah angka alami ( solution), Anda dapat dengan mudah menentukan rentang solutionberdasarkan pada jumlah digit dari number:

    • numbermemiliki 1 digit: solutiondalam kisaran = 1 - 4
    • numbermemiliki 2 digit: solutiondalam kisaran = 3 - 10
    • numbermemiliki 3 digit: solutiondalam kisaran = 10 - 40
    • numbermemiliki 4 digit: solutiondalam kisaran = 30 - 100
    • numbermemiliki 5 digit: solutiondalam kisaran = 100 - 400

    Perhatikan pengulangannya?

    Anda dapat menggunakan rentang ini dalam pendekatan pencarian biner untuk melihat apakah ada solutionyang:

    number == solution * solution

    Ini kodenya

    Ini adalah SquareRootChecker kelas saya

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

}

    Dan berikut ini adalah contoh cara menggunakannya.

    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"
    MWB
    sumber
    2
    Saya suka konsepnya, tapi saya ingin dengan sopan menunjukkan kesalahan besar: angka ada di basis 2 biner. Mengonversi basis 2 ke basis 10 melalui toStringadalah operasi yang sangat mahal dibandingkan dengan operator bitwise. Dengan demikian, untuk memenuhi tujuan dari pertanyaan - kinerja - Anda harus menggunakan operator bitwise bukannya string 10 basis. Sekali lagi, saya sangat menyukai konsep Anda. Meskipun demikian, implementasi Anda (seperti saat ini) sejauh ini adalah yang paling lambat dari semua solusi yang mungkin diposting untuk pertanyaan.
    Jack Giffin
    1

    Jika kecepatan menjadi perhatian, mengapa tidak mempartisi set input dan nilai-nilainya yang paling umum digunakan ke tabel pencarian dan kemudian melakukan algoritma sulap yang dioptimalkan untuk kasus luar biasa?

    Elia
    sumber
    Masalahnya adalah bahwa tidak ada "set input yang biasa digunakan" - biasanya saya mengulangi daftar, jadi saya tidak akan menggunakan input yang sama dua kali.
    Kip
    1

    Seharusnya dimungkinkan untuk mengemas 'tidak bisa menjadi kuadrat sempurna jika angka X terakhir adalah N' jauh lebih efisien dari itu! Saya akan menggunakan java 32 bit ints, dan menghasilkan data yang cukup untuk memeriksa 16 bit terakhir dari nomor - itu 2048 nilai int heksadesimal.

    ...

    Baik. Entah saya telah menemukan beberapa teori bilangan yang sedikit di luar saya, atau ada bug dalam kode saya. Bagaimanapun, ini kodenya:

    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("};");
}

    dan inilah hasilnya:

    (ed: elided untuk kinerja buruk di prettify.js; lihat riwayat revisi untuk dilihat.)

    paulmurray
    sumber
    1

    Metode Newton dengan aritmatika integer

    Jika Anda ingin menghindari operasi non-integer, Anda dapat menggunakan metode di bawah ini. Ini pada dasarnya menggunakan Metode Newton yang dimodifikasi untuk integer aritmatika.

    /**
 * Test if the given number is a perfect square.
 * @param n Must be greater than 0 and less
 *    than Long.MAX_VALUE.
 * @return <code>true</code> if n is a perfect
 *    square, or <code>false</code> otherwise.
 */
public static boolean isSquare(long n)
{
    long x1 = n;
    long x2 = 1L;

    while (x1 > x2)
    {
        x1 = (x1 + x2) / 2L;
        x2 = n / x1;
    }

    return x1 == x2 && n % x1 == 0L;
}

    Implementasi ini tidak dapat bersaing dengan solusi yang digunakan Math.sqrt. Namun, kinerjanya dapat ditingkatkan dengan menggunakan mekanisme penyaringan yang dijelaskan dalam beberapa pos lainnya.

    aventurin
    sumber
    1

    Menghitung akar kuadrat dengan metode Newton sangat cepat ... asalkan nilai awalnya masuk akal. Namun tidak ada nilai awal yang masuk akal, dan dalam praktik kami diakhiri dengan perilaku membagi dua dan mencatat (2 ^ 64).
    Agar benar-benar cepat, kita perlu cara cepat untuk mendapatkan nilai awal yang masuk akal, dan itu berarti kita perlu turun ke bahasa mesin. Jika sebuah prosesor memberikan instruksi seperti POPCNT di Pentium, yang menghitung nol terkemuka kita dapat menggunakannya untuk memiliki nilai awal dengan setengah bit signifikan. Dengan hati-hati kita dapat menemukan sejumlah langkah Newton yang pasti akan cukup. (Dengan demikian melepaskan kebutuhan untuk loop dan memiliki eksekusi yang sangat cepat.)

    Solusi kedua akan melalui fasilitas floating point, yang mungkin memiliki perhitungan sqrt cepat (seperti coprocessor i87.) Bahkan perjalanan melalui exp () dan log () mungkin lebih cepat daripada Newton yang terdegenerasi menjadi pencarian biner. Ada aspek rumit untuk ini, analisis tergantung prosesor tentang apa dan jika perbaikan setelahnya diperlukan.

    Solusi ketiga menyelesaikan masalah yang sedikit berbeda, tetapi perlu disebutkan karena situasinya dijelaskan dalam pertanyaan. Jika Anda ingin menghitung banyak akar kuadrat untuk angka-angka yang sedikit berbeda, Anda dapat menggunakan iterasi Newton, jika Anda tidak pernah menginisialisasi ulang nilai awal, tetapi biarkan saja di tempat perhitungan sebelumnya ditinggalkan. Saya telah menggunakan ini dengan sukses dalam setidaknya satu masalah Euler.

    Albert van der Horst
    sumber
    Memperoleh perkiraan yang baik tidak terlalu sulit. Anda dapat menggunakan jumlah digit angka untuk memperkirakan batas bawah dan atas untuk solusi. Lihat juga jawaban saya di mana saya mengusulkan solusi membagi dan menaklukkan.
    MWB
    Apa perbedaan antara POPCNT dan penghitungan jumlah digit? Kecuali Anda dapat melakukan POPCNT dalam satu nanodetik.
    Albert van der Horst
    1

    Akar Kuadrat dari angka, mengingat bahwa angka tersebut adalah kuadrat sempurna.

    Kompleksitasnya adalah log (n)

    /**
 * Calculate square root if the given number is a perfect square.
 * 
 * Approach: Sum of n odd numbers is equals to the square root of n*n, given 
 * that n is a perfect square.
 *
 * @param number
 * @return squareRoot
 */

public static int calculateSquareRoot(int number) {

    int sum=1;
    int count =1;
    int squareRoot=1;
    while(sum<number) {
        count+=2;
        sum+=count;
        squareRoot++;
    }
    return squareRoot;
}
    Sajjad Ali Vayani
    sumber
    0

    Jika Anda menginginkan kecepatan, mengingat bilangan bulat Anda berukuran terbatas, saya menduga bahwa cara tercepat akan melibatkan (a) mempartisi parameter berdasarkan ukuran (misalnya, ke dalam kategori dengan set bit terbesar), kemudian memeriksa nilainya terhadap array kuadrat sempurna. dalam kisaran itu.

    Celestial M Weasel
    sumber
    2
    Ada 2 ^ 32 kotak sempurna dalam kisaran panjang. Tabel ini akan sangat besar. Juga, keuntungan dari komputasi nilai lebih dari akses memori bisa sangat besar.
    PeterAllenWebb
    Oh tidak, tidak ada, ada 2 ^ 16. 2 ^ 32 adalah 2 ^ 16 kuadrat. Ada 2 ^ 16.
    Celestial M Weasel
    3
    ya, tapi rentang panjangnya adalah 64 bit, bukan 32 bit. sqrt (2 ^ 64) = 2 ^ 32. (Saya mengabaikan tanda bit untuk membuat matematika sedikit lebih mudah ... sebenarnya ada (panjang) (2 ^ 31,5) = 3037000499 kotak sempurna)
    Kip
    0

    Mengenai metode Carmac, sepertinya akan cukup mudah hanya untuk mengulangi sekali lagi, yang seharusnya menggandakan jumlah digit akurasi. Bagaimanapun, ini adalah metode berulang yang sangat terpotong - metode Newton, dengan tebakan pertama yang sangat bagus.

    Mengenai yang terbaik saat ini, saya melihat dua optimasi mikro:

    • pindahkan cek vs 0 setelah cek menggunakan mod255
    • mengatur ulang pembagian kekuatan empat untuk melewati semua pemeriksaan untuk kasus biasa (75%).

    Yaitu:

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

    Bahkan yang lebih baik mungkin sederhana

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

    Jelas, akan menarik untuk mengetahui berapa banyak angka yang diambil di setiap pos pemeriksaan - Saya agak ragu bahwa cek benar-benar independen, yang membuat semuanya rumit.

    Ben
    sumber