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


Saya mencari cara tercepat untuk menentukan apakah a long nilai adalah persegi sempurna (yaitu akar kuadratnya adalah bilangan bulat lain):

  1. Saya telah melakukannya dengan cara yang mudah, dengan menggunakan built-in Math.sqrt () berfungsi, tapi aku bertanya-tanya apakah ada cara untuk melakukannya lebih cepat membatasi diri Anda ke domain hanya-integer.
  2. Mempertahankan tabel pencarian bersifat tidak teratur (karena ada sekitar 231,5 bilangan bulat yang persegi kurang dari 263).

Inilah cara yang sangat sederhana dan lugas 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 dalam banyak hal Proyek Euler masalah. Jadi tidak ada orang lain yang harus mempertahankan kode ini. Dan jenis pengoptimalan mikro ini benar-benar dapat 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.


Solusi baru diposting oleh A. Rex telah terbukti lebih cepat. Dalam menjalankan lebih dari 1 miliar bilangan bulat pertama, solusinya hanya membutuhkan 34% dari waktu yang digunakan solusi asli. Sementara hack John Carmack sedikit lebih baik untuk nilai-nilai kecil n, manfaatnya dibandingkan dengan solusi ini cukup kecil.

Berikut ini adalah solusi A. Rex, dikonversi ke Java:

private final static boolean isPerfectSquare(long n)
{
  // Quickfail
  if( n < 0 || ((n&2) != 0) || ((n & 7) == 5) || ((n & 11) == 8) )
    return false;
  if( n == 0 )
    return true;

  // Check mod 255 = 3 * 5 * 17, for fun
  long y = n;
  y = (y & 0xffffffffL) + (y >> 32);
  y = (y & 0xffffL) + (y >> 16);
  y = (y & 0xffL) + ((y >> 8) & 0xffL) + (y >> 16);
  if( bad255[(int)y] )
      return false;

  // Divide out powers of 4 using binary search
  if((n & 0xffffffffL) == 0)
      n >>= 32;
  if((n & 0xffffL) == 0)
      n >>= 16;
  if((n & 0xffL) == 0)
      n >>= 8;
  if((n & 0xfL) == 0)
      n >>= 4;
  if((n & 0x3L) == 0)
      n >>= 2;

  if((n & 0x7L) != 1)
      return false;

  // Compute sqrt using something like Hensel's lemma
  long r, t, z;
  r = start[(int)((n >> 3) & 0x3ffL)];
  do {
    z = n - r * r;
    if( z == 0 )
      return true;
    if( z < 0 )
      return false;
    t = z & (-z);
    r += (z & t) >> 1;
    if( r > (t  >> 1) )
    r = t - r;
  } while( t <= (1L << 33) );
  return false;
}

