Câu hỏi Cách nhanh nhất để xác định xem căn bậc hai của một số nguyên là một số nguyên


Tôi đang tìm cách nhanh nhất để xác định xem long giá trị là một hình vuông hoàn hảo (nghĩa là căn bậc hai của nó là một số nguyên khác):

  1. Tôi đã thực hiện nó một cách dễ dàng, bằng cách sử dụng Math.sqrt được tích hợp sẵn () nhưng tôi tự hỏi liệu có cách nào để làm nhanh hơn không hạn chế chính bạn thành miền chỉ có số nguyên.
  2. Duy trì bảng tra cứu là không chính xác (vì có khoảng 231,5 số nguyên có hình vuông nhỏ hơn 263).

Đây là cách rất đơn giản và dễ hiểu, tôi đang thực hiện nó ngay bây giờ:

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

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

Lưu ý: Tôi đang sử dụng chức năng này trong nhiều Project Euler các vấn đề. Vì vậy, không ai khác sẽ phải duy trì mã này. Và loại tối ưu hóa vi mô này thực sự có thể tạo ra sự khác biệt, vì một phần của thử thách là thực hiện mọi thuật toán trong chưa đầy một phút và chức năng này sẽ cần được gọi hàng triệu lần trong một số vấn đề.


Một giải pháp mới được đăng bởi A. Rex đã được chứng minh là nhanh hơn. Trong một lần chạy trên 1 tỷ nguyên đầu tiên, giải pháp chỉ yêu cầu 34% thời gian mà giải pháp ban đầu được sử dụng. Trong khi hack John Carmack tốt hơn một chút cho các giá trị nhỏ của n, lợi ích so với giải pháp này là khá nhỏ.

Đây là giải pháp A. Rex, được chuyển đổi sang 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
};

Tôi đã thử các giải pháp khác nhau được trình bày bên dưới.

  • Sau khi thử nghiệm toàn diện, tôi thấy rằng việc thêm 0.5 đến kết quả của Math.sqrt () là không cần thiết, ít nhất là không có trên máy tính của tôi.
  • Các John Carmack hack đã nhanh hơn, nhưng nó đã cho kết quả không chính xác bắt đầu từ n = 410881. Tuy nhiên, theo đề xuất của BobbyShaftoe, chúng ta có thể sử dụng bản hack Carmack cho n <410881.
  • Phương pháp của Newton chậm hơn một chút so với Math.sqrt(). Điều này có lẽ vì Math.sqrt() sử dụng một cái gì đó tương tự như phương pháp Newton, nhưng thực hiện trong phần cứng vì vậy nó nhanh hơn nhiều so với trong Java. Ngoài ra, phương pháp Newton vẫn yêu cầu sử dụng tăng gấp đôi.
  • Một phương pháp Newton đã sửa đổi, sử dụng một vài thủ thuật để chỉ có toán số nguyên, yêu cầu một số hacks để tránh tràn (tôi muốn hàm này hoạt động với tất cả các số nguyên 64 bit tích cực) và nó vẫn chậm hơn Math.sqrt().
  • Nhị phân nhị phân thậm chí còn chậm hơn. Điều này có ý nghĩa bởi vì các nhị phân chặt trung bình sẽ yêu cầu 16 đi để tìm căn bậc hai của một số 64-bit.

Đề xuất một trong đó đã cho thấy những cải tiến đã được thực hiện bởi John D. Cook. Bạn có thể quan sát rằng chữ số hex cuối cùng (tức là 4 bit cuối cùng) của một hình vuông hoàn hảo phải là 0, 1, 4 hoặc 9. Điều này có nghĩa là 75% số có thể được loại bỏ ngay lập tức dưới dạng hình vuông có thể. Việc triển khai giải pháp này dẫn đến giảm 50% thời gian chạy.

Làm việc theo gợi ý của John, tôi đã nghiên cứu các đặc tính của n bit của một hình vuông hoàn hảo. Bằng cách phân tích 6 bit cuối cùng, tôi thấy rằng chỉ có 12 trong số 64 giá trị có thể cho 6 bit cuối cùng. Điều này có nghĩa là 81% giá trị có thể được loại bỏ mà không sử dụng bất kỳ phép toán nào. Việc triển khai giải pháp này đã giảm thêm 8% thời gian chạy (so với thuật toán ban đầu của tôi). Phân tích nhiều hơn 6 bit dẫn đến một danh sách các bit kết thúc có thể quá lớn để thực tế.

