Найшвидший спосіб визначити, чи є цілочисельний квадратний корінь цілим числом

Я шукаю найшвидший спосіб визначити, чи є long значення ідеальним квадратом (тобто його квадратний корінь є іншим цілим числом):

  1. Я зробив це простим способом, використовуючи вбудовану Math.sqrt() , але мені цікаво, чи є спосіб зробити це швидше, обмеживши себе тільки целочисленной областю.
  2. Ведення довідкової таблиці недоцільно (оскільки існує близько 2 31,5 цілих чисел, площа яких менше 2 63).

Ось дуже простий і зрозумілий спосіб зробити це зараз:

 public final static boolean isPerfectSquare(long n) { if (n < 0) return false; long tst = (long)(Math.sqrt(n) + 0.5); return tst*tst == n; } 

Примітка: я використовую цю функцію в багатьох задачах Project Euler . Так що більше нікому не доведеться підтримувати цей код. І цей вид мікрооптімізаціі може реально змінити ситуацію, оскільки одне із завдань полягає в тому, щоб виконати кожен алгоритм менш ніж за хвилину, і в деяких завданнях цю функцію доведеться викликати мільйони разів.


Я пробував різні рішення проблеми:

  • Після вичерпного тестування я виявив, що додавання 0.5 до результату Math.sqrt () не потрібно, принаймні, на моїй машині.
  • Швидкий зворотний квадратний корінь був швидше, але він дав неправильні результати для n> = 410881. Однак, як припускає БоббіШафто , ми можемо використовувати хак FISR для n <410881.
  • Метод Ньютона був трохи повільніше, ніж Math.sqrt() . Ймовірно, це пов'язано з Math.sqrt() що Math.sqrt() використовує щось схоже на метод Ньютона, але реалізовано в обладнанні, тому воно набагато швидше, ніж в Java. Крім того, метод Ньютона все ще вимагав використання подвійних чисел.
  • Модифікований метод Ньютона, який використовував кілька прийомів так, щоб була задіяна тільки целочисленная математика, зажадав деяких хаков, щоб уникнути переповнення (я хочу, щоб ця функція працювала з усіма позитивними 64-бітними цілими числами зі Math.sqrt() ), і він все ще був повільніше, ніж Math.sqrt() .
  • Бінарна відбивна була ще повільніше. Це має сенс, тому що двійковій відбитті в середньому потрібно 16 проходів, щоб знайти квадратний корінь 64-бітного числа.
  • Згідно з тестами Джона, використання or операторів в C ++ швидше, ніж використання switch , але в Java і С #, схоже, немає різниці між or і switch .
  • Я також спробував створити таблицю пошуку (як приватний статичний масив з 64 логічних значень). Тоді замість параметра switch або or я просто сказав if(lookup[(int)(n { test } else return false; , На мій подив, це було (трохи) повільніше. Це тому, що межі масиву перевіряються в Java .
1306
17 нояб. заданий Kip 17 нояб. 2008-11-17 16:43 '08 о 16:43 2008-11-17 16:43
@ 35 відповідей
  • 1
  • 2

Я з'ясував метод, який працює на 35% швидше, ніж ваш код 6bits + Carmack + sqrt, по крайней мере, з моїм процесором (x86) і мовою програмування (C / С ++). Ваші результати можуть відрізнятися, особливо тому, що я не знаю, як буде грати Java-фактор.

Мій підхід тричі:

  • Спочатку отфильтруйте очевидні відповіді. Це включає негативні числа і перегляд останніх 4 біт. (Я знайшов, що дивитися на останні шість не допомогло.) Я також відповідаю так за 0. (Читаючи наведений нижче код, зверніть увагу, що мій введення int64 x .)
     if( x < 0 || (x || ((x  7) == 5) || ((x  11) == 8) ) return false; if( x == 0 ) return true; 
  • Потім перевірте, чи є це квадратом за модулем 255 = 3 * 5 * 17. Так як твір трьох різних простих чисел, тільки близько 1/8 залишків mod 255 є квадратами. Однак, з мого досвіду, виклик оператора modulo (%) коштує дорожче, ніж виграш, тому я використовую бітові трюки з 255 = 2 ^ 8-1 для обчислення залишку. (До кращого або гіршого, я не використовую трюк, щоб читати окремі байти з слова, тільки побітовое і зрушення.)
     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. 
    To actually check if the residue is a square, I look up the answer in a precomputed table.
     if( bad255[y] ) return false; // However, I just use a table of size 512 
  • Нарешті, спробуйте обчислити квадратний корінь, використовуючи метод, аналогічний лемме Хензель . (Я не думаю, що він застосуємо безпосередньо, але він працює з деякими змінами.) Перш ніж це зробити, я поділяю всі повноваження 2 з бінарним пошуком:
     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; 
    На цьому етапі, щоб наш номер був квадратом, він повинен бути 1 mod 8.
     if((x  7) != 1) return false; 
    Основна структура леми Хензель полягає в наступному. (Примітка: неперевірений код, якщо він не працює, спробуйте t = 2 або 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. 
    Ідея полягає в тому, що на кожній ітерації ви додаєте один біт в r, "поточний" квадратний корінь з x; кожен квадратний корінь точно по модулю більше і більше потужності 2, а саме t / 2. В кінці r і t / 2-r будуть квадратними коренями з x по модулю t / 2. (Зауважимо, що якщо r є квадратним коренем з x, то і -r. Це вірно навіть по модулю чисел, але будьте обережні, по модулю деяких чисел, речі можуть мати навіть більш 2 квадратних коренів, особливо це включає в себе повноваження 2. ) Оскільки наш фактичний квадратний корінь менше 2 ^ 32, в цій точці ми можемо просто перевірити, чи є r або t / 2 -r речовими квадратними коренями. У моєму фактичному коді я використовую наступний модифікований цикл:
     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) ); 
    Прискорення тут виходить трьома способами: попередньо обчислене початкове значення (еквівалентну ~ 10 итерациям циклу), більш ранній вихід з циклу і пропускання деяких значень t. В останній частині я дивлюся на z = r - x * x і встановлюю t як найбільший ступінь 2, що ділить z за допомогою трюку. Це дозволяє мені пропускати значення t, які не вплинули б на значення r в будь-якому випадку. Попередньо обчислене початкове значення в моєму випадку вибирає "найменший позитивний" квадратний корінь по модулю 8192.

Навіть якщо цей код не працює швидше для вас, я сподіваюся, вам сподобаються деякі з його ідей. Повний, перевірений код слід, включаючи попередньо обчислені таблиці.

 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 || ((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 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; } 
644
08 янв. відповідь дан A. Rex 08 Січня. 2009-01-08 19:32 '09 о 19:32 2009-01-08 19:32

2019

307
08 сент. відповідь дан maaartinus 08 сент. 2013-09-08 20:37 '13 о 20:37 2013-09-08 20:37

Вам потрібно буде провести бенчмаркінг. Кращий алгоритм буде залежати від розподілу ваших входів.

Ваш алгоритм може бути майже оптимальним, але ви можете зробити швидку перевірку, щоб виключити деякі можливості перед викликом вашої кореневої підпрограми. Наприклад, подивіться останню цифру свого номера в шістнадцятковому форматі, виконавши біт-мудрий "і". Ідеальні квадрати можуть закінчуватися тільки на 0, 1, 4 або 9 в базі 16. Таким чином, для 75% ваших входів (за умови, що вони рівномірно розподілені) ви можете уникнути виклику квадратного кореня в обмін на дуже швидке свердління біт.

Кіп порівняв наступний код, який реалізує шістнадцятковий трюк. При тестуванні чисел від 1 до 100 000 000 цей код виконувався в два рази швидше оригіналу.

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

Коли я протестував аналогічний код на С ++, він фактично працював повільніше оригіналу. Однак, коли я виключив оператор switch, шістнадцятковий трюк ще раз зробить код в два рази швидше.

 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; } if statement as soon as possible 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; } 

Усунення оператора switch мало вплинуло на код С #.

124
17 нояб. відповідь дан John D. Cook 17 нояб. 2008-11-17 17:27 '08 о 17:27 2008-11-17 17:27

Я думав про страшні часи, які я провів в курсі "Чисельний аналіз".

І потім я пам'ятаю, що ця функція оберталася навколо "мережі" з вихідного коду Quake:

 float Q_rsqrt( float number ) { long i; float x2, y; const float threehalfs = 1.5F; x2 = number * 0.5F; y = number; i = * ( long * )  // evil floating point bit level hacking i = 0x5f3759df - ( i >> 1 ); // wtf? y = * ( float * )  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; } 

В основному обчислює квадратний корінь, використовуючи функцію апроксимації Ньютона (не пам'ятаю точну назву).

Він повинен бути корисний і навіть може бути швидше, він з однією з феноменальних програмних ігор!

Це написано на С ++, але не слід занадто складно повторно використовувати ту ж техніку на Java, як тільки ви отримаєте ідею:

Я спочатку знайшов його за адресою: http://www.codemaestro.com/reviews/9

Метод Ньютона пояснений в wikipedia: http://en.wikipedia.org/wiki/Newton%27s_method

Ви можете перейти по посиланню, щоб дізнатися більше про те, як вона працює, але якщо вас це не хвилює, то це приблизно те, що я пам'ятаю, коли читав блог і проходив курс Numerical Analysis:

  • * (long*) > - це, в основному, швидка функція перетворення в довгий, тому для необроблених байтів можуть застосовуватися цілі операції.
  • рядок 0x5f3759df - (i >> 1); - це попередньо обчислене початкове значення для апроксимаційної функції.
  • * (float*) > перетворює значення назад в плаваючу точку.
  • рядок y = y * ( threehalfs - ( x2 * y * y ) ) базово повторює значення над функцією знову.

Функція апроксимації дає більш точні значення, чим більше ви виконуєте функцію по результату. У разі Quake одна ітерація "досить хороша", але якби це було не для вас ... тоді ви могли б додати стільки ж ітерацій, скільки вам потрібно.

Це повинно бути швидше, тому що воно зменшує кількість операцій поділу, виконуваних при наївному квадратному укоріненні, до простого поділу на 2 (фактично операція множення * 0.5F ) і замість цього замінює собою кілька фіксованих чисел операцій множення.

45
17 нояб. відповідь дан chakrit 17 нояб. 2008-11-17 16:50 '08 о 16:50 2008-11-17 16:50

Я не впевнений, чи буде це швидше або навіть точно, але ви можете використовувати John Carmack Magical Square Root , алгоритм для вирішення квадратний корінь швидше. Ймовірно, ви можете легко протестувати це для всіх можливих 32-бітних цілих чисел і підтвердити, що у вас дійсно є правильні результати, так як це тільки апроксимація. Однак тепер, коли я думаю про це, використання подвоєнь також наближається, тому я не впевнений, як це вступає в гру.

36
17 нояб. відповідь дан Kibbee 17 нояб. 2008-11-17 16:51 '08 о 16:51 2008-11-17 16:51

Якщо ви робите двійкову відбиття, щоб спробувати знайти "правильний" квадратний корінь, ви можете досить легко виявити, чи має значення, яке у вас є, досить близько, щоб сказати:

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

Отже, обчислюючи n^2 , параметри:

  • n^2 = target : done, return true
  • n^2 + 2n + 1 > target > n^2 : ви близькі, але це не ідеально: return false
  • n^2 - 2n + 1 < target < n^2 : ditto
  • target < n^2 - 2n + 1 : бінарна відбивна на нижній n
  • target > n^2 + 2n + 1 : бінарна відбивна на більш високому n

(Вибачте, це використовує n як ваше поточне припущення і target для параметра. Вибачте за плутанину!)

Я не знаю, чи буде це швидше чи ні, але варто спробувати.

EDIT: бінарна відбивна не повинна приймати весь діапазон цілих чисел, або (2^x)^2 = 2^(2x) , тому, як тільки ви знайдете верхній біт набору у своїй меті (що може бути зроблено за допомогою трюку з битою, Я забуваю, як саме) ви можете швидко отримати ряд потенційних відповідей. Майте на увазі, що наївна бінарна дріб все ще буде займати до 31 або 32 ітерацій.

32
17 нояб. відповідь дан Jon Skeet 17 нояб. 2008-11-17 16:50 '08 о 16:50 2008-11-17 16:50

Я провів власний аналіз декількох алгоритмів в цьому потоці і придумав деякі нові результати. Ви можете побачити ці старі результати в історії змін цієї відповіді, але вони не точні, оскільки я припустився помилки, і витратив час на аналіз декількох алгоритмів, які не близькі. Однак, витягуючи уроки з декількох різних відповідей, у мене тепер є два алгоритму, які пригнічують "переможця" цього потоку. Тут головне, що я роблю інакше, ніж всі інші:

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

Однак ця проста рядок, яка в більшості випадків додає одну або дві дуже швидкі інструкції, значно спрощує оператор switch-case в один оператор if. Проте, він може додати до робочого часу, якщо багато з тестованих номерів мають значну силу двох факторів.

Нижче наведені такі алгоритми:

  • Інтернет - відповідь на Kip
  • Durron - Мій змінений відповідь, використовуючи однопрохідний відповідь в якості бази
  • DurronTwo. Мій змінений відповідь, використовуючи двопрохідний відповідь (by @JohnnyHeggheim), з деякими іншими невеликими змінами.

Ось приклад часу виконання, якщо числа генеруються за допомогою 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