private static boolean[] bad255 =
{
   false,false,true ,true ,false,true ,true ,true ,true ,false,true ,true ,true ,
   true ,true ,false,false,true ,true ,false,true ,false,true ,true ,true ,false,
   true ,true ,true ,true ,false,true ,true ,true ,false,true ,false,true ,true ,
   true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,false,true ,false,
   true ,true ,true ,false,true ,true ,true ,true ,false,true ,true ,true ,false,
   true ,false,true ,true ,false,false,true ,true ,true ,true ,true ,false,true ,
   true ,true ,true ,false,true ,true ,false,false,true ,true ,true ,true ,true ,
   true ,true ,true ,false,true ,true ,true ,true ,true ,false,true ,true ,true ,
   true ,true ,false,true ,true ,true ,true ,false,true ,true ,true ,false,true ,
   true ,true ,true ,false,false,true ,true ,true ,true ,true ,true ,true ,true ,
   true ,true ,true ,true ,true ,false,false,true ,true ,true ,true ,true ,true ,
   true ,false,false,true ,true ,true ,true ,true ,false,true ,true ,false,true ,
   true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,false,true ,true ,
   false,true ,false,true ,true ,false,true ,true ,true ,true ,true ,true ,true ,
   true ,true ,true ,true ,false,true ,true ,false,true ,true ,true ,true ,true ,
   false,false,true ,true ,true ,true ,true ,true ,true ,false,false,true ,true ,
   true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,false,false,
   true ,true ,true ,true ,false,true ,true ,true ,false,true ,true ,true ,true ,
   false,true ,true ,true ,true ,true ,false,true ,true ,true ,true ,true ,false,
   true ,true ,true ,true ,true ,true ,true ,true ,false,false,true ,true ,false,
   true ,true ,true ,true ,false,true ,true ,true ,true ,true ,false,false,true ,
   true ,false,true ,false,true ,true ,true ,false,true ,true ,true ,true ,false,
   true ,true ,true ,false,true ,false,true ,true ,true ,true ,true ,true ,true ,
   true ,true ,true ,true ,true ,false,true ,false,true ,true ,true ,false,true ,
   true ,true ,true ,false,true ,true ,true ,false,true ,false,true ,true ,false,
   false,true ,true ,true ,true ,true ,false,true ,true ,true ,true ,false,true ,
   true ,false,false,true ,true ,true ,true ,true ,true ,true ,true ,false,true ,
   true ,true ,true ,true ,false,true ,true ,true ,true ,true ,false,true ,true ,
   true ,true ,false,true ,true ,true ,false,true ,true ,true ,true ,false,false,
   true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,
   false,false,true ,true ,true ,true ,true ,true ,true ,false,false,true ,true ,
   true ,true ,true ,false,true ,true ,false,true ,true ,true ,true ,true ,true ,
   true ,true ,true ,true ,true ,false,true ,true ,false,true ,false,true ,true ,
   false,true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,true ,false,
   true ,true ,false,true ,true ,true ,true ,true ,false,false,true ,true ,true ,
   true ,true ,true ,true ,false,false,true ,true ,true ,true ,true ,true ,true ,
   true ,true ,true ,true ,true ,true ,false,false,true ,true ,true ,true ,false,
   true ,true ,true ,false,true ,true ,true ,true ,false,true ,true ,true ,true ,
   true ,false,true ,true ,true ,true ,true ,false,true ,true ,true ,true ,true ,
   true ,true ,true ,false,false
};