Đây là mã mà tôi đã sử dụng, chạy trong 42% thời gian theo yêu cầu của thuật toán gốc (dựa trên chạy trên 100 triệu số nguyên đầu tiên). Đối với các giá trị của n ít hơn 410881, nó chỉ chạy trong 29% thời gian theo yêu cầu của thuật toán gốc.

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

Ghi chú:

  • Theo các bài kiểm tra của John, sử dụng or báo cáo nhanh hơn trong C ++ so với sử dụng switch, nhưng trong Java và C # dường như không có sự khác biệt giữa or và switch.
  • Tôi cũng đã cố gắng thực hiện một bảng tra cứu (như là một mảng tĩnh riêng của 64 giá trị boolean). Sau đó, thay vì chuyển đổi hoặc or tuyên bố, tôi sẽ nói if(lookup[(int)(n&0x3F)]) { test } else return false;. Trước sự ngạc nhiên của tôi, đây là (hơi chậm). Tôi cung không chăc tại sao.  Điều này là bởi vì các giới hạn mảng được kiểm tra trong Java.

1210


gốc


Đây là mã Java, trong đó int == 32 bit và dài == 64 bit, và cả hai đều được ký. - Kip
@ Shreevasta: Tôi đã thực hiện một số thử nghiệm trên các giá trị lớn (lớn hơn 2 ^ 53), và phương pháp của bạn cho một số dương tính giả. Người đầu tiên gặp phải là n = 9007199326062755, không phải là một hình vuông hoàn hảo nhưng được trả lại là một. - Kip
Xin đừng gọi nó là "John Carmack hack." Anh ta không nghĩ ra nó. - user9282
@mamama - Có lẽ, nhưng nó là do anh ta. Henry Ford đã không phát minh ra chiếc xe, Wright Bros. đã không phát minh ra chiếc máy bay, và Galleleo không phải là người đầu tiên tìm ra Trái Đất xoay quanh mặt trời ... thế giới được tạo thành từ những phát minh bị đánh cắp (và yêu). - Robert Fraser
Bạn có thể nhận được một sự gia tăng tốc độ nhỏ trong 'quickfail' bằng cách sử dụng một cái gì đó như ((1<<(n&15))|65004) != 0, thay vì có ba kiểm tra riêng biệt. - Nabb


Các câu trả lời:


Tôi đã tìm ra một phương thức hoạt động nhanh hơn 35% so với mã 6bits + Carmack + sqrt của bạn, ít nhất là với CPU (x86) và ngôn ngữ lập trình (C / C ++) của tôi. Kết quả của bạn có thể thay đổi, đặc biệt là bởi vì tôi không biết làm thế nào các yếu tố Java sẽ diễn ra.

Cách tiếp cận của tôi là gấp ba lần:

  1. Đầu tiên, lọc ra câu trả lời rõ ràng. Điều này bao gồm các số âm và xem 4 bit cuối cùng. (Tôi thấy sáu người cuối cùng không giúp được gì.) Tôi cũng trả lời có cho 0. (Đọc đoạn mã dưới đây, lưu ý rằng đầu vào của tôi là int64 x.)
    if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) )
        return false;
    if( x == 0 )
        return true;
  2. Tiếp theo, kiểm tra nếu nó là một modulo vuông 255 = 3 * 5 * 17. Bởi vì đó là một sản phẩm của ba số nguyên tố riêng biệt, chỉ có khoảng 1/8 của dư lượng mod 255 là hình vuông. Tuy nhiên, theo kinh nghiệm của tôi, việc gọi toán tử modulo (%) tốn nhiều hơn lợi ích của nó, vì vậy tôi sử dụng các thủ thuật bit liên quan đến 255 = 2 ^ 8-1 để tính toán dư lượng. (Đối với tốt hơn hoặc tệ hơn, tôi không sử dụng mẹo đọc từng byte riêng lẻ, chỉ theo bitwise và ca.)
    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



