الخوارزمية الثنائية لحساب القاسم المشترك الأكبر

الخوارزمية الثنائية لحساب القاسم المشترك الأكبر، أو خوارزمية GCD الثنائية ، والمعروفة أيضًا باسم خوارزمية Stein أو الخوارزمية الإقليدية الثنائية،[1][2] هي خوارزمية تحسب القاسم المشترك الأكبر لعددين صحيحين غير سالبين. تستخدم هذه الخوارزمية عمليات حسابية أبسط من الخوارزمية الإقليدية التقليدية، حيث يستبدل القسمة بعمليات حسابية مثل الإزاحات والمقارنات والطرح.

تصور استخدام خوارزمية GCD الثنائية للعثور على القاسم المشترك الأكبر (GCD) 36 و24. وبالتالي ، فإن GCD هو 2 2 × 3 = 12.

على الرغم من أن الخوارزمية في شكلها المعاصر قد نُشرت لأول مرة من قبل الفيزيائي والمبرمج جوزيف شتاين في عام 1967،[3] إلا أنها ربما كانت معروفة في القرن الثاني قبل الميلاد في الصين القديمة.[4][5]

الخوارزمية

تقلل الخوارزمية من مشكلة العثور على القاسم المشترك الأكبر (gcd) لرقمين غير سالبين v وu من خلال تطبيق هذه الخطوات بشكل متكرر:

  • gcd(0، v) = v ، لأن كل شيء يقسم الصفر، وv هو أكبر رقم يقسم v. وبالمثل ، فإن gcd(u ، 0) = u .
  • gcd(2u ، 2v) = 2 · gcd(u ، v)
  • gcd(2u ،v) = gcd(u ، v) ، إذا كانت v فردية (2 ليست قاسم مشترك). وبالمثل ، فإن gcd(u ، 2v) = gcd(u ، v) إذا كان u فردية.
  • gcd(u ، v) = gcd(|u −v| ، min(u ، v)) ، إذا كان كل من u وv فرديًا.

  • حيث: gcd تعني القاسم المشترك الأكبر وmin تعني الأصغر

التطبيق

نسخة متكررة في لغة سي

فيما يلي تنفيذ متكرر recursive للخوارزمية في لغة سي. يشبه التطبيق وصف الخوارزمية المذكورة أعلاه، وهو مُحسّن لسهولة القراءة بدلاً من سرعة التنفيذ، على الرغم من أن جميع الاستدعاءات المتكررة باستثناء واحدة هي ذيل متكرر tail recursive.

unsigned int gcd(unsigned int u, unsigned int v)
{
 // Base cases
 //  gcd(n, n) = n
 if (u == v)
 return u;

 //  Identity 1: gcd(0, n) = gcd(n, 0) = n
 if (u == 0)
 return v;
 if (v == 0)
 return u;

 if (u % 2 == 0) { // u is even
 if (v % 2 == 1) // v is odd
 return gcd(u/2, v); // Identity 3
 else // both u and v are even
 return 2 * gcd(u/2, v/2); // Identity 2

 } else { // u is odd
 if (v % 2 == 0) // v is even
 return gcd(u, v/2); // Identity 3

 // Identities 4 and 3 (u and v are odd, so u-v and v-u are known to be even)
 if (u > v)
 return gcd((u - v)/2, v);
 else
 return gcd((v - u)/2, u);
 }
}

نسخة تكرارية في لغة Rust

فيما يلي تنفيذ الخوارزمية في لغة Rust ، مقتبس من uutils. حيث يزيل جميع العوامل المشتركة لـ 2 ، ثم يحسب القاسم المشترك الأكبر GCD للأرقام المتبقية باستخدام الهويات 3 و 4 (identity)، ويجمع بين هذه لتشكيل الإجابة النهائية.

pub fn gcd(mut u: u64, mut v: u64) -> u64 {
 use std::cmp::min;
 use std::mem::swap;

 // Base cases: gcd(n, 0) = gcd(0, n) = n
 if u == 0 {
 return v;
 } else if v == 0 {
 return u;
 }

 // Using identities 2 and 3:
 // gcd(2ⁱ u, 2ʲ v) = 2ᵏ gcd(u, v) with u, v odd and k = min(i, j)
 // 2ᵏ is the greatest power of two that divides both u and v
 let i = u.trailing_zeros();  u >>= i;
 let j = v.trailing_zeros();  v >>= j;
 let k = min(i, j);

 loop {
 // u and v are odd at the start of the loop
 debug_assert!(u % 2 == 1, "u = {} is even", u);
 debug_assert!(v % 2 == 1, "v = {} is even", v);

 // Swap if necessary so u <= v
 if u > v {
 swap(&mut u, &mut v);
 }

 // Using identity 4 (gcd(u, v) = gcd(|v-u|, min(u, v))
 v -= u;

 // Identity 1: gcd(u, 0) = u
 // The shift by k is necessary to add back the 2ᵏ factor that was removed before the loop
 if v == 0 {
 return u << k;
 }

 // Identity 3: gcd(u, 2ʲ v) = gcd(u, v) (u is known to be odd)
 v >>= v.trailing_zeros();
 }
}

