أسرع طريقة لتحديد ما إذا كان الجذر التربيعي لعدد صحيح هو عدد صحيح
https://stackoverflow.com/questions/295579
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أنا أبحث عن أسرع طريقة لتحديد ما إذا كان أ long القيمة هي مربع كامل (أيجذره التربيعي هو عدد صحيح آخر):
- لقد فعلت ذلك بطريقة سهلة، وذلك باستخدام المدمج في
Math.sqrt()الوظيفة ، لكنني أتساءل عما إذا كانت هناك طريقة للقيام بذلك بشكل أسرع من خلال تقييد نفسك في مجال عدد صحيح فقط. - الحفاظ على جدول البحث أمر غير عملي (نظرًا لوجود حوالي 231.5 الأعداد الصحيحة التي مربعها أقل من 263).
هذه هي الطريقة البسيطة والمباشرة التي أقوم بها الآن:
public final static boolean isPerfectSquare(long n)
{
if (n < 0)
return false;
long tst = (long)(Math.sqrt(n) + 0.5);
return tst*tst == n;
}
ملحوظة:أنا أستخدم هذه الوظيفة في كثير مشروع أويلر مشاكل.لذلك لن يضطر أي شخص آخر إلى الحفاظ على هذا الرمز.وهذا النوع من التحسين الجزئي يمكن أن يُحدث فرقًا في الواقع، نظرًا لأن جزءًا من التحدي يتمثل في تنفيذ كل خوارزمية في أقل من دقيقة، وسيلزم استدعاء هذه الوظيفة ملايين المرات في بعض المشكلات.
لقد جربت الحلول المختلفة للمشكلة:
- وبعد اختبار شامل، وجدت أن الإضافة
0.5إلى نتيجة Math.sqrt() ليست ضرورية، على الأقل ليس على جهازي. - ال الجذر التربيعي العكسي السريع كان أسرع، لكنه أعطى نتائج غير صحيحة لـ n >= 410881.ومع ذلك، كما اقترح بوبي شافتو, يمكننا استخدام اختراق FISR لـ n <410881.
- كانت طريقة نيوتن أبطأ قليلاً من
Math.sqrt().ربما يكون هذا بسببMath.sqrt()يستخدم شيئًا مشابهًا لطريقة نيوتن، ولكن يتم تنفيذه في الأجهزة، لذا فهو أسرع بكثير من Java.كما أن طريقة نيوتن لا تزال تتطلب استخدام الثنائيات. - تتطلب طريقة نيوتن المعدلة، والتي استخدمت بعض الحيل بحيث يتم استخدام الرياضيات الصحيحة فقط، بعض الاختراقات لتجنب التجاوز (أريد أن تعمل هذه الوظيفة مع جميع الأعداد الصحيحة الموجبة ذات 64 بت)، وكانت لا تزال أبطأ من
Math.sqrt(). - وكان الفرم الثنائي أبطأ.وهذا أمر منطقي لأن القطع الثنائي سيتطلب في المتوسط 16 تمريرة للعثور على الجذر التربيعي لعدد 64 بت.
- وفقا لاختبارات جون، وذلك باستخدام
orالبيانات أسرع في C++ من استخدام ملفswitch, ، ولكن في Java وC# يبدو أنه لا يوجد فرق بينهماorوswitch. - لقد حاولت أيضًا إنشاء جدول بحث (كمصفوفة ثابتة خاصة مكونة من 64 قيمة منطقية).ثم بدلاً من التبديل أو
orالبيان، وأود أن أقول فقطif(lookup[(int)(n&0x3F)]) { test } else return false;.لدهشتي، كان هذا (قليلاً) أبطأ.هذا بسبب يتم التحقق من حدود الصفيف في Java.
المحلول
لقد اكتشفت طريقة تعمل بشكل أسرع بنسبة 35% تقريبًا من كود 6bits+Carmack+sqrt، على الأقل مع وحدة المعالجة المركزية (x86) ولغة البرمجة (C/C++).قد تختلف نتائجك، خاصة لأنني لا أعرف كيف سيعمل عامل Java.
نهجي هو ثلاثة أضعاف:
- أولاً، قم بتصفية الإجابات الواضحة.يتضمن ذلك الأرقام السالبة والنظر إلى آخر 4 بتات.(لقد وجدت أن النظر إلى الستة الأخيرة لم يساعد.) وأجيب أيضًا بنعم بـ 0.(عند قراءة الكود أدناه، لاحظ أن مدخلاتي هي
int64 x.)if( x < 0 || (x&2) || ((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.if( bad255[y] ) return false; // However, I just use a table of size 512 - وأخيرًا، حاول حساب الجذر التربيعي باستخدام طريقة مشابهة لـ ليما هينسل.(لا أعتقد أنه قابل للتطبيق بشكل مباشر، لكنه يعمل مع بعض التعديلات.) قبل القيام بذلك، أقسم جميع قوى العدد 2 باستخدام بحث ثنائي:
في هذه المرحلة، لكي يكون الرقم مربعًا، يجب أن يكون 1 mod 8.if((x & 4294967295LL) == 0) x >>= 32; if((x & 65535) == 0) x >>= 16; if((x & 255) == 0) x >>= 8; if((x & 15) == 0) x >>= 4; if((x & 3) == 0) x >>= 2;
الهيكل الأساسي لليما هنسل هو ما يلي.(ملحوظة:رمز لم يتم اختباره؛إذا لم ينجح الأمر، فجرّب t=2 أو 8.)if((x & 7) != 1) return false;
الفكرة هي أنه في كل تكرار، يمكنك إضافة بت واحد إلى r، الجذر التربيعي "الحالي" لـ x؛كل جذر تربيعي هو معامل دقيق لقوة أكبر وأكبر من 2، وهي t/2.في النهاية، r وt/2-r سيكونان جذورًا تربيعية لـ x modulo t/2.(لاحظ أنه إذا كان r هو الجذر التربيعي لـ x، فإن -r كذلك.هذا صحيح حتى في الأرقام المعيارية، لكن احذر، في بعض الأرقام، يمكن أن تحتوي الأشياء على أكثر من جذرين تربيعيين؛على وجه الخصوص، يتضمن هذا قوى 2.) نظرًا لأن الجذر التربيعي الفعلي لدينا أقل من 2^32، عند هذه النقطة يمكننا فقط التحقق مما إذا كان r أو t/2-r جذورًا تربيعية حقيقية.في الكود الفعلي الخاص بي، أستخدم الحلقة المعدلة التالية: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.
يتم الحصول على التسريع هنا بثلاث طرق:قيمة البدء المحسوبة مسبقًا (أي ما يعادل ~10 تكرارات للحلقة)، والخروج المبكر من الحلقة، وتخطي بعض قيم t.بالنسبة للجزء الأخير، وأنا أنظر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) );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&2) || ((x & 7) == 5) || ((x & 11) == 8) )
return false;
if( x == 0 )
return true;
// Check mod 255 = 3 * 5 * 17, for fun
int64 y = x;
y = (y & 4294967295LL) + (y >> 32);
y = (y & 65535) + (y >> 16);
y = (y & 255) + ((y >> 8) & 255) + (y >> 16);
if( bad255[y] )
return false;
// Divide out powers of 4 using binary search
if((x & 4294967295LL) == 0)
x >>= 32;
if((x & 65535) == 0)
x >>= 16;
if((x & 255) == 0)
x >>= 8;
if((x & 15) == 0)
x >>= 4;
if((x & 3) == 0)
x >>= 2;
if((x & 7) != 1)
return false;
// Compute sqrt using something like Hensel's lemma
int64 r, t, z;
r = start[(x >> 3) & 1023];
do {
z = x - r * r;
if( z == 0 )
return true;
if( z < 0 )
return false;
t = z & (-z);
r += (z & t) >> 1;
if( r > (t >> 1) )
r = t - r;
} while( t <= (1LL << 33) );
return false;
}نصائح أخرى
لقد تأخرت كثيرًا عن الحفلة، لكني آمل أن أقدم إجابة أفضل؛أقصر و (على افتراض بلدي المعيار صحيح) أيضا كثيرا أسرع.
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;
}
يلتقط الاختبار الأول معظم المربعات غير المربعة بسرعة.يستخدم جدولًا مكونًا من 64 عنصرًا ومعبأًا لفترة طويلة، لذلك لا توجد تكلفة للوصول إلى المصفوفة (التحقق من المراوغة والحدود).للحصول على عشوائية موحدة long, ، هناك احتمال 81.25% للانتهاء هنا.
يلتقط الاختبار الثاني جميع الأرقام التي تحتوي على عدد فردي من الثنائيات في تحليلها.طريقة Long.numberOfTrailingZeros سريع جدًا حيث يقوم بإدخال JIT-ed في تعليمات i86 واحدة.
بعد إسقاط الأصفار الزائدة، يتعامل الاختبار الثالث مع الأرقام التي تنتهي بـ 011 أو 101 أو 111 في النظام الثنائي، وهي ليست مربعات كاملة.كما أنه يهتم بالأرقام السالبة ويتعامل أيضًا مع 0.
الاختبار النهائي يعود إلى double علم الحساب.مثل double لديه 53 بت فقط مانتيسا ، التحويل من long ل double يتضمن التقريب للقيم الكبيرة.ومع ذلك، فإن الاختبار صحيح (ما لم يكن دليل خطأ).
لم تكن محاولة دمج فكرة mod255 ناجحة.
سيكون عليك القيام ببعض المعايير.ستعتمد أفضل خوارزمية على توزيع مدخلاتك.
قد تكون الخوارزمية الخاصة بك مثالية تقريبًا، ولكن قد ترغب في إجراء فحص سريع لاستبعاد بعض الاحتمالات قبل استدعاء روتين الجذر التربيعي الخاص بك.على سبيل المثال ، انظر إلى آخر رقم من رقمك في Hex عن طريق القيام قليلاً "و." لا يمكن أن تنتهي المربعات المثالية إلا في 0 أو 1 أو 4 أو 9 في القاعدة 16 ، لذا بالنسبة إلى 75 ٪ من مدخلاتك (على افتراض أنها موزعة بشكل موحد) ، يمكنك تجنب مكالمة إلى الجذر التربيعي في مقابل بعض الحشوة السريعة جدًا.
قام Kip بقياس الكود التالي لتنفيذ الخدعة السداسية.عند اختبار الأرقام من 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;
}
}
عندما اختبرت التعليمات البرمجية المشابهة في لغة C++، كانت في الواقع تعمل بشكل أبطأ من النسخة الأصلية.ومع ذلك، عندما قمت بحذف بيان التبديل، فإن الخدعة السداسية تجعل الكود أسرع مرتين مرة أخرى.
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;
}
لم يكن لإزالة بيان التبديل تأثير يذكر على كود C#.
كنت أفكر في الأوقات الفظيعة التي قضيتها في دورة التحليل العددي.
ثم أتذكر أنه كانت هناك هذه الوظيفة تدور حول الشبكة من كود مصدر الزلزال:
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;
}
الذي يحسب بشكل أساسي الجذر التربيعي، باستخدام وظيفة تقريب نيوتن (لا أستطيع تذكر الاسم الدقيق).
يجب أن يكون قابلاً للاستخدام وربما يكون أسرع، فهو من إحدى ألعاب برامج الهوية الرائعة!
إنه مكتوب بلغة C++ ولكن لا ينبغي أن يكون من الصعب جدًا إعادة استخدام نفس التقنية في Java بمجرد حصولك على الفكرة:
لقد وجدته في الأصل في: http://www.codemaestro.com/reviews/9
طريقة نيوتن موضحة في ويكيبيديا: http://en.wikipedia.org/wiki/Newton%27s_method
يمكنك اتباع الرابط لمزيد من الشرح حول كيفية عمله، ولكن إذا كنت لا تهتم كثيرًا، فهذا تقريبًا ما أتذكره من قراءة المدونة ومن تلقي دورة التحليل العددي:
- ال
* (long*) &yهي في الأساس وظيفة تحويل سريعة إلى طويلة بحيث يمكن تطبيق عمليات الأعداد الصحيحة على البايتات الأولية. - ال
0x5f3759df - (i >> 1);الخط هو قيمة أولية محسوبة مسبقًا لوظيفة التقريب. - ال
* (float*) &iتحويل القيمة مرة أخرى إلى النقطة العائمة. - ال
y = y * ( threehalfs - ( x2 * y * y ) )يقوم الخط بتكرار القيمة بشكل أساسي على الوظيفة مرة أخرى.
تعطي وظيفة التقريب قيمًا أكثر دقة كلما كررت الوظيفة على النتيجة.في حالة Quake، يعد تكرار واحد "جيدًا بما فيه الكفاية"، ولكن إذا لم يكن ذلك مناسبًا لك...ثم يمكنك إضافة أكبر قدر من التكرار الذي تحتاجه.
يجب أن يكون هذا أسرع لأنه يقلل من عدد عمليات القسمة التي يتم إجراؤها باستخدام الجذر التربيعي الساذج وصولاً إلى قسمة بسيطة على 2 (في الواقع * 0.5F عملية الضرب) واستبدالها بعدد قليل من عمليات الضرب بدلاً من ذلك.
لست متأكدًا مما إذا كان سيكون أسرع أو حتى دقيقًا، ولكن يمكنك استخدامه الجذر التربيعي السحري لجون كارماك, خوارزمية لحل الجذر التربيعي بشكل أسرع.ربما يمكنك بسهولة اختبار ذلك لجميع الأعداد الصحيحة 32 بت الممكنة، والتحقق من أنك حصلت بالفعل على النتائج الصحيحة، حيث إنها مجرد تقدير تقريبي.ومع ذلك، الآن بعد أن أفكر في الأمر، فإن استخدام الزوجي يعد أمرًا تقريبيًا أيضًا، لذلك لست متأكدًا من كيفية تطبيق ذلك.
إذا قمت بإجراء عملية قطع ثنائية لمحاولة العثور على الجذر التربيعي "الصحيح"، فيمكنك بسهولة اكتشاف ما إذا كانت القيمة التي حصلت عليها قريبة بدرجة كافية لمعرفة ما يلي:
(n+1)^2 = n^2 + 2n + 1
(n-1)^2 = n^2 - 2n + 1
لذلك بعد أن حسبت n^2, ، الخيارات هي:
n^2 = target:تم، والعودة الحقيقيةn^2 + 2n + 1 > target > n^2:أنت قريب، لكنه ليس مثاليًا:عودة كاذبةn^2 - 2n + 1 < target < n^2:كما سبقtarget < n^2 - 2n + 1:قطع ثنائي على أقلntarget > n^2 + 2n + 1:ختم ثنائي على مستوى أعلىn
(عذرا، هذا يستخدم n كما تخمينك الحالي، و target للمعلمة.اعتذر عن الارتباك!)
لا أعرف ما إذا كان هذا سيكون أسرع أم لا، ولكن الأمر يستحق المحاولة.
يحرر:ليس من الضروري أن تأخذ القطعة الثنائية نطاقًا كاملاً من الأعداد الصحيحة أيضًا (2^x)^2 = 2^(2x), ، لذلك بمجرد العثور على البتة العلوية في هدفك (والتي يمكن القيام بها بخدعة التلاعب بالبت؛لقد نسيت بالضبط كيف) يمكنك الحصول بسرعة على مجموعة من الإجابات المحتملة.ضع في اعتبارك أن القطع الثنائي الساذج سيستغرق ما يصل إلى 31 أو 32 تكرارًا فقط.
لقد قمت بإجراء تحليلي الخاص للعديد من الخوارزميات في هذا الموضوع وتوصلت إلى بعض النتائج الجديدة.يمكنك رؤية تلك النتائج القديمة في سجل التعديل لهذه الإجابة، لكنها ليست دقيقة، لأنني ارتكبت خطأً وأهدرت الوقت في تحليل العديد من الخوارزميات غير المتقاربة.ومع ذلك، وباستخلاص الدروس من عدة إجابات مختلفة، لدي الآن خوارزميتان تسحقان "الفائز" في هذا الموضوع.هذا هو الشيء الأساسي الذي أفعله بشكل مختلف عن أي شخص آخر:
// 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 بيان في واحد إذا البيان.ومع ذلك، يمكن أن يضيف إلى وقت التشغيل إذا كان لدى العديد من الأرقام التي تم اختبارها قوة عاملين مهمين.
الخوارزميات أدناه هي كما يلي:
- إنترنت - إجابة كيب المنشورة
- دورون - إجابتي المعدلة باستخدام إجابة المرور الواحد كقاعدة
- دورونتو - إجابتي المعدلة باستخدام الإجابة ذات التمريرتين (بواسطة @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
وإليك نموذجًا لوقت التشغيل إذا تم تشغيله على المليون الأول فقط:
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
كما ترون، DurronTwo يعمل بشكل أفضل مع المدخلات الكبيرة، لأنه يستخدم الخدعة السحرية في كثير من الأحيان، ولكنه يتعرض للضرب مقارنة بالخوارزمية الأولى و Math.sqrt لأن الأرقام أصغر بكثير.وفي الوقت نفسه، أبسط Durron يعد هذا فائزًا كبيرًا لأنه لا يتعين عليه أبدًا القسمة على 4 عدة مرات في أول مليون رقم.
هنا 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;
}
وحزامي المعياري:(يتطلب فرجار جوجل 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);
}
}
تحديث: لقد قمت بإنشاء خوارزمية جديدة تكون أسرع في بعض السيناريوهات، وأبطأ في سيناريوهات أخرى، وحصلت على معايير مختلفة بناءً على مدخلات مختلفة.إذا قمنا بحساب modulo 0xFFFFFF = 3 x 3 x 5 x 7 x 13 x 17 x 241, ، يمكننا حذف 97.82% من الأرقام التي لا يمكن أن تكون مربعات.يمكن (نوعًا ما) القيام بذلك في سطر واحد، مع 5 عمليات بت:
if (!goodLookupSquares[(int) ((n & 0xFFFFFFl) + ((n >> 24) & 0xFFFFFFl) + (n >> 48))]) return false;
المؤشر الناتج هو إما 1) البقايا، 2) البقايا + 0xFFFFFF, أو 3) الباقي + 0x1FFFFFE.بالطبع، نحن بحاجة إلى جدول بحث عن وحدات المخلفات 0xFFFFFF, ، وهو عبارة عن ملف بحجم 3 ميجابايت (في هذه الحالة يتم تخزينه كأرقام عشرية لنص ascii، وهو ليس مثاليًا ولكن من الواضح أنه يمكن تحسينه باستخدام ملف ByteBuffer وهكذا دواليك.ولكن بما أن هذا هو الحساب المسبق، فإنه لا يهم كثيرا. يمكنك العثور على الملف هنا (أو قم بإنشائها بنفسك):
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;
}
أنا تحميله في boolean مصفوفة مثل هذا:
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();
}
مثال لوقت التشغيل.لقد تغلب Durron (الإصدار الأول) في كل تجربة أجريتها.
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
يجب أن يكون أسرع بكثير في الاستخدام طريقة نيوتن لحساب عدد صحيح الجذر التربيعي, ، ثم قم بتربيع هذا الرقم وتحقق منه، كما تفعل في الحل الحالي.طريقة نيوتن هي أساس حل كارماك المذكور في بعض الإجابات الأخرى.من المفترض أن تكون قادرًا على الحصول على إجابة أسرع نظرًا لأنك مهتم فقط بالجزء الصحيح من الجذر، مما يسمح لك بإيقاف خوارزمية التقريب عاجلاً.
تحسين آخر يمكنك تجربته:إذا الجذر الرقمي لا ينتهي الرقم في 1 أو 4 أو 7 أو 9 الرقم لا مربع مثالي.يمكن استخدام هذا كطريقة سريعة للتخلص من 60% من مدخلاتك قبل تطبيق خوارزمية الجذر التربيعي الأبطأ.
أريد أن تعمل هذه الوظيفة مع جميع الأعداد الصحيحة الإيجابية 64 بت
Math.sqrt() يعمل مع الزوجي كمعلمات إدخال، لذلك لن تحصل على نتائج دقيقة للأعداد الصحيحة الأكبر من 2^53.
فقط للعلم، هناك طريقة أخرى وهي استخدام التحليل الأولي.إذا كانت جميع عوامل التحلل زوجية، فإن العدد يكون مربعًا كاملاً.إذن ما تريده هو معرفة ما إذا كان من الممكن تحليل الرقم كمنتج لمربعات الأعداد الأولية.وبطبيعة الحال، لا تحتاج إلى الحصول على مثل هذا التحلل، فقط لمعرفة ما إذا كان موجودا.
قم أولاً ببناء جدول مربعات الأعداد الأولية التي تكون أقل من 2^32.وهذا أصغر بكثير من جدول يضم جميع الأعداد الصحيحة حتى هذا الحد.
ثم سيكون الحل مثل هذا:
boolean isPerfectSquare(long number)
{
if (number < 0) return false;
if (number < 2) return true;
for (int i = 0; ; i++)
{
long square = squareTable[i];
if (square > number) return false;
while (number % square == 0)
{
number /= square;
}
if (number == 1) return true;
}
}
أعتقد أنه غامض بعض الشيء.ما يفعله هو التحقق في كل خطوة من أن مربع الرقم الأولي يقسم رقم الإدخال.فإذا فعل ذلك فإنه يقسم العدد على المربع لأطول فترة ممكنة، لإزالة هذا المربع من التحلل الأولي.إذا وصلنا بهذه العملية إلى 1، فسيكون رقم الإدخال عبارة عن تحليل لمربع الأعداد الأولية.إذا أصبح المربع أكبر من الرقم نفسه، فلا يمكن لهذا المربع، أو أي مربع أكبر، أن يقسمه، وبالتالي لا يمكن أن يكون الرقم عبارة عن تحليل لمربعات من الأعداد الأولية.
نظرًا لما يتم تنفيذه في الوقت الحاضر من استخدام sqrt في الأجهزة والحاجة إلى حساب الأعداد الأولية هنا، أعتقد أن هذا الحل أبطأ بكثير.ولكن يجب أن تعطي نتائج أفضل من الحل مع sqrt الذي لن يعمل أكثر من 2 ^ 54، كما يقول mrzl في إجابته.
مشكلة عدد صحيح تستحق حل عدد صحيح.هكذا
قم بإجراء بحث ثنائي على الأعداد الصحيحة (غير السالبة) للعثور على أكبر عدد صحيح من هذا القبيل t**2 <= n.ثم اختبار ما إذا كان r**2 = n بالضبط.يستغرق هذا وقتًا O(log n).
إذا كنت لا تعرف كيفية البحث الثنائي عن الأعداد الصحيحة الموجبة لأن المجموعة غير محدودة، فالأمر سهل.تبدأ بحساب وظيفتك المتزايدة f (أعلاه f(t) = t**2 - n) على صلاحيات اثنين.عندما تراه يتحول إلى إيجابي، فقد وجدت الحد الأعلى.ثم يمكنك إجراء بحث ثنائي قياسي.
وقد تمت الإشارة إلى أن الأخير d يمكن لأرقام المربع الكامل أن تأخذ قيمًا معينة فقط.الاخير d أرقام (في القاعدة b) من عدد n هو نفس الباقي عندما n مقسمة على bd, ، أي.في تدوين C n % pow(b, d).
يمكن تعميم ذلك على أي معامل m, ، أي. n % m يمكن استخدامها لاستبعاد نسبة معينة من الأرقام من كونها مربعات كاملة.المعامل الذي تستخدمه حاليًا هو 64، وهو ما يسمح بـ 12، أي.19% من الباقي، كمربعات محتملة.مع القليل من الترميز وجدت المعامل 110880، والذي يسمح فقط بـ 2016، أي.1.8% من الباقي كمربعات محتملة.لذلك اعتمادًا على تكلفة عملية المعامل (أي.Division) والبحث عن جدول مقابل الجذر التربيعي على جهازك، قد يكون استخدام هذا المعامل أسرع.
بالمناسبة، إذا كان لدى Java طريقة لتخزين مجموعة من البتات لجدول البحث، فلا تستخدمها.110880 كلمة 32 بت لا تمثل الكثير من ذاكرة الوصول العشوائي (RAM) هذه الأيام وسيكون جلب كلمة الآلة أسرع من جلب بت واحد.
بالنسبة للأداء، يتعين عليك في كثير من الأحيان القيام ببعض التنازلات.لقد عبر آخرون عن طرق مختلفة، ومع ذلك، فقد لاحظت أن اختراق كارماك كان أسرع حتى قيم معينة من N.بعد ذلك، يجب عليك التحقق من "n" وإذا كان أقل من هذا الرقم N، فاستخدم اختراق Carmack، وإلا استخدم طريقة أخرى موضحة في الإجابات هنا.
هذا هو أسرع تطبيق Java يمكن أن أتوصل إليه، باستخدام مجموعة من التقنيات التي اقترحها الآخرون في هذا الموضوع.
- اختبار مود-256
- اختبار mod-3465 غير دقيق (يتجنب تقسيم الأعداد الصحيحة على حساب بعض النتائج الإيجابية الخاطئة)
- الجذر التربيعي للفاصلة العائمة، مستدير ومقارنته بقيمة الإدخال
لقد قمت أيضًا بتجربة هذه التعديلات لكنها لم تساعد في الأداء:
- اختبار إضافي لـ mod-255
- قسمة قيمة الإدخال على قوى 4
- الجذر التربيعي العكسي السريع (للعمل مع القيم العالية لـ N، يحتاج إلى 3 تكرارات، وهو ما يكفي لجعله أبطأ من وظيفة الجذر التربيعي للأجهزة.)
public class SquareTester {
public static boolean isPerfectSquare(long n) {
if (n < 0) {
return false;
} else {
switch ((byte) n) {
case -128: case -127: case -124: case -119: case -112:
case -111: case -103: case -95: case -92: case -87:
case -79: case -71: case -64: case -63: case -60:
case -55: case -47: case -39: case -31: case -28:
case -23: case -15: case -7: case 0: case 1:
case 4: case 9: case 16: case 17: case 25:
case 33: case 36: case 41: case 49: case 57:
case 64: case 65: case 68: case 73: case 81:
case 89: case 97: case 100: case 105: case 113:
case 121:
long i = (n * INV3465) >>> 52;
if (! good3465[(int) i]) {
return false;
} else {
long r = round(Math.sqrt(n));
return r*r == n;
}
default:
return false;
}
}
}
private static int round(double x) {
return (int) Double.doubleToRawLongBits(x + (double) (1L << 52));
}
/** 3465<sup>-1</sup> modulo 2<sup>64</sup> */
private static final long INV3465 = 0x8ffed161732e78b9L;
private static final boolean[] good3465 =
new boolean[0x1000];
static {
for (int r = 0; r < 3465; ++ r) {
int i = (int) ((r * r * INV3465) >>> 52);
good3465[i] = good3465[i+1] = true;
}
}
}
يبدو أن التبسيط التالي لحل maaartinus يختصر بضع نقاط مئوية من وقت التشغيل، لكنني لست جيدًا بما يكفي في قياس الأداء لإنتاج معيار يمكنني الوثوق به:
long goodMask; // 0xC840C04048404040 computed below
{
for (int i=0; i<64; ++i) goodMask |= Long.MIN_VALUE >>> (i*i);
}
public boolean isSquare(long x) {
// This tests if the 6 least significant bits are right.
// Moving the to be tested bit to the highest position saves us masking.
if (goodMask << x >= 0) return false;
// Remove an even number of trailing zeros, leaving at most one.
x >>= (Long.numberOfTrailingZeros(x) & (-2);
// Repeat the test on the 6 least significant remaining bits.
if (goodMask << x >= 0 | x <= 0) return x == 0;
// Do it in the classical way.
// The correctness is not trivial as the conversion from long to double is lossy!
final long tst = (long) Math.sqrt(x);
return tst * tst == x;
}
سيكون من المفيد التحقق من كيفية حذف الاختبار الأول،
if (goodMask << x >= 0) return false;
من شأنه أن يؤثر على الأداء.
يجب عليك التخلص من الجزء ذو القوة 2 من N منذ البداية.
التحرير الثانييجب أن يكون التعبير السحري لـ m أدناه
m = N - (N & (N-1));
وليس كما هو مكتوب
نهاية التعديل الثاني
m = N & (N-1); // the lawest bit of N
N /= m;
byte = N & 0x0F;
if ((m % 2) || (byte !=1 && byte !=9))
return false;
التعديل الأول:
تحسين طفيف:
m = N & (N-1); // the lawest bit of N
N /= m;
if ((m % 2) || (N & 0x07 != 1))
return false;
نهاية التعديل الأول
الآن استمر كالمعتاد.بهذه الطريقة، بحلول الوقت الذي تصل فيه إلى جزء النقطة العائمة، تكون قد تخلصت بالفعل من جميع الأرقام التي يكون جزء أسها 2 فرديًا (حوالي النصف)، وبعد ذلك لا تفكر إلا في 1/8 مما تبقى.أي.تقوم بتشغيل جزء النقطة العائمة على 6% من الأرقام.
هذه إعادة صياغة من النظام العشري إلى الثنائي لخوارزمية آلة حاسبة Marchant القديمة (عذرًا، ليس لدي مرجع)، في روبي، تم تكييفها خصيصًا لهذا السؤال:
def isexactsqrt(v)
value = v.abs
residue = value
root = 0
onebit = 1
onebit <<= 8 while (onebit < residue)
onebit >>= 2 while (onebit > residue)
while (onebit > 0)
x = root + onebit
if (residue >= x) then
residue -= x
root = x + onebit
end
root >>= 1
onebit >>= 2
end
return (residue == 0)
end
فيما يلي ملخص لشيء مشابه (من فضلك لا تصوت لي لصالح أسلوب/روائح الترميز أو O/O غير المتقنة - إنها الخوارزمية التي تهم، وC++ ليست لغتي الأم).في هذه الحالة، نحن نبحث عن البقايا == 0:
#include <iostream>
using namespace std;
typedef unsigned long long int llint;
class ISqrt { // Integer Square Root
llint value; // Integer whose square root is required
llint root; // Result: floor(sqrt(value))
llint residue; // Result: value-root*root
llint onebit, x; // Working bit, working value
public:
ISqrt(llint v = 2) { // Constructor
Root(v); // Take the root
};
llint Root(llint r) { // Resets and calculates new square root
value = r; // Store input
residue = value; // Initialise for subtracting down
root = 0; // Clear root accumulator
onebit = 1; // Calculate start value of counter
onebit <<= (8*sizeof(llint)-2); // Set up counter bit as greatest odd power of 2
while (onebit > residue) {onebit >>= 2; }; // Shift down until just < value
while (onebit > 0) {
x = root ^ onebit; // Will check root+1bit (root bit corresponding to onebit is always zero)
if (residue >= x) { // Room to subtract?
residue -= x; // Yes - deduct from residue
root = x + onebit; // and step root
};
root >>= 1;
onebit >>= 2;
};
return root;
};
llint Residue() { // Returns residue from last calculation
return residue;
};
};
int main() {
llint big, i, q, r, v, delta;
big = 0; big = (big-1); // Kludge for "big number"
ISqrt b; // Make q sqrt generator
for ( i = big; i > 0 ; i /= 7 ) { // for several numbers
q = b.Root(i); // Get the square root
r = b.Residue(); // Get the residue
v = q*q+r; // Recalc original value
delta = v-i; // And diff, hopefully 0
cout << i << ": " << q << " ++ " << r << " V: " << v << " Delta: " << delta << "\n";
};
return 0;
};
إن استدعاء sqrt ليس دقيقًا تمامًا، كما ذكرنا سابقًا، ولكنه مثير للاهتمام ومفيد لأنه لا يتجاهل الإجابات الأخرى من حيث السرعة.بعد كل شيء، تسلسل تعليمات لغة التجميع لـ sqrt صغير جدًا.لدى Intel تعليمات خاصة بالأجهزة، والتي لا تستخدمها Java على ما أعتقد لأنها لا تتوافق مع IEEE.
فلماذا هو بطيء؟لأن Java تقوم بالفعل باستدعاء روتين C من خلال JNI، وهو في الواقع أبطأ في القيام بذلك من استدعاء روتين Java الفرعي، والذي هو في حد ذاته أبطأ من القيام بذلك بشكل مضمّن.هذا أمر مزعج للغاية، وكان ينبغي لـ Java أن تتوصل إلى حل أفضل، أي إنشاء استدعاءات مكتبة الفاصلة العائمة إذا لزم الأمر.اوه حسناً.
في C++، أظن أن جميع البدائل المعقدة ستفقد السرعة، لكنني لم أتحقق منها جميعًا.ما فعلته، وما سيجده موظفو Java مفيدًا، هو اختراق بسيط، وهو امتداد لاختبار الحالة الخاصة الذي اقترحه A.ريكس.استخدم قيمة طويلة واحدة كمصفوفة بتات، والتي لم يتم تحديد حدودها.بهذه الطريقة، سيكون لديك بحث منطقي 64 بت.
typedef unsigned long long UVLONG
UVLONG pp1,pp2;
void init2() {
for (int i = 0; i < 64; i++) {
for (int j = 0; j < 64; j++)
if (isPerfectSquare(i * 64 + j)) {
pp1 |= (1 << j);
pp2 |= (1 << i);
break;
}
}
cout << "pp1=" << pp1 << "," << pp2 << "\n";
}
inline bool isPerfectSquare5(UVLONG x) {
return pp1 & (1 << (x & 0x3F)) ? isPerfectSquare(x) : false;
}
يتم تشغيل الإجراء isPerfectSquare5 في حوالي ثلث الوقت على جهاز core2 الثنائي الخاص بي.أظن أن المزيد من التعديلات على نفس المنوال يمكن أن تقلل الوقت بشكل أكبر في المتوسط، ولكن في كل مرة تتحقق فيها، فإنك تستبدل المزيد من الاختبارات بمزيد من الإزالة، لذلك لا يمكنك الذهاب أبعد من ذلك على هذا الطريق.
بالتأكيد، بدلاً من إجراء اختبار منفصل للنتائج السلبية، يمكنك التحقق من الـ 6 بتات العالية بنفس الطريقة.
لاحظ أن كل ما أفعله هو إزالة المربعات المحتملة، ولكن عندما تكون لدي حالة محتملة، يجب علي استدعاء الحالة الأصلية المضمنة بـ isPerfectSquare.
يتم استدعاء روتين init2 مرة واحدة لتهيئة القيم الثابتة لـ pp1 وpp2.لاحظ أنه في تطبيقي في C++، أستخدم unsigned long long، لذا بما أنك قمت بالتسجيل، فسيتعين عليك استخدام عامل التشغيل >>>.
ليست هناك حاجة جوهرية للتحقق من حدود المصفوفة، ولكن يجب على مُحسِّن Java اكتشاف هذه الأشياء بسرعة كبيرة، لذلك لا ألومهم على ذلك.
تعجبني فكرة استخدام الطريقة الصحيحة تقريبًا في بعض المدخلات.هنا نسخة ذات "إزاحة" أعلى.يبدو أن الكود يعمل ويجتاز حالة الاختبار البسيطة الخاصة بي.
فقط استبدل الخاص بك:
if(n < 410881L){...}
الكود مع هذا:
if (n < 11043908100L) {
//John Carmack hack, converted to Java.
// See: http://www.codemaestro.com/reviews/9
int i;
float x2, y;
x2 = n * 0.5F;
y = n;
i = Float.floatToRawIntBits(y);
//using the magic number from
//http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf
//since it more accurate
i = 0x5f375a86 - (i >> 1);
y = Float.intBitsToFloat(i);
y = y * (1.5F - (x2 * y * y));
y = y * (1.5F - (x2 * y * y)); //Newton iteration, more accurate
sqrt = Math.round(1.0F / y);
} else {
//Carmack hack gives incorrect answer for n >= 11043908100.
sqrt = (long) Math.sqrt(n);
}
مشروع أويلر مذكور في العلامات والعديد من المشاكل فيه تتطلب التحقق من الأرقام >> 2^64.معظم التحسينات المذكورة أعلاه لا تعمل بسهولة عند العمل مع مخزن مؤقت بسعة 80 بايت.
لقد استخدمت Java BigInteger ونسخة معدلة قليلاً من طريقة نيوتن، وهي نسخة تعمل بشكل أفضل مع الأعداد الصحيحة.كانت المشكلة أن المربعات بالضبط n^2 متقاربة ل (n-1) بدلاً من n لأن n^2-1 = (n-1)(n+1) وكان الخطأ الأخير أقل بخطوة واحدة فقط من المقسوم عليه النهائي وتم إنهاء الخوارزمية.كان من السهل إصلاح ذلك عن طريق إضافة واحد إلى الوسيطة الأصلية قبل حساب الخطأ.(أضف اثنين للجذور التكعيبية، وما إلى ذلك)
إحدى السمات الرائعة لهذه الخوارزمية هي أنه يمكنك على الفور معرفة ما إذا كان الرقم مربعًا كاملاً أم لا - الخطأ الأخير (وليس التصحيح) في طريقة نيوتن سيكون صفرًا.يتيح لك التعديل البسيط أيضًا الحساب بسرعة floor(sqrt(x)) بدلاً من أقرب عدد صحيح.هذا مفيد مع العديد من مشاكل أويلر.
لقد تحققت من جميع النتائج المحتملة عند ملاحظة آخر عدد من البتات في المربع.من خلال فحص المزيد من البتات على التوالي، يمكن التخلص من ما يصل إلى 5/6 من المدخلات.لقد صممت هذا بالفعل لتنفيذ خوارزمية التخصيم الخاصة بـ Fermat، وهي سريعة جدًا هناك.
public static boolean isSquare(final long val) {
if ((val & 2) == 2 || (val & 7) == 5) {
return false;
}
if ((val & 11) == 8 || (val & 31) == 20) {
return false;
}
if ((val & 47) == 32 || (val & 127) == 80) {
return false;
}
if ((val & 191) == 128 || (val & 511) == 320) {
return false;
}
// if((val & a == b) || (val & c == d){
// return false;
// }
if (!modSq[(int) (val % modSq.length)]) {
return false;
}
final long root = (long) Math.sqrt(val);
return root * root == val;
}
يمكن استخدام الجزء الأخير من الكود الكاذب لتوسيع الاختبارات لإزالة المزيد من القيم.الاختبارات المذكورة أعلاه هي لـ k = 0، 1، 2، 3
فهو يختبر أولاً ما إذا كان لديه مربع متبقي بمعامل قوة يساوي اثنين، ثم يختبر بناءً على المعامل النهائي، ثم يستخدم Math.sqrt لإجراء اختبار نهائي.لقد خطرت لي الفكرة من أعلى المنشور، وحاولت التوسع فيها.وأنا أقدر أي تعليقات أو اقتراحات.
تحديث: باستخدام الاختبار بواسطة المعامل (modSq) وقاعدة المعامل 44352، يتم تشغيل الاختبار الخاص بي في 96% من وقت الاختبار الموجود في تحديث OP للأرقام التي تصل إلى 1,000,000,000.
بالنظر إلى طول البت العام (على الرغم من أنني استخدمت نوعًا محددًا هنا)، حاولت تصميم خوارزمية مبسطة على النحو التالي.مطلوب فحص بسيط وواضح لـ 0،1،2 أو <0 في البداية.التالي بسيط بمعنى أنه لا يحاول استخدام أي وظائف رياضية موجودة.يمكن استبدال معظم عوامل التشغيل بمعاملات البت.لم أختبر أي بيانات على الرغم من ذلك.أنا لست خبيرًا في الرياضيات أو تصميم خوارزميات الكمبيوتر على وجه الخصوص، وأحب أن أراك تشير إلى المشكلة.أعلم أن هناك الكثير من فرص التحسن هناك.
int main()
{
unsigned int c1=0 ,c2 = 0;
unsigned int x = 0;
unsigned int p = 0;
int k1 = 0;
scanf("%d",&p);
if(p % 2 == 0) {
x = p/2;
}
else {
x = (p/2) +1;
}
while(x)
{
if((x*x) > p) {
c1 = x;
x = x/2;
}else {
c2 = x;
break;
}
}
if((p%2) != 0)
c2++;
while(c2 < c1)
{
if((c2 * c2 ) == p) {
k1 = 1;
break;
}
c2++;
}
if(k1)
printf("\n Perfect square for %d", c2);
else
printf("\n Not perfect but nearest to :%d :", c2);
return 0;
}
لا أعرف إذا كان هذا قد تم ذكره من قبل.لكنني وجدت الحل هنا:
int result = (int)(floor(sqrt(b)) - ceil(sqrt(a)) + 1);
إذا كانت السرعة مصدر قلق، فلماذا لا يتم تقسيم مجموعة المدخلات الأكثر استخدامًا وقيمها إلى جدول بحث ثم القيام بأي خوارزمية سحرية محسنة توصلت إليها للحالات الاستثنائية؟
يجب أن يكون من الممكن حزم "لا يمكن أن يكون مربعًا مثاليًا إذا كانت أرقام X الأخيرة هي N" بكفاءة أكبر بكثير من ذلك!سأستخدم Java 32 بت int، وأنتج بيانات كافية للتحقق من آخر 16 بت من الرقم - أي 2048 قيمة int سداسية عشرية.
...
نعم.إما أنني واجهت بعض نظريات الأعداد التي تفوق قدراتي قليلاً، أو أن هناك خطأً في الكود الخاص بي.على أية حال، إليك الكود:
public static void main(String[] args) {
final int BITS = 16;
BitSet foo = new BitSet();
for(int i = 0; i< (1<<BITS); i++) {
int sq = (i*i);
sq = sq & ((1<<BITS)-1);
foo.set(sq);
}
System.out.println("int[] mayBeASquare = {");
for(int i = 0; i< 1<<(BITS-5); i++) {
int kk = 0;
for(int j = 0; j<32; j++) {
if(foo.get((i << 5) | j)) {
kk |= 1<<j;
}
}
System.out.print("0x" + Integer.toHexString(kk) + ", ");
if(i%8 == 7) System.out.println();
}
System.out.println("};");
}
وهنا النتائج:
(إد:تم حذفه بسبب ضعف الأداء في prettify.js؛عرض سجل المراجعة لنرى.)
هذه هي الطريقة الأبسط والأكثر إيجازًا، على الرغم من أنني لا أعرف كيف يمكن مقارنتها من حيث دورات وحدة المعالجة المركزية.يعمل هذا بشكل رائع إذا كنت ترغب فقط في معرفة ما إذا كان الجذر عددًا صحيحًا.إذا كنت تهتم حقًا بما إذا كان عددًا صحيحًا، فيمكنك أيضًا معرفة ذلك.إليك وظيفة بسيطة (ونقية):
public static boolean isRootWhole(double number) {
return Math.sqrt(number) % 1 == 0;
}
إذا لم تكن بحاجة إلى تحسين دقيق، فهذه الإجابة أفضل من حيث البساطة وقابلية الصيانة.إذا كنت ستحصل على أرقام سالبة، فربما تريد استخدام Math.abs() في وسيطة الرقم كوسيطة Math.sqrt().
على وحدة المعالجة المركزية Intel i7-4790 بتردد 3.6 جيجا هرتز، استغرق تشغيل هذه الخوارزمية على سرعة 0 - 10000000 ما متوسطه 35 - 37 نانو ثانية لكل عملية حسابية.لقد أجريت 10 عمليات تشغيل متتابعة، وطبعت متوسط الوقت المستغرق في كل عملية حسابية من حسابات العشرة ملايين مربع مربع.استغرق كل تشغيل إجمالي ما يزيد قليلاً عن 600 مللي ثانية لإكماله.
إذا كنت تقوم بإجراء عدد أقل من العمليات الحسابية، فستستغرق العمليات الحسابية السابقة وقتًا أطول قليلاً.
هنا هو الحل فرق تسد.
إذا كان الجذر التربيعي لعدد طبيعي (number) هو عدد طبيعي (solution)، يمكنك بسهولة تحديد نطاق لـ solution على أساس عدد أرقام number:
numberيحتوي على رقم واحد:solutionفي النطاق = 1 - 4numberيحتوي على رقمين:solutionفي النطاق = 3 - 10numberلديه 3 أرقام:solutionفي النطاق = 10 - 40numberلديه 4 أرقام:solutionفي النطاق = 30 - 100numberلديه 5 أرقام:solutionفي النطاق = 100 - 400
لاحظ التكرار؟
يمكنك استخدام هذا النطاق في أسلوب البحث الثنائي لمعرفة ما إذا كان هناك solution لأي منهم:
number == solution * solution
هنا هو الرمز
هنا صفي SquareRootChecker
public class SquareRootChecker {
private long number;
private long initialLow;
private long initialHigh;
public SquareRootChecker(long number) {
this.number = number;
initialLow = 1;
initialHigh = 4;
if (Long.toString(number).length() % 2 == 0) {
initialLow = 3;
initialHigh = 10;
}
for (long i = 0; i < Long.toString(number).length() / 2; i++) {
initialLow *= 10;
initialHigh *= 10;
}
if (Long.toString(number).length() % 2 == 0) {
initialLow /= 10;
initialHigh /=10;
}
}
public boolean checkSquareRoot() {
return findSquareRoot(initialLow, initialHigh, number);
}
private boolean findSquareRoot(long low, long high, long number) {
long check = low + (high - low) / 2;
if (high >= low) {
if (number == check * check) {
return true;
}
else if (number < check * check) {
high = check - 1;
return findSquareRoot(low, high, number);
}
else {
low = check + 1;
return findSquareRoot(low, high, number);
}
}
return false;
}
}
وهنا مثال على كيفية استخدامه.
long number = 1234567;
long square = number * number;
SquareRootChecker squareRootChecker = new SquareRootChecker(square);
System.out.println(square + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677489: true"
long notSquare = square + 1;
squareRootChecker = new SquareRootChecker(notSquare);
System.out.println(notSquare + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677490: false"
إذا كنت تريد السرعة، نظرًا لأن الأعداد الصحيحة الخاصة بك ذات حجم محدود، أعتقد أن الطريقة الأسرع ستتضمن (أ) تقسيم المعلمات حسب الحجم (على سبيل المثال:إلى فئات حسب أكبر مجموعة بت)، ثم التحقق من القيمة مقابل مجموعة من المربعات المثالية ضمن هذا النطاق.
فيما يتعلق بطريقة كارماك، يبدو أنه سيكون من السهل جدًا التكرار مرة أخرى، وهو ما يجب أن يضاعف عدد أرقام الدقة.إنها، في النهاية، طريقة تكرارية مبتورة للغاية - طريقة نيوتن، مع تخمين أولي جيد جدًا.
فيما يتعلق بأفضل ما لديك حاليًا، أرى تحسينين صغيرين:
- نقل الشيك مقابل.0 بعد التحقق باستخدام mod255
- أعد ترتيب قوى القسمة على الأربعة لتخطي جميع عمليات التحقق للحالة المعتادة (75%).
أي:
// Divide out powers of 4 using binary search
if((n & 0x3L) == 0) {
n >>=2;
if((n & 0xffffffffL) == 0)
n >>= 32;
if((n & 0xffffL) == 0)
n >>= 16;
if((n & 0xffL) == 0)
n >>= 8;
if((n & 0xfL) == 0)
n >>= 4;
if((n & 0x3L) == 0)
n >>= 2;
}
والأفضل من ذلك قد يكون بسيطًا
while ((n & 0x03L) == 0) n >>= 2;
ومن الواضح أنه سيكون من المثير للاهتمام معرفة عدد الأعداد التي يتم إعدامها عند كل نقطة تفتيش - فأنا أشك في أن تكون عمليات التفتيش مستقلة حقًا، مما يجعل الأمور صعبة.
"أنا أبحث عن أسرع طريقة لتحديد ما إذا كانت القيمة الطويلة هي مربع كامل (أي.جذره التربيعي هو عدد صحيح آخر)."
الإجابات مثيرة للإعجاب، لكنني فشلت في رؤية فحص بسيط:
تحقق مما إذا كان الرقم الأول الموجود على يمين الطول هو عضو في المجموعة (0,1,4,5,6,9) .إذا لم يكن الأمر كذلك، فمن غير الممكن أن يكون "مربعًا مثاليًا".
على سبيل المثال.
4567 - لا يمكن أن يكون مربعًا كاملاً.