Wow! Tôi sẽ cố gắng chuyển đổi nó sang Java và thực hiện so sánh, cũng như kiểm tra độ chính xác về kết quả. Tôi sẽ cho bạn biết những gì tôi tìm thấy. - Kip
Wow, cái này thật đẹp. Tôi đã nhìn thấy Hensel nâng trước (tính toán rễ của đa thức modulo một nguyên tố) nhưng tôi thậm chí đã không nhận ra bổ đề có thể được cẩn thận hạ xuống tất cả các cách để tính toán căn bậc hai của số; đây là ... nâng cao :) - ShreevatsaR
@nightcracker Nó không. 9 < 0 => false, 9&2 => 0, 9&7 == 5 => false, 9&11 == 8 => false. - primo
Maartinus đăng một giải pháp nhanh hơn 2x (và ngắn hơn nhiều) xuống dưới, một chút sau đó, điều đó dường như không nhận được nhiều tình yêu. - Jason C
Có vẻ như rất nhiều lợi thế về tốc độ trong các giải pháp khác nhau là thu được bằng cách lọc ra các ô vuông rõ ràng. Có ai đánh giá tình hình lọc ra thông qua giải pháp của Maartinus và sau đó chỉ sử dụng chức năng sqrt vì đó là một chức năng tích hợp? - user1914292


Tôi khá muộn với bữa tiệc, nhưng tôi hy vọng sẽ cung cấp một câu trả lời tốt hơn; ngắn hơn và (giả sử của tôi điểm chuẩn là chính xác) cũng nhiều nhanh hơn.

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

Thử nghiệm đầu tiên bắt hầu hết các hình vuông không nhanh. Nó sử dụng một bảng 64-mục đóng gói trong một thời gian dài, do đó, không có chi phí truy cập mảng (kiểm tra hướng dẫn và giới hạn). Đối với một ngẫu nhiên thống nhất long, có khả năng kết thúc ở đây là 81,25%.

Bài kiểm tra thứ hai bắt tất cả các con số có số lượng twos lẻ trong hệ số của chúng. Phương pháp Long.numberOfTrailingZeros là rất nhanh vì nó được JIT-ed thành một hướng dẫn đơn i86.

Sau khi giảm các số 0 theo sau, phép thử thứ ba xử lý các số kết thúc bằng 011, 101 hoặc 111 ở dạng nhị phân, không phải là các ô vuông hoàn hảo. Nó cũng quan tâm đến số âm và cũng xử lý 0.

Thử nghiệm cuối cùng rơi trở lại double số học. Như double chỉ có 53 bit mantissa, chuyển đổi từ long đến double bao gồm làm tròn cho các giá trị lớn. Tuy nhiên, thử nghiệm là chính xác (trừ khi bằng chứng là sai).

Cố gắng kết hợp ý tưởng mod255 không thành công.


262



Đó là mặt nạ tiềm ẩn của giá trị thay đổi là một chút ... ác. Bạn có bất kỳ ý tưởng tại sao đó là trong spec Java? - dfeuer
Một câu hỏi về mã của bạn nói riêng: tại sao bạn cần phải kiểm tra xem một số lẻ có kết thúc không 001? Đó không phải là do goodMask kiểm tra? - dfeuer
@dfeuer Tôi đoán có hai lý do: 1. Chuyển bằng nhiều hơn không có ý nghĩa gì cả. 2. Nó giống như các công trình HW và bất cứ ai sử dụng các hoạt động bitwise là quan tâm đến hiệu suất, do đó, làm bất cứ điều gì khác sẽ là sai. - - Các goodMask thử nghiệm, nhưng nó trước sự thay đổi đúng. Vì vậy, bạn sẽ phải lặp lại nó, nhưng theo cách này thì nó đơn giản hơn và AFAIK nhanh hơn và tốt hơn một chút. - maaartinus
@Sebastian A có thể là thử nghiệm tốt hơn: if ((x & (7 | Integer.MIN_VALUE)) != 1) return x == 0;. - maaartinus
"Như đôi đã chỉ 56 bit mantissa" -> Tôi sẽ nói nó có nhiều khả năng có một 53 bitmột. Cũng thế - chux


Bạn sẽ phải làm một số điểm chuẩn. Thuật toán tốt nhất sẽ phụ thuộc vào việc phân phối các yếu tố đầu vào của bạn.

Thuật toán của bạn có thể gần như tối ưu, nhưng bạn có thể muốn thực hiện kiểm tra nhanh để loại bỏ một số khả năng trước khi gọi thủ tục căn bậc hai của bạn. Ví dụ, hãy nhìn vào chữ số cuối cùng của số của bạn trong hex bằng cách làm một chút khôn ngoan "và". Hình vuông hoàn hảo chỉ có thể kết thúc bằng 0, 1, 4, hoặc 9 trong cơ sở 16, Vì vậy, với 75% đầu vào của bạn (giả sử chúng được phân bố đồng đều), bạn có thể tránh cuộc gọi đến căn bậc hai để đổi lấy một số bit rất nhanh.