يعرض هذا التنفيذ العديد من تحسينات الأداء:

  • جرى تجنب القسمة التجريبية على 2 وذلك بتغيير بت واحد وعدد الأصفار الزائدة الأولية u64 :: trailing_zeros. هذا يؤدي إلى ما يعادل تطبيق الهوية 3 بشكل متكرر، في فترة زمنية أقل بكثير.
  • وُضعت الحلقة لتجنب العمل المتكرر؛ على سبيل المثال، حذف 2 كعامل v تم نقله إلى الجزء الخلفي من الحلقة، وبعد حالة الخروج، حيث من المعروف أن v يكون فرديًا عند دخول الحلقة.
  • جسم الحلقة خالي من الفروع باستثناء حالة الخروج (v == 0) ، حيث أن تبادل u وv (لضمان أن u ≤ v) يتحول إلى حركات شرطية.[6] يمكن أن يكون للفروع التي يصعب التنبؤ بها تأثير سلبي كبير على الأداء.[7] [8]

الكفاءة

تتطلب الخوارزمية خطوات O (n) ، حيث n هو عدد البتات في العدد الأكبر من الرقمين، حيث إن كل خطوتين تقلل واحدًا على الأقل من المعاملات بمقدار 2 على الأقل. تتضمن كل خطوة عددًا قليلاً من العمليات الحسابية (O (1) بثابت صغير) ؛ عند العمل بأرقام بحجم الكلمة word-sized، تُترجم كل عملية حسابية إلى عملية آلة machine operation واحدة، وبالتالي فإن عدد عمليات الآلة يكون في حدود log(max(u, v))

ومع ذلك ، فإن التعقيد المقارب لهذه الخوارزمية هو O(n2)، [9] حيث أن هذه العمليات الحسابية (الطرح والتحويل) تستغرق كل منها وقتًا خطيًا للأرقام ذات الحجم الاختياري (عملية آلة واحدة لكل كلمة من التمثيل). هذا هو نفسه بالنسبة للخوارزمية الإقليدية ، على الرغم من أن التحليل الأكثر دقة الذي أجراه Akhavi وVallée أثبت أن هذه الخوارزمية تستخدم عمليات-بت أقل بنسبة 60٪. [10]

التوسيع

يمكن توسيع خوارزمية GCD الثنائية بعدة طرق ، إما لإخراج معلومات إضافية ، أو التعامل مع أعداد صحيحة كبيرة بشكل عشوائي ، أو لحساب GCDs في مجالات أخرى غير الأعداد الصحيحة.

تناظر خوارزمية GCD الثنائية الممتدة ، الخوارزمية الإقليدية الموسعة، حيث توفر معاملات بيزوت بالإضافة إلى GCD ، أي أن الأعداد الصحيحة a وb بحيث أن a · u + b · v = gcd(u, v).[11] [12] [13]

في حالة الأعداد الصحيحة الكبيرة، فإن أفضل تعقيد مقارب asymptotic complexity هو O (log n M (n)) ، حيث M (n) هي تكلفة ضرب n من البتات ؛ وهذا شبه خطي ، وأصغر بكثير من O (n²) من خوارزمية GCD الثنائية ، على الرغم من أن التطبيقات الملموسة تتفوق فقط على الخوارزميات القديمة للأرقام الأكبر من حوالي 64 كيلو-بت (أي أكبر من 8 × 10 19265). يتحقق ذلك من خلال توسيع خوارزمية GCD الثنائية باستخدام أفكار من خوارزمية Schönhage – Strassen لضرب عدد صحيح سريعًا.[14]

جرى أيضًا توسيع خوارزمية GCD الثنائية لتشمل مجالات أخرى غير الأعداد الطبيعية، مثل الأعداد الصحيحة الغاوسية،[15] وأعداد آيزنشتاين الصحيحة، والحلقات التربيعية، ومجالات العوامل الفريدة الاختيارية.

الوصف التاريخي

عُرفت خوارزمية لحساب GCD المكونة من رقمين في الصين القديمة، في عهد أسرة هان ، كطريقة لتقليل الكسور:

«If possible halve it; otherwise, take the denominator and the numerator, subtract the lesser from the greater, and do that alternately to make them the same. Reduce by the same number.»