private static int[] start =
{
  1,3,1769,5,1937,1741,7,1451,479,157,9,91,945,659,1817,11,
  1983,707,1321,1211,1071,13,1479,405,415,1501,1609,741,15,339,1703,203,
  129,1411,873,1669,17,1715,1145,1835,351,1251,887,1573,975,19,1127,395,
  1855,1981,425,453,1105,653,327,21,287,93,713,1691,1935,301,551,587,
  257,1277,23,763,1903,1075,1799,1877,223,1437,1783,859,1201,621,25,779,
  1727,573,471,1979,815,1293,825,363,159,1315,183,27,241,941,601,971,
  385,131,919,901,273,435,647,1493,95,29,1417,805,719,1261,1177,1163,
  1599,835,1367,315,1361,1933,1977,747,31,1373,1079,1637,1679,1581,1753,1355,
  513,1539,1815,1531,1647,205,505,1109,33,1379,521,1627,1457,1901,1767,1547,
  1471,1853,1833,1349,559,1523,967,1131,97,35,1975,795,497,1875,1191,1739,
  641,1149,1385,133,529,845,1657,725,161,1309,375,37,463,1555,615,1931,
  1343,445,937,1083,1617,883,185,1515,225,1443,1225,869,1423,1235,39,1973,
  769,259,489,1797,1391,1485,1287,341,289,99,1271,1701,1713,915,537,1781,
  1215,963,41,581,303,243,1337,1899,353,1245,329,1563,753,595,1113,1589,
  897,1667,407,635,785,1971,135,43,417,1507,1929,731,207,275,1689,1397,
  1087,1725,855,1851,1873,397,1607,1813,481,163,567,101,1167,45,1831,1205,
  1025,1021,1303,1029,1135,1331,1017,427,545,1181,1033,933,1969,365,1255,1013,
  959,317,1751,187,47,1037,455,1429,609,1571,1463,1765,1009,685,679,821,
  1153,387,1897,1403,1041,691,1927,811,673,227,137,1499,49,1005,103,629,
  831,1091,1449,1477,1967,1677,697,1045,737,1117,1737,667,911,1325,473,437,
  1281,1795,1001,261,879,51,775,1195,801,1635,759,165,1871,1645,1049,245,
  703,1597,553,955,209,1779,1849,661,865,291,841,997,1265,1965,1625,53,
  1409,893,105,1925,1297,589,377,1579,929,1053,1655,1829,305,1811,1895,139,
  575,189,343,709,1711,1139,1095,277,993,1699,55,1435,655,1491,1319,331,
  1537,515,791,507,623,1229,1529,1963,1057,355,1545,603,1615,1171,743,523,
  447,1219,1239,1723,465,499,57,107,1121,989,951,229,1521,851,167,715,
  1665,1923,1687,1157,1553,1869,1415,1749,1185,1763,649,1061,561,531,409,907,
  319,1469,1961,59,1455,141,1209,491,1249,419,1847,1893,399,211,985,1099,
  1793,765,1513,1275,367,1587,263,1365,1313,925,247,1371,1359,109,1561,1291,
  191,61,1065,1605,721,781,1735,875,1377,1827,1353,539,1777,429,1959,1483,
  1921,643,617,389,1809,947,889,981,1441,483,1143,293,817,749,1383,1675,
  63,1347,169,827,1199,1421,583,1259,1505,861,457,1125,143,1069,807,1867,
  2047,2045,279,2043,111,307,2041,597,1569,1891,2039,1957,1103,1389,231,2037,
  65,1341,727,837,977,2035,569,1643,1633,547,439,1307,2033,1709,345,1845,
  1919,637,1175,379,2031,333,903,213,1697,797,1161,475,1073,2029,921,1653,
  193,67,1623,1595,943,1395,1721,2027,1761,1955,1335,357,113,1747,1497,1461,
  1791,771,2025,1285,145,973,249,171,1825,611,265,1189,847,1427,2023,1269,
  321,1475,1577,69,1233,755,1223,1685,1889,733,1865,2021,1807,1107,1447,1077,
  1663,1917,1129,1147,1775,1613,1401,555,1953,2019,631,1243,1329,787,871,885,
  449,1213,681,1733,687,115,71,1301,2017,675,969,411,369,467,295,693,
  1535,509,233,517,401,1843,1543,939,2015,669,1527,421,591,147,281,501,
  577,195,215,699,1489,525,1081,917,1951,2013,73,1253,1551,173,857,309,
  1407,899,663,1915,1519,1203,391,1323,1887,739,1673,2011,1585,493,1433,117,
  705,1603,1111,965,431,1165,1863,533,1823,605,823,1179,625,813,2009,75,
  1279,1789,1559,251,657,563,761,1707,1759,1949,777,347,335,1133,1511,267,
  833,1085,2007,1467,1745,1805,711,149,1695,803,1719,485,1295,1453,935,459,
  1151,381,1641,1413,1263,77,1913,2005,1631,541,119,1317,1841,1773,359,651,
  961,323,1193,197,175,1651,441,235,1567,1885,1481,1947,881,2003,217,843,
  1023,1027,745,1019,913,717,1031,1621,1503,867,1015,1115,79,1683,793,1035,
  1089,1731,297,1861,2001,1011,1593,619,1439,477,585,283,1039,1363,1369,1227,
  895,1661,151,645,1007,1357,121,1237,1375,1821,1911,549,1999,1043,1945,1419,
  1217,957,599,571,81,371,1351,1003,1311,931,311,1381,1137,723,1575,1611,
  767,253,1047,1787,1169,1997,1273,853,1247,413,1289,1883,177,403,999,1803,
  1345,451,1495,1093,1839,269,199,1387,1183,1757,1207,1051,783,83,423,1995,
  639,1155,1943,123,751,1459,1671,469,1119,995,393,219,1743,237,153,1909,
  1473,1859,1705,1339,337,909,953,1771,1055,349,1993,613,1393,557,729,1717,
  511,1533,1257,1541,1425,819,519,85,991,1693,503,1445,433,877,1305,1525,
  1601,829,809,325,1583,1549,1991,1941,927,1059,1097,1819,527,1197,1881,1333,
  383,125,361,891,495,179,633,299,863,285,1399,987,1487,1517,1639,1141,
  1729,579,87,1989,593,1907,839,1557,799,1629,201,155,1649,1837,1063,949,
  255,1283,535,773,1681,461,1785,683,735,1123,1801,677,689,1939,487,757,
  1857,1987,983,443,1327,1267,313,1173,671,221,695,1509,271,1619,89,565,
  127,1405,1431,1659,239,1101,1159,1067,607,1565,905,1755,1231,1299,665,373,
  1985,701,1879,1221,849,627,1465,789,543,1187,1591,923,1905,979,1241,181
};