Kip benchmarked mã sau đây thực hiện lừa hex. Khi kiểm tra các con số từ 1 đến 100.000.000, mã này chạy nhanh gấp hai lần so với bản gốc.

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

Khi tôi kiểm tra mã tương tự trong C ++, nó thực sự chạy chậm hơn so với bản gốc. Tuy nhiên, khi tôi loại bỏ câu lệnh switch, thủ thuật hex lại một lần nữa làm cho mã nhanh gấp hai lần.

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

Loại bỏ các tuyên bố chuyển đổi có ít ảnh hưởng đến mã C #.


118



khá thông minh ... sẽ không nghĩ đến điều đó - warren
Nice điểm về các bit trailing. Tôi sẽ cố gắng kết hợp thử nghiệm đó với một số nhận xét khác ở đây. - PeterAllenWebb
Tôi đã đánh giá nó cho 100 triệu số nguyên đầu tiên .. khoảng chừng một nửa thời gian cần thiết. - Kip
Giải pháp tuyệt vời. Tự hỏi làm thế nào bạn đến với nó? Là một nguyên tắc khá thành lập hay chỉ là một cái gì đó bạn đã tìm ra? : D - Jeel Shah
@ LarsH Không cần phải thêm 0,5, xem giải pháp của tôi cho một liên kết đến bằng chứng. - maaartinus


Tôi đã suy nghĩ về những lần khủng khiếp mà tôi đã trải qua trong khóa học Phân tích số.

Và sau đó tôi nhớ, có chức năng này vòng quanh 'net từ mã nguồn 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;
}

Mà về cơ bản tính toán một căn bậc hai, sử dụng hàm xấp xỉ của Newton (không thể nhớ tên chính xác).

Nó có thể sử dụng được và thậm chí có thể nhanh hơn, nó là từ một trong những trò chơi phần mềm id hiện tượng!

Nó được viết bằng C ++ nhưng không quá khó để sử dụng lại cùng một kỹ thuật trong Java khi bạn nhận được ý tưởng:

Ban đầu tôi tìm thấy nó tại: http://www.codemaestro.com/reviews/9

Phương pháp của Newton được giải thích tại wikipedia: http://en.wikipedia.org/wiki/Newton%27s_method

Bạn có thể theo liên kết để giải thích thêm về cách nó hoạt động, nhưng nếu bạn không quan tâm nhiều, thì đây là những gì tôi nhớ từ việc đọc blog và từ tham gia khóa học Phân tích số:

  • các * (long*) &y về cơ bản là một hàm chuyển đổi nhanh thành dài nên các phép toán số nguyên có thể được áp dụng trên các byte thô.
  • các 0x5f3759df - (i >> 1); line là một giá trị hạt giống được tính toán trước cho hàm gần đúng.
  • các * (float*) &i chuyển đổi giá trị trở lại điểm nổi.
  • các y = y * ( threehalfs - ( x2 * y * y ) ) dòng bascially lặp lại giá trị trên hàm một lần nữa.

Hàm gần đúng cung cấp cho các giá trị chính xác hơn, bạn càng lặp lại hàm trên kết quả. Trong trường hợp của Quake, một lần lặp lại là "đủ tốt", nhưng nếu nó không dành cho bạn ... thì bạn có thể thêm nhiều lần lặp lại nếu cần.

Điều này sẽ nhanh hơn bởi vì nó làm giảm số hoạt động phân chia được thực hiện trong rễ vuông ngây thơ xuống đến một phân chia đơn giản bằng 2 (thực sự là một * 0.5F nhân hoạt động) và thay thế nó bằng một số hoạt động nhân giống cố định thay thế.


41



Cần lưu ý rằng điều này trả về 1 / sqrt (số), không phải sqrt (số). Tôi đã thực hiện một số thử nghiệm, và điều này không thành công bắt đầu từ n = 410881: công thức ma thuật John Carmack trả về 642.00104, khi căn bậc hai thực tế là 641. - Kip
Bạn có thể nhìn vào giấy Chris Lomonts trên rễ vuông nghịch đảo nhanh: lomont.org/Math/Papers/2003/InvSqrt.pdf Nó sử dụng kỹ thuật tương tự như ở đây, nhưng với một số phép thuật khác. Bài báo giải thích tại sao số ma thuật được chọn. - Dan
Cũng thế, beyond3d.com/content/articles/8 và beyond3d.com/content/articles/15 làm sáng tỏ nguồn gốc của phương pháp này. Nó thường được quy cho John Carmack, nhưng có vẻ như mã ban đầu là (có thể) được viết bởi Gary Tarolli, Greg Walsh và có lẽ là những người khác. - Dan
Ngoài ra, bạn không thể gõ vào các float và int trong Java. - Antimony
@Antimony ai nói? FloatToIntBits và IntToFloatBits đã có từ java 1.0.2. - corsiKa


