الخوارزمية الثنائية لحساب القاسم المشترك الأكبر، أو خوارزمية GCD الثنائية ، والمعروفة أيضًا باسم خوارزمية Stein أو الخوارزمية الإقليدية الثنائية، هي خوارزمية تحسب القاسم المشترك الأكبر لعددين صحيحين غير سالبين. تستخدم هذه الخوارزمية عمليات حسابية أبسط من الخوارزمية الإقليدية التقليدية، حيث يستبدل القسمة بعمليات حسابية مثل الإزاحات والمقارنات والطرح. على الرغم من أن الخوارزمية في شكلها المعاصر قد نُشرت لأول مرة من قبل الفيزيائي والمبرمج جوزيف شتاين في عام 1967، إلا أنها ربما كانت معروفة في القرن الثاني قبل الميلاد في الصين القديمة. الخوارزمية. تقلل الخوارزمية من مشكلة العثور على القاسم المشترك الأكبر (gcd) لرقمين غير سالبين "v" و"u من" خلال تطبيق هذه الخطوات بشكل متكرر: التطبيق. نسخة متكررة في لغة سي. فيما يلي تنفيذ متكرر للخوارزمية في لغة سي. يشبه التطبيق وصف الخوارزمية المذكورة أعلاه، وهو مُحسّن لسهولة القراءة بدلاً من سرعة التنفيذ، على الرغم من أن جميع الاستدعاءات المتكررة باستثناء واحدة هي ذيل متكرر . 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 &gt; 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) -&gt; 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 &lt;= v if u &gt; v { swap(&amp;mut u, &amp;mut v); // Using identity 4 (gcd(u, v) = gcd(|v-u|, min(u, v)) v -= u; //
على الرغم من أن الخوارزمية في شكلها المعاصر قد نُشرت لأول مرة من قبل الفيزيائي والمبرمج جوزيف شتاين
من هو جوزيف شتاين وما هي إسهاماته في مجال الخوارزميات؟

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

فيما يلي تنفيذ متكرر للخوارزمية في لغة سي
كيف يعمل تنفيذ الخوارزمية في لغة سي؟

عمليات حسابية أبسط من الخوارزمية الإقليدية التقليدية
ما هي الميزات التي تميز الخوارزمية الثنائية عن الخوارزمية الإقليدية في حساب القاسم المشترك الأكبر؟

القاسم المشترك الأكبر لعددين صحيحين غير سالبين.
ما هي الخوارزمية الثنائية لحساب القاسم المشترك الأكبر ولماذا تعرف أيضًا باسم خوارزمية Stein؟

القرن الثاني قبل الميلاد
متى كانت تعرف الخوارزمية فى الصين القديمة ؟