Saya sudah mencoba solusi berbeda yang disajikan di bawah ini.

  • Setelah pengujian menyeluruh, saya menemukan bahwa menambahkan 0.5 hasil dari Math.sqrt () tidak diperlukan, setidaknya tidak di komputer saya.
  • Itu John Carmack meretas lebih cepat, tetapi memberikan hasil yang salah mulai dari n = 410881. Namun, seperti yang disarankan oleh Bobby Shaftoe, kita bisa menggunakan hack Carmack untuk n <410881.
  • Metode Newton sedikit lebih lambat daripada Math.sqrt(). Ini mungkin karena Math.sqrt() menggunakan sesuatu yang mirip dengan Metode Newton, tetapi diimplementasikan dalam 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 integer yang terlibat, diperlukan beberapa hacks untuk menghindari overflow (saya ingin fungsi ini bekerja dengan semua bilangan bulat 64-bit yang ditandatangani), dan itu masih lebih lambat dari Math.sqrt().
  • Daging biner bahkan lebih lambat. Ini masuk akal karena memotong biner akan rata-rata membutuhkan 16 melewati untuk menemukan akar kuadrat dari nomor 64-bit.

Satu saran yang menunjukkan perbaikan dibuat oleh John D. Cook. Anda dapat mengamati bahwa digit hex terakhir (yaitu 4 bit terakhir) dari persegi sempurna harus 0, 1, 4, atau 9. Ini berarti bahwa 75% dari angka dapat segera dihilangkan sebagai kotak yang mungkin. Menerapkan solusi ini menghasilkan pengurangan sekitar 50% dalam waktu proses.

Bekerja dari saran John, saya menyelidiki properti yang terakhir n bit persegi yang sempurna. Dengan menganalisis 6 bit terakhir, saya menemukan bahwa hanya 12 dari 64 nilai yang mungkin untuk 6 bit terakhir. Ini berarti 81% nilai dapat dihilangkan tanpa menggunakan matematika apa pun. Menerapkan solusi ini memberikan pengurangan 8% tambahan dalam runtime (dibandingkan dengan algoritma asli saya). Menganalisis lebih dari 6 bit menghasilkan daftar kemungkinan bit akhir yang terlalu besar untuk menjadi praktis.

Berikut adalah kode yang saya gunakan, yang berjalan dalam 42% dari waktu yang diperlukan oleh algoritma asli (berdasarkan pada lompatan di atas 100 juta bilangan bulat pertama). Untuk nilai-nilai n kurang dari 410881, ia hanya berjalan 29% dari waktu yang dibutuhkan oleh algoritma asli.

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

  switch((int)(n & 0x3F))
  {
  case 0x00: case 0x01: case 0x04: case 0x09: case 0x10: case 0x11:
  case 0x19: case 0x21: case 0x24: case 0x29: case 0x31: case 0x39:
    long sqrt;
    if(n < 410881L)
    {
      //John Carmack hack, converted to Java.
      // See: http://www.codemaestro.com/reviews/9
      int i;
      float x2, y;

      x2 = n * 0.5F;
      y  = n;
      i  = Float.floatToRawIntBits(y);
      i  = 0x5f3759df - ( i >> 1 );
      y  = Float.intBitsToFloat(i);
      y  = y * ( 1.5F - ( x2 * y * y ) );

      sqrt = (long)(1.0F/y);
    }
    else
    {
      //Carmack hack gives incorrect answer for n >= 410881.
      sqrt = (long)Math.sqrt(n);
    }
    return sqrt*sqrt == n;

  default:
    return false;
  }
}

Catatan:

  • Menurut tes Yohanes, menggunakan or pernyataan lebih cepat dalam C ++ daripada menggunakan switch, tetapi di Jawa dan C # tampaknya tidak ada perbedaan antara or dan switch.
  • Saya juga mencoba membuat tabel pencarian (sebagai array statis privat dengan 64 nilai boolean). Kemudian alih-alih beralih atau or pernyataan, saya hanya akan mengatakan if(lookup[(int)(n&0x3F)]) { test } else return false;. Yang mengejutkan saya, ini (sedikit lebih lambat). Saya tidak yakin mengapa.  Hal ini karena batas array diperiksa di Java.