Tôi không chắc liệu nó có nhanh hơn hay thậm chí chính xác, nhưng bạn có thể sử dụng Root Square huyền bí của John Carmack, thuật toán để giải quyết căn bậc hai nhanh hơn. Bạn có thể dễ dàng kiểm tra điều này cho tất cả các số nguyên 32 bit có thể, và xác nhận rằng bạn thực sự có kết quả chính xác, vì nó chỉ là một sự phỏng đoán. Tuy nhiên, bây giờ tôi nghĩ về nó, bằng cách sử dụng đôi là xấp xỉ cũng có, vì vậy tôi không chắc chắn như thế nào mà sẽ đi vào chơi.


33



1 cho tham chiếu groack groovy! - Mitch Wheat
Tôi tin rằng mẹo của Carmack là khá vô nghĩa trong những ngày này. Hướng dẫn sqrt dựng sẵn nhanh hơn rất nhiều so với trước đây, vì vậy bạn có thể làm tốt hơn việc thực hiện một căn bậc hai bình thường và thử nghiệm nếu kết quả là một int. Như mọi khi, điểm chuẩn nó. - jalf
Điều này phá vỡ bắt đầu từ n = 410881, công thức ma thuật John Carmack trả về 642.00104, khi căn bậc hai thực tế là 641. - Kip
Gần đây tôi đã sử dụng mẹo của Carmack trong một trò chơi Java và nó rất hiệu quả, tăng tốc khoảng 40%, vì vậy nó vẫn hữu ích, ít nhất là trong Java. - finnw
@Robert Fraser Có + 40% trong tỷ lệ khung hình chung. Trò chơi có một hệ thống vật lý hạt chiếm gần như tất cả các chu kỳ CPU có sẵn, bị chi phối bởi hàm gốc hình vuông và hàm số nguyên từ gần đến số nguyên (mà tôi cũng đã tối ưu hóa bằng cách sử dụng một số bit tương tự.) - finnw


Nếu bạn thực hiện một băm nhị phân để cố gắng tìm căn bậc hai "đúng", bạn có thể dễ dàng phát hiện nếu giá trị bạn có đủ gần để nói:

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

Vì vậy, có tính toán n^2, các tùy chọn là:

  • n^2 = target: xong, trả lại đúng
  • n^2 + 2n + 1 > target > n^2 : bạn thân thiết, nhưng nó không hoàn hảo: trả về false
  • n^2 - 2n + 1 < target < n^2 : ditto
  • target < n^2 - 2n + 1 : nhị phân chặt trên thấp hơn n
  • target > n^2 + 2n + 1 : nhị phân chặt trên cao hơn n

(Xin lỗi, việc sử dụng này n như dự đoán hiện tại của bạn và target cho tham số. Xin lỗi vì sự nhầm lẫn!)

Tôi không biết liệu điều này có nhanh hơn hay không, nhưng đáng để thử.

EDIT: Các nhị phân chop không phải mất trong phạm vi toàn bộ các số nguyên, hoặc là (2^x)^2 = 2^(2x), vì vậy khi bạn đã tìm thấy bit thiết lập hàng đầu trong mục tiêu của mình (có thể được thực hiện bằng mẹo nhỏ đôi chút), tôi quên chính xác cách thức) bạn có thể nhanh chóng nhận được một loạt các câu trả lời tiềm năng. Tâm trí bạn, một băm nhị phân ngây thơ vẫn chỉ mất đến 31 hoặc 32 lần lặp.


30



