الخوارزمية الثنائية لحساب القاسم المشترك الأكبر
المحتويات
- return gcd(u, v/2); // Identity 3
- الخوارزمية
- التوسيع
- }
- loop {
- نسخة تكرارية في لغة Rust
- }
- }
- return gcd(u/2, v); // Identity 3
- use std::mem::swap;
- الوصف التاريخي
- قراءة متعمقة
- } else { // u is odd
- return u;
- نسخة متكررة في لغة سي
- // gcd(n, n) = n
- Cut-the-Knot: خوارزمية Euclid الثنائية في cut-the-knot
- الكفاءة
- // Identity 1: gcd(u, 0) = u
- return v;
- return u;

على سبيل التعريف، الخوارزمية الثنائية لحساب القاسم المشترك الأكبر، أو خوارزمية GCD الثنائية ، والمعروفة كذلك باسم خوارزمية Stein أو الخوارزمية الإقليدية الثنائية، هي خوارزمية تحسب القاسم المشترك الأكبر لعددين صحيحين غير سالبين. تستعمل هذه الخوارزمية عمليات حسابية أبسط من الخوارزمية الإقليدية التقليدية، حيث يستبدل القسمة بعمليات حسابية مثل الإزاحات والمقارنات والطرح. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
كذلك، على الرغم من أن الخوارزمية في شكلها المعاصر قد نُشرت لأول مرة من قبل الفيزيائي والمبرمج جوزيف شتاين في سنة 1967، إلا أنها ربما كانت معروفة في القرن الثاني قبل الميلاد في الصين القديمة.
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);
- }
- }
الخوارزمية
وفي هذا الصدد، gcd(0، v) = v ، لأن كل شيء يقسم الصفر، وv هو أكبر رقم يقسم v. وبالمثل، فإن gcd(u ، 0) = u .
من جهة ثانية، gcd(2u ،v) = gcd(u ، v) ، إذا كانت v فردية (2 ليست قاسم مشترك). وبالمثل، فإن gcd(u ، 2v) = gcd(u ، v) إذا كان u فردية.
التطبيق
حيث: gcd تعني القاسم المشترك الأكبر وmin تعني الأصغر
gcd(2u ، 2v) = 2 · gcd(u ، v)
كذلك، تقلل الخوارزمية من مشكلة العثور على القاسم المشترك الأكبر (gcd) لرقمين غير سالبين v وu من خلال تطبيق هذه الخطوات بشكل متكرر:
التوسيع
وفي هذا الصدد، جرى كذلك توسيع خوارزمية GCD الثنائية لتشمل مجالات أخرى غير الأعداد الطبيعية، مثل الأعداد الصحيحة الغاوسية، وأعداد آيزنشتاين الصحيحة، والحلقات التربيعية، ومجالات العوامل الفريدة الاختيارية.
وعلى صعيد آخر، في حالة الأعداد الصحيحة الكبيرة، فإن أفضل تعقيد مقارب asymptotic complexity هو O (log n M (n)) ، حيث M (n) هي تكلفة ضرب n من البتات ؛ وهذا شبه خطي، وأصغر بكثير من O (n²) من خوارزمية GCD الثنائية، على الرغم من أن التطبيقات الملموسة تتفوق فقط على الخوارزميات القديمة للأرقام الأكبر من نحو 64 كيلو-بت (أي أكبر من 8 × 10 19265). يتحقق ذلك من خلال توسيع خوارزمية GCD الثنائية باستخدام أفكار من خوارزمية Schönhage – Strassen لضرب عدد صحيح سريعًا.
وفي هذا السياق، يمكن توسيع خوارزمية GCD الثنائية بعدة طرق، إما لإخراج معلومات إضافية، أو التعامل مع أعداد صحيحة كبيرة بشكل عشوائي ، أو لحساب GCDs في مجالات أخرى غير الأعداد الصحيحة.
من جانب آخر، تناظر خوارزمية GCD الثنائية الممتدة ، الخوارزمية الإقليدية الموسعة، حيث توفر معاملات بيزوت إلى جانب GCD ، أي أن الأعداد الصحيحة a وb بحيث أن a · u + b · v = gcd(u, v).
}
v >>= v.trailing_zeros;
من جهة ثانية، // Identity 3: gcd(u, 2ʲ v) = gcd(u, v) (u is known to be odd)
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);
- }
- v -= u;
نسخة تكرارية في لغة Rust
وفي هذا الصدد، فيما يلي تنفيذ الخوارزمية في لغة Rust ، مقتبس من uutils . حيث يزيل جميع العوامل المشتركة لـ 2 ، ثم يحسب القاسم المشترك الأكبر GCD للأرقام المتبقية باستخدام الهويات 3 و 4 (identity)، ويجمع بين هذه لتشكيل الإجابة النهائية.pub fn gcd(mut u: u64, mut v: u64) -> u64 {
use std::cmp::min;
}
- // 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);
}
وفي السياق ذاته، جرى تجنب القسمة التجريبية على 2 وذلك بتغيير بت واحد وعدد الأصفار الزائدة الأولية u64 :: trailing_zeros . هذا يؤدي إلى ما يعادل تطبيق الهوية 3 بشكل متكرر، في فترة زمنية أقل بكثير.
وفي هذا السياق، جسم الحلقة خالي من الفروع باستثناء حالة الخروج (v == 0) ، حيث أن تبادل u وv (لضمان أن u ≤ v) يتحول إلى حركات شرطية. يمكن أن يكون للفروع التي يصعب التنبؤ بها تأثير سلبي كبير على الأداء.
}يعرض هذا التنفيذ الكثير من تحسينات الأداء:
ومن جهة أخرى، وُضعت الحلقة لتجنب العمل المتكرر؛ مثلًا، حذف 2 كعامل v تم نقله إلى الجزء الخلفي من الحلقة، وبعد حالة الخروج، حيث من المعروف أن v يكون فرديًا عند دخول الحلقة.
return gcd(u/2, v); // Identity 3
else // both u and v are even
return 2 * gcd(u/2, v/2); // Identity 2
use std::mem::swap;
- // Base cases: gcd(n, 0) = gcd(0, n) = n
- if u == 0 {
- return v;
- } else if v == 0 {
- return u;
الوصف التاريخي
من جانب آخر، إذا كان هذا ينطبق عندما يصبح أي من الأرقام زوجيًا، فإن الخوارزمية هي خوارزمية GCD الثنائية ؛
وفي السياق ذاته، العنوان:Fangtian - Land surveying، المصدر:The Nine Chapters on the Mathematical Art.
عبارة «إذا أمكن خفضها إلى النصف» غامضة،
في هذا الإطار، عُرفت خوارزمية لحساب GCD المكونة من رقمين في الصين القديمة، في عهد أسرة هان ، كطريقة لتقليل الكسور:
كذلك، إذا كان هذا ينطبق فقط عندما يكون كلا الرقمين زوجيين، فإن الخوارزمية تكون مشابهة للخوارزمية الإقليدية .
- انظر كذلك
- الخوارزمية الإقليدية
- خوارزمية إقليدية ممتدة
- أقل مضاعف مشترك
قراءة متعمقة
وفي هذا السياق، يغطي مجموعة متنوعة من الموضوعات، بما في ذلك خوارزمية GCD الثنائية الموسعة التي تنتج معاملات بيزوت ، والتعامل الفعال مع الأعداد الصحيحة متعددة الدقة باستخدام متغير من خوارزمية Lehmer GCD ، والعلاقة بين GCD والتوسعات المستمرة للكسور للأرقام الحقيقية.
وفي هذا السياق، تحليل الخوارزمية في الحالة المتوسطة، من خلال التحليل الوظيفي : يتم عرض المعاملات الرئيسية للخوارزميات كنظام ديناميكي ، ومتوسط قيمتها مرتبط بالقياس الثابت لمعامل النقل transfer operatorفي النظام.
يغطي GCD الثنائي الممتد، وتحليل احتمالي للخوارزمية.
} else { // u is odd
if (v % 2 == 0) // v is even
return u;
if (u == 0)
// Identity 1: gcd(0, n) = gcd(n, 0) = n
نسخة متكررة في لغة سي
// Base cases
ومن جهة أخرى، فيما يلي تنفيذ متكرر recursive للخوارزمية في لغة سي. يشبه التطبيق وصف الخوارزمية المذكورة أعلاه، وهو مُحسّن لسهولة القراءة بدلاً من سرعة التنفيذ، على الرغم من أن جميع الاستدعاءات المتكررة باستثناء واحدة هي ذيل متكرر tail recursive.unsigned int gcd(unsigned int u, unsigned int v)
{
// gcd(n, n) = n
if (u == v)
Cut-the-Knot: خوارزمية Euclid الثنائية في cut-the-knot
من جانب آخر، تحليل الخوارزمية الإقليدية الثنائية (1976) ، بحث بقلم ريتشارد ب. برنت ، بما في ذلك متغير باستخدام الإزاحات اليسرى
الكفاءة
من جانب آخر، ومع ذلك، فإن التعقيد المقارب لهذه الخوارزمية هو O(n2)، حيث أن هذه العمليات الحسابية (الطرح والتحويل) تستغرق كل منها وقتًا خطيًا للأرقام ذات الحجم الاختياري (عملية آلة واحدة لكل كلمة من التمثيل). هذا هو نفسه بالنسبة للخوارزمية الإقليدية، على الرغم من أن التحليل الأكثر دقة الذي أجراه Akhavi وVallée أثبت أن هذه الخوارزمية تستعمل عمليات-بت أقل بنسبة 60٪.
وفي السياق ذاته، تتطلب الخوارزمية خطوات O (n) ، حيث n هو عدد البتات في العدد الأكبر من الرقمين، حيث إن كل خطوتين تقلل واحدًا على الأقل من المعاملات بمقدار 2 على الأقل. تتضمن كل خطوة عددًا قليلاً من العمليات الحسابية (O (1) بثابت صغير) ؛ عند العمل بأرقام بحجم الكلمة word-sized، تُترجم كل عملية حسابية إلى عملية آلة machine operation واحدة، وبالتالي فإن عدد عمليات الآلة يكون في حدود log(max(u, v))
// Identity 1: gcd(u, 0) = u
إضافةً إلى ذلك، // The shift by k is necessary to add back the 2ᵏ factor that was removed before the loop
return u << k;
if v == 0 {
return v;
if (v == 0)
return u;
if (u % 2 == 0) { // u is even
if (v % 2 == 1) // v is odd
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