العنوان:Fangtian - Land surveying، المصدر:The Nine Chapters on the Mathematical Art.

عبارة "إذا أمكن خفضها إلى النصف" غامضة،[4]

  • إذا كان هذا ينطبق عندما يصبح أي من الأرقام زوجيًا، فإن الخوارزمية هي خوارزمية GCD الثنائية ؛
  • إذا كان هذا ينطبق فقط عندما يكون كلا الرقمين زوجيين، فإن الخوارزمية تكون مشابهة للخوارزمية الإقليدية .

انظر أيضًا

المراجع
  1. Brent, Richard P. (13–15 September 1999). Twenty years' analysis of the Binary Euclidean Algorithm. 1999 Oxford-Microsoft Symposium in honour of Professor Sir Antony Hoare. Oxford. مؤرشف من الأصل في 15 أبريل 2012. الوسيط |CitationClass= تم تجاهله (مساعدة)
  2. Brent, Richard P. (November 1999). Further analysis of the Binary Euclidean algorithm (Technical report). Oxford University Computing Laboratory. arXiv:1303.2772. PRG TR-7-99. الوسيط |CitationClass= تم تجاهله (مساعدة)
  3. Stein, J. (February 1967), "Computational problems associated with Racah algebra", Journal of Computational Physics, 1, صفحات 397–405, Bibcode:1967JCoPh...1..397S, doi:10.1016/0021-9991(67)90047-2, ISSN 0021-9991 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link)
  4. Knuth, Donald (1998), Seminumerical Algorithms, 2 (الطبعة 3rd), Addison-Wesley, ISBN 978-0-201-89684-8 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link)
  5. A bot will complete this citation soon. Click here to jump the queue أرخايف:0910.0095.
  6. Godbolt, Matt. "Compiler Explorer". مؤرشف من الأصل في 04 ديسمبر 2020. اطلع عليه بتاريخ 04 نوفمبر 2020. الوسيط |CitationClass= تم تجاهله (مساعدة)
  7. Kapoor, Rajiv (2009-02-21). "Avoiding the Cost of Branch Misprediction". Intel Developer Zone. مؤرشف من الأصل في 06 نوفمبر 2020. الوسيط |CitationClass= تم تجاهله (مساعدة)
  8. Lemire, Daniel (2019-10-15). "Mispredicted branches can multiply your running times". مؤرشف من الأصل في 12 نوفمبر 2020. الوسيط |CitationClass= تم تجاهله (مساعدة)
  9. "GNU MP 6.1.2: Binary GCD". مؤرشف من الأصل في 05 نوفمبر 2018. الوسيط |CitationClass= تم تجاهله (مساعدة)
  10. Akhavi, Ali; Vallée, Brigitte (2000), "Average Bit-Complexity of Euclidean Algorithms", Proceedings ICALP'00, Lecture Notes Computer Science 1853, صفحات 373–387 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link)
  11. Knuth 1998, answer to exercise 39 of section 4.5.2
  12. Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (October 1996). "§14.4 Greatest Common Divisor Algorithms". Handbook of Applied Cryptography. CRC Press. صفحات 606–610. ISBN 0-8493-8523-7. مؤرشف من الأصل (PDF) في 03 فبراير 2021. اطلع عليه بتاريخ 09 سبتمبر 2017. الوسيط |CitationClass= تم تجاهله (مساعدة)
  13. Cohen, Henri (1993). "Chapter 1 : Fundamental Number-Theoretic Algorithms". A Course In Computational Algebraic Number Theory. 138. شبغنكا. صفحات 17–18. ISBN 0-387-55640-0. مؤرشف من الأصل في 03 مايو 2019. الوسيط |CitationClass= تم تجاهله (مساعدة)
  14. Stehlé, Damien; Zimmermann, Paul (2004), "A binary recursive gcd algorithm" (PDF), Algorithmic number theory, 3076, Springer, Berlin, صفحات 411–425, doi:10.1007/978-3-540-24847-7_31, ISBN 978-3-540-22156-2, MR = 2138011 2138011, INRIA Research Report RR-5050 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
  15. Weilert, André (July 2000). "(1+i)-ary GCD Computation in Z[i] as an Analogue to the Binary GCD Algorithm". Journal of Symbolic Computation. 30 (5): 605–617. doi:10.1006/jsco.2000.0422. الوسيط |CitationClass= تم تجاهله (مساعدة)
  16. Knuth, Donald (1998), Seminumerical Algorithms, 2 (الطبعة 3rd), Addison-Wesley, ISBN 978-0-201-89684-8 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link)
  17. Knuth 1998، صفحة 646, answer to exercise 39 of section 4.5.2
  18. Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (October 1996). "§14.4 Greatest Common Divisor Algorithms". Handbook of Applied Cryptography. CRC Press. صفحات 606–610. ISBN 0-8493-8523-7. مؤرشف من الأصل (PDF) في 03 فبراير 2021. اطلع عليه بتاريخ 09 سبتمبر 2017. الوسيط |CitationClass= تم تجاهله (مساعدة)
  19. Cohen, Henri (1993). "Chapter 1 : Fundamental Number-Theoretic Algorithms". A Course In Computational Algebraic Number Theory. 138. شبغنكا. صفحات 17–18. ISBN 0-387-55640-0. مؤرشف من الأصل في 03 مايو 2019. الوسيط |CitationClass= تم تجاهله (مساعدة)
  20. Stehlé, Damien; Zimmermann, Paul (2004), "A binary recursive gcd algorithm" (PDF), Algorithmic number theory, 3076, Springer, Berlin, صفحات 411–425, CiteSeerX = 10.1.1.107.8612 10.1.1.107.8612, doi:10.1007/978-3-540-24847-7_31, ISBN 978-3-540-22156-2, MR = 2138011 2138011, INRIA Research Report RR-5050 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
  21. Akhavi, Ali; Vallée, Brigitte (2000), "Average Bit-Complexity of Euclidean Algorithms", Proceedings ICALP'00, Lecture Notes Computer Science 1853, صفحات 373–387, CiteSeerX = 10.1.1.42.7616 10.1.1.42.7616, مؤرشف من الأصل في 29 أغسطس 2017 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link)
  22. Weilert, André (July 2000). "(1+i)-ary GCD Computation in Z[i] as an Analogue to the Binary GCD Algorithm". Journal of Symbolic Computation. 30 (5): 605–617. doi:10.1006/jsco.2000.0422. الوسيط |CitationClass= تم تجاهله (مساعدة)
  23. Damgård, Ivan Bjerre; Frandsen, Gudmund Skovbjerg (August 12–15, 2003). Efficient Algorithms for GCD and Cubic Residuosity in the Ring of Eisenstein Integers. 14th International Symposium on the Fundamentals of Computation Theory. مالمو، السويد. صفحات 109–117. doi:10.1007/978-3-540-45077-1_11. الوسيط |CitationClass= تم تجاهله (مساعدة)صيانة CS1: تنسيق التاريخ (link)
  24. Agarwal, Saurabh; Frandsen, Gudmund Skovbjerg (June 13–18, 2004). Binary GCD Like Algorithms for Some Complex Quadratic Rings. Algorithmic Number Theory Symposium. برلينغتون, USA. صفحات 57–71. doi:10.1007/978-3-540-24847-7_4. الوسيط |CitationClass= تم تجاهله (مساعدة)صيانة CS1: تنسيق التاريخ (link)
  25. Agarwal, Saurabh; Frandsen, Gudmund Skovbjerg (March 20–24, 2006). A New GCD Algorithm for Quadratic Number Rings with Unique Factorization. 7th Latin American Symposium on Theoretical Informatics. فالديفيا. صفحات 30–42. doi:10.1007/11682462_8. الوسيط |CitationClass= تم تجاهله (مساعدة)صيانة CS1: تنسيق التاريخ (link)
  26. Wikström, Douglas (July 11–15, 2005). On the l-Ary GCD-Algorithm in Rings of Integers. Automata, Languages and Programming, 32nd International Colloquium. لشبونة، البرتغال. صفحات 1189–1201. doi:10.1007/11523468_96. الوسيط |CitationClass= تم تجاهله (مساعدة)صيانة CS1: تنسيق التاريخ (link)

قراءة متعمقة
  • Knuth, Donald (1998). "§4.5 Rational arithmetic". Seminumerical Algorithms. 2 (الطبعة 3rd). Addison-Wesley. صفحات 330–417. ISBN 978-0-201-89684-8. الوسيط |CitationClass= تم تجاهله (مساعدة)

يغطي GCD الثنائي الممتد ، وتحليل احتمالي للخوارزمية.

يغطي مجموعة متنوعة من الموضوعات ، بما في ذلك خوارزمية GCD الثنائية الموسعة التي تنتج معاملات بيزوت ، والتعامل الفعال مع الأعداد الصحيحة متعددة الدقة باستخدام متغير من خوارزمية Lehmer GCD ، والعلاقة بين GCD والتوسعات المستمرة للكسور للأرقام الحقيقية.

تحليل الخوارزمية في الحالة المتوسطة ، من خلال التحليل الوظيفي : يتم عرض المعاملات الرئيسية للخوارزميات كنظام ديناميكي ، ومتوسط قيمتها مرتبط بالقياس الثابت لمعامل النقل transfer operatorفي النظام.

روابط خارجية
  • بوابة برمجة الحاسوب
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.