1209


asal


Jawaban:


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

Pendekatan saya ada tiga:

  1. Pertama, saring jawaban yang jelas. Ini termasuk angka negatif dan melihat 4 bit terakhir. (Saya menemukan melihat enam terakhir tidak membantu.) Saya juga menjawab ya untuk 0. (Dalam membaca kode di bawah ini, perhatikan bahwa masukan 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 modulo square 255 = 3 * 5 * 17. Karena itu adalah produk dari tiga bilangan prima yang berbeda, hanya sekitar 1/8 residu mod 255 adalah kuadrat. Namun, dalam pengalaman saya, memanggil operator modulo (%) lebih mahal daripada manfaat yang didapat, 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 kata, hanya bitwise-dan dan pergeseran.)
    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.
    

602



Saya sangat terlambat ke pesta, tetapi saya berharap dapat memberikan jawaban yang lebih baik; lebih pendek dan (dengan asumsi saya patokan benar) juga banyak 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 waktu yang lama, jadi tidak ada biaya akses array (pengabaian dan pemeriksaan batas). Untuk acak seragam long, ada kemungkinan 81,25% untuk berakhir di sini.

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

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

Tes terakhir kembali lagi double hitung. Sebagai double hanya memiliki 53 bit mantissa, konversi dari long untuk double termasuk pembulatan untuk nilai-nilai besar. Meskipun demikian, tes itu benar (kecuali bukti salah).

Mencoba menggabungkan ide mod255 tidak berhasil.


260



Anda harus melakukan beberapa pembandingan. Algoritme terbaik akan bergantung pada distribusi input Anda.

Algoritme Anda mungkin hampir optimal, tetapi Anda mungkin ingin melakukan pemeriksaan cepat untuk mengesampingkan beberapa kemungkinan sebelum memanggil rutinitas akar kuadrat Anda. Misalnya, lihat digit terakhir nomor Anda dalam heksa dengan melakukan sedikit-bijaksana "dan." Kotak yang sempurna hanya dapat diakhiri dengan 0, 1, 4, atau 9 dalam basis 16, Jadi untuk 75% dari input Anda (dengan asumsi mereka terdistribusi secara merata) Anda dapat menghindari panggilan ke akar kuadrat dalam pertukaran untuk beberapa bit yang sangat cepat berputar.

Kip mengacu pada kode berikut yang mengimplementasikan trik hex. Saat menguji angka 1 hingga 100.000.000, kode ini berjalan 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 #.


118



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

Dan kemudian saya ingat, ada fungsi ini berputar di sekitar 'net from the Quake Source code:

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 aproksimasi Newton (cant ingat nama persisnya).

Ini 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 Java setelah Anda mendapatkan ide:

Awalnya saya 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 ini kira-kira apa yang saya ingat dari membaca blog dan dari mengambil kursus Analisis Numerik:

  • itu * (long*) &y pada dasarnya merupakan fungsi konvert-to-long yang cepat sehingga operasi bilangan bulat dapat diterapkan pada byte mentah.
  • itu 0x5f3759df - (i >> 1); garis adalah nilai benih pra-dihitung untuk fungsi pendekatan.
  • itu * (float*) &i mengkonversi nilai kembali ke floating point.
  • itu y = y * ( threehalfs - ( x2 * y * y ) ) baris pada dasarnya mengulangi nilai melalui fungsi lagi.

Fungsi aproksimasi memberikan nilai yang lebih tepat, semakin Anda mengiterasi fungsi di atas hasil. Dalam kasus Quake, satu iterasi adalah "cukup baik", tetapi jika itu bukan untuk Anda ... maka Anda dapat menambahkan iterasi sebanyak yang Anda butuhkan.

Ini harus lebih cepat karena mengurangi jumlah operasi pembagian yang dilakukan di rooting persegi naive ke pembagian sederhana oleh 2 (sebenarnya * 0.5F mengalikan operasi) dan menggantikannya dengan beberapa operasi perbanyakan tetap sebagai gantinya.


41