Tiền của tôi là theo cách tiếp cận này. Tránh gọi sqrt () vì nó đang tính toán một căn bậc hai đầy đủ, và bạn chỉ cần vài chữ số đầu tiên. - PeterAllenWebb
Mặt khác, nếu điểm nổi đang được thực hiện trong một đơn vị FP chuyên dụng, nó có thể sử dụng tất cả các loại thủ thuật thú vị. Tôi không muốn đặt cược vào nó mà không có một điểm chuẩn :) (Tôi có thể thử nó tối nay mặc dù trong C #, chỉ để xem ...) - Jon Skeet
Phần cứng sqrts thực sự là khá nhanh những ngày này. - Adam Rosenfield


Tôi chạy phân tích của riêng tôi về một số thuật toán trong chuỗi này và đã đưa ra một số kết quả mới. Bạn có thể thấy những kết quả cũ trong lịch sử chỉnh sửa của câu trả lời này, nhưng chúng không chính xác, vì tôi đã phạm sai lầm và lãng phí thời gian phân tích một số thuật toán không gần. Tuy nhiên, kéo bài học từ một số câu trả lời khác nhau, bây giờ tôi có hai thuật toán đè bẹp "người chiến thắng" của chủ đề này. Đây là điều cốt lõi tôi làm khác với mọi người khác:

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

Tuy nhiên, dòng đơn giản này, phần lớn thời gian thêm một hoặc hai hướng dẫn rất nhanh, rất đơn giản hóa switch-case tuyên bố thành một câu lệnh if. Tuy nhiên, nó có thể thêm vào thời gian chạy nếu nhiều trong số các con số được thử nghiệm có các nhân tố có sức mạnh đáng kể.

Các thuật toán dưới đây như sau:

  • Internet - Câu trả lời được đăng của Kip
  • Durron - Câu trả lời đã sửa đổi của tôi bằng câu trả lời một lần làm cơ sở
  • DurronTwo - Câu trả lời đã sửa đổi của tôi bằng câu trả lời hai câu (bởi @JohnnyHeggheim), với một số sửa đổi nhỏ khác.

Đây là thời gian chạy mẫu nếu các số được tạo bằng 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

Và đây là thời gian chạy mẫu nếu nó chỉ chạy trên một triệu lần đầu tiên:

 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

Bạn có thể thấy, DurronTwo làm tốt hơn cho đầu vào lớn, bởi vì nó được sử dụng ma thuật lừa rất thường xuyên, nhưng được clobbered so với các thuật toán đầu tiên và Math.sqrt bởi vì các con số nhỏ hơn rất nhiều. Trong khi đó, đơn giản hơn Durron là một người chiến thắng lớn bởi vì nó không bao giờ phải chia cho 4 nhiều lần trong số triệu đầu tiên.

Đây là 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;
}

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

Và khai thác chuẩn của tôi: (Yêu cầu 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);
    }
}

CẬP NHẬT: Tôi đã thực hiện một thuật toán mới nhanh hơn trong một số kịch bản, chậm hơn trong các trường hợp khác, tôi đã nhận được các điểm chuẩn khác nhau dựa trên các yếu tố đầu vào khác nhau. Nếu chúng ta tính toán modulo 0xFFFFFF = 3 x 3 x 5 x 7 x 13 x 17 x 241, chúng tôi có thể loại bỏ 97,82% số không thể là hình vuông. Đây có thể là (loại) được thực hiện trong một dòng, với 5 hoạt động bitwise:

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

Chỉ số kết quả là 1) dư lượng, 2) dư lượng + 0xFFFFFF, hoặc 3) dư lượng + 0x1FFFFFE. Tất nhiên, chúng ta cần có một bảng tra cứu dư lượng modulo 0xFFFFFF, đó là khoảng một tệp 3mb (trong trường hợp này được lưu trữ dưới dạng số thập phân văn bản ascii, không tối ưu nhưng rõ ràng có thể thay thế bằng một ByteBuffer và kể từ đó trở đi. Nhưng vì đó là precalculation nó không quan trọng quá nhiều. Bạn có thể tìm thấy tệp ở đây (hoặc tự tạo):

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

Tôi tải nó vào một boolean mảng như thế này:

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

Thời gian chạy ví dụ. Nó đánh bại Durron (phiên bản một) trong mọi thử nghiệm tôi chạy.

 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



Một bảng tra cứu khổng lồ dường như không phải là một ý tưởng hay. Lỗi bộ nhớ cache chậm hơn (~ 100 đến 150 chu kỳ) so với lệnh sqrt phần cứng x86 (~ 20 chu kỳ). Thông lượng-khôn ngoan, bạn có thể duy trì rất nhiều bộ nhớ cache nổi bật-bỏ lỡ, nhưng bạn vẫn đang đuổi các dữ liệu hữu ích khác. Một bảng tra cứu lớn sẽ chỉ có giá trị nếu nó là một LOT nhanh hơn bất kỳ tùy chọn khác, và chức năng này là yếu tố chính trong việc thực hiện toàn bộ chương trình của bạn. - Peter Cordes