Saya tidak yakin apakah itu akan lebih cepat, atau bahkan akurat, tetapi Anda bisa menggunakannya John Magack Square Root dari John Carmack, algoritma untuk menyelesaikan akar kuadrat lebih cepat. Anda mungkin dapat dengan mudah menguji ini untuk semua bilangan bulat 32 bit yang mungkin, dan memvalidasi bahwa Anda benar-benar mendapatkan hasil yang benar, karena itu hanya sebuah appoximation. Namun, sekarang aku memikirkannya, menggunakan doubles juga mendekati, jadi aku tidak yakin bagaimana itu akan berperan.


33



Jika Anda melakukan pemotongan biner untuk menemukan akar kata kunci "benar", Anda dapat dengan mudah mendeteksi apakah nilai yang Anda miliki cukup dekat untuk diceritakan:

(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 tidak sempurna: kembali salah
  • n^2 - 2n + 1 < target < n^2 : idem
  • 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 menggunakan n sebagai tebakan Anda saat ini, dan target untuk parameter. Minta maaf untuk kebingungan!)

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

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


30



Saya menjalankan analisis saya sendiri tentang beberapa algoritme di utas ini dan menghasilkan beberapa hasil baru. Anda dapat melihat hasil-hasil lama dalam riwayat suntingan jawaban ini, tetapi mereka tidak akurat, karena saya membuat kesalahan, dan membuang waktu menganalisis beberapa algoritma yang tidak dekat. Namun, menarik pelajaran dari beberapa jawaban yang berbeda, saya sekarang memiliki dua algoritma yang menghancurkan "pemenang" dari 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, garis sederhana ini, yang sebagian besar waktu menambahkan satu atau dua instruksi yang sangat cepat, sangat menyederhanakan switch-case pernyataan menjadi satu jika pernyataan. Namun, itu dapat menambah runtime jika banyak dari angka yang diuji memiliki faktor kekuatan-dua yang signifikan.

Algoritma di bawah ini adalah sebagai berikut:

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

Berikut ini adalah runtime sampel jika angka-angka yang 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 di sini adalah runtime sampel jika dijalankan pada juta klik pertama saja:

 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, DurronTwo tidak lebih baik untuk input besar, karena menggunakan trik sulap sangat sering, tetapi terhimpit dibandingkan dengan algoritme pertama dan Math.sqrt karena jumlahnya jauh lebih kecil. Sementara itu, yang lebih sederhana Durron adalah pemenang besar karena tidak pernah harus membagi dengan 4 banyak kali dalam satu juta angka pertama.

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

MEMPERBARUI: Saya telah membuat algoritme baru yang lebih cepat dalam beberapa skenario, lebih lambat pada yang lain, saya mendapatkan tolok ukur berbeda berdasarkan masukan yang berbeda. Jika kita menghitung modulo 0xFFFFFF = 3 x 3 x 5 x 7 x 13 x 17 x 241, kita dapat menghilangkan 97,82% dari jumlah yang tidak dapat berbentuk persegi. Ini bisa (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 modulo residu 0xFFFFFF, yaitu sekitar 3mb file (dalam hal ini disimpan sebagai ascii teks angka desimal, tidak optimal tetapi jelas dapat ditingkatkan dengan ByteBuffer Dan seterusnya. Tapi karena itu adalah precalculation, itu tidak begitu penting. Anda dapat menemukan file di sini (atau buat 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 menjadi boolean array 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 waktu proses. 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

21



Itu harus lebih cepat digunakan Metode Newton untuk menghitung Integer Square Root, kemudian sertakan nomor ini dan periksa, seperti yang Anda lakukan dalam solusi Anda saat ini. Metode Newton adalah dasar untuk solusi Carmack yang disebutkan dalam beberapa jawaban lainnya. Anda harus bisa mendapatkan jawaban yang lebih cepat karena Anda hanya tertarik pada bagian integer dari root, memungkinkan Anda untuk menghentikan algoritma aproksimasi lebih cepat.

Pengoptimalan lain yang dapat Anda coba: Jika Akar Digital angka tidak berakhiran 1, 4, 7, atau 9 nomornya tidak persegi yang sempurna. Ini dapat digunakan sebagai cara cepat untuk menghilangkan 60% dari input Anda sebelum menerapkan algoritma akar kuadrat yang lebih lambat.


14



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

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


12