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

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

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

تجد الخوارزمية القاسم المشترك الأكبر لعددين غير سالبين${\displaystyle u}$و${\displaystyle v}$من خلال تطبيق هذه المتطابقات بشكل متكرر:

1. ${\displaystyle \gcd(u,0)=u}$كل شيء يقسم الصفر، و${\displaystyle u}$هو أكبر عدد يقسم${\displaystyle u}$.
2. ${\displaystyle \gcd(2u,2v)=2\cdot \gcd(u,v)}$:${\displaystyle 2}$هو قاسم مشترك.
3. ${\displaystyle \gcd(u,2v)=\gcd(u,v)}$لو${\displaystyle u}$غريب:${\displaystyle 2}$إذن فهو ليس قاسمًا مشتركًا.
4. ${\displaystyle \gcd(u,v)=\gcd(u,vu)}$لو${\displaystyle u,v}$غريب و${\displaystyle u\leq v}$.

بما أن القاسم المشترك الأكبر تبادلي (${\displaystyle \gcd(u,v)=\gcd(v,u)}$)، تظل تلك المتطابقات سارية حتى في حالة تبديل المعاملات:${\displaystyle \gcd(0,v)=v}$،${\displaystyle \gcd(2u,v)=\gcd(u,v)}$لو${\displaystyle v}$غريب، إلخ.

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

• تجنب التقسيم التجريبي المتكرر بواسطة${\displaystyle 2}$لصالح عملية العد البدائية للأصفار اللاحقة وإزاحة بت واحد ، وهو ما يعادل وظيفيًا تطبيق الهوية 3 بشكل متكرر، ولكنه أسرع بكثير؛
• التعبير عن الخوارزمية بشكل تكراري بدلاً من التكراري : يمكن تصميم التنفيذ الناتج لتجنب العمل المتكرر، وذلك باستدعاء المتطابقة  2 في البداية والحفاظ على أن كلا العددين فرديان عند دخول الحلقة، والتي تحتاج فقط إلى تنفيذ المتطابقتين 3 و4؛ و
• جعل جسم الحلقة خالياً من التفرعات باستثناء شرط الخروج : يمكن أن يكون للتفرعات غير المتوقعة تأثير سلبي كبير على الأداء. ^{[ 5 ] [ 6 ]}v==0

فيما يلي تطبيق للخوارزمية بلغة C.

// عدّ الأصفار اللاحقة. هذا مثال تعليمي فقط؛ // لتحسين الأداء، استخدم __builtin_ctzll() أو ما شابه. static int ctz ( uint64_t n ) { int s = 0 , t ; while (( t = n & 15 ) == 0 ) { n >>= 4 ; s += 4 ; } return s + (( 0x12131210 >> 2 * t ) & 3 ); } uint64_t gcd ( uint64_t u , uint64_t v ) { if ( ! u || ! v ) return u | v ; // العنصر المحايد رقم 1 int shift = ctz ( u | v ); u >>= ctz ( u ); uint64_t min , max ; while ( v ) { v >>= ctz ( v ); // العنصر المحايد رقم 3 min = ( u < v ) ? u : v ; // المتطابقة رقم 4 max = ( u > v ) ? u : v ; u = min ; v = max - min ; } return u << shift ; // المتطابقة رقم 2 }

فيما يلي تطبيق للخوارزمية بلغة Rust يوضح تلك الاختلافات، وهو مقتبس من uutils . التبادل الشرطي لـ${\displaystyle u}$و${\displaystyle v}$(ضمان${\displaystyle u\leq v}$) يتم تجميعها إلى حركات مشروطة ؛ ^{[ 7 ]} :

pub fn gcd ( mut u : u64 , mut v : u64 ) -> u64 { // الحالات الأساسية: gcd(n, 0) = gcd(0, n) = n if u == 0 { return v ; } else if v == 0 { return u ; }// باستخدام المتطابقتين 2 و3: // القاسم المشترك الأكبر (2ⁱ u, 2ʲ v) = 2ᵏ القاسم المشترك الأكبر (u, v) حيث u وv عددان فرديان و k = min(i, j) // 2ᵏ هو أكبر قوة للعدد 2 تقسم كلاً من 2ⁱ u و2ʲ v let i = u.trailing_zeros ( ) ; u >>= i ; let j = v.trailing_zeros ( ) ; v >>= j ; let k = i.min ( j ) ;حلقة { // u و v عددان فرديان في بداية الحلقة debug_assert! ( u % 2 == 1 , "u = {} يجب أن يكون عددًا فرديًا" , u ); debug_assert! ( v % 2 == 1 , "v = {} يجب أن يكون عددًا فرديًا" , v );// قم بالتبديل إذا لزم الأمر بحيث يكون u ≤ v إذا كان u > v { ( u , v ) = ( v , u ); }// المتطابقة 4: القاسم المشترك الأكبر (u, v) = القاسم المشترك الأكبر (u, vu) لأن u ≤ v و u و v كلاهما فرديان v -= u ; // v الآن زوجيإذا كانت قيمة v تساوي صفرًا { // العنصر المحايد 1: القاسم المشترك الأكبر (u, 0) = u // الإزاحة بمقدار k ضرورية لإعادة إضافة العامل 2ᵏ الذي تم حذفه قبل الحلقة return u << k ; }// المتطابقة 3: القاسم المشترك الأكبر (u, 2ʲ v) = القاسم المشترك الأكبر (u, v) لأن u عدد فردي ، v >> = v.trailing_zeros (); } }

ملاحظة : يقبل التطبيق أعلاه أعدادًا صحيحة غير سالبة؛ مع العلم أن${\displaystyle \gcd(u,v)=\gcd(\pm {}u,\pm {}v)}$يمكن التعامل مع الحالة الموقعة على النحو التالي:

/// يحسب القاسم المشترك الأكبر لعددين صحيحين مُوقّعين من 64 بت /// النتيجة غير مُوقّعة، ولا يمكن تمثيلها دائمًا كـ i64: gcd(i64::MIN, i64::MIN) == 1 << 63 pub fn signed_gcd ( u : i64 , v : i64 ) -> u64 { gcd ( u . unsigned_abs (), v . unsigned_abs ()) }

يتطلب الخوارزمية، من الناحية التقاربية ،${\displaystyle O(n)}$خطوات، حيث${\displaystyle n}$يمثل عدد البتات في العدد الأكبر من العددين، حيث أن كل خطوتين تقللان أحد المعاملات على الأقل بمعامل واحد على الأقل من${\displaystyle 2}$تتضمن كل خطوة بضع عمليات حسابية فقط (${\displaystyle O(1)}$(مع ثابت صغير)؛ عند التعامل مع أرقام بحجم الكلمات ، تُترجم كل عملية حسابية إلى عملية آلة واحدة، لذا فإن عدد عمليات الآلة يكون في حدود${\displaystyle n}$، أي${\displaystyle \log _{2}(\max(u,v))}$.

بالنسبة للأعداد الكبيرة بشكل تعسفي، فإن التعقيد التقاربي لهذه الخوارزمية هو${\displaystyle O(n^{2})}$[ ^{8 ]} بما أن كل عملية حسابية (الطرح والإزاحة) تتضمن عددًا خطيًا من عمليات الآلة (عملية واحدة لكل كلمة في التمثيل الثنائي للأعداد). إذا أمكن تمثيل الأعداد في ذاكرة الآلة، أي إذا ^أمكن تمثيل حجم كل عدد بكلمة آلة واحدة، فإن هذا الحد يتقلص إلى: $${\displaystyle O\left({\frac {n^{2}}{\log _{2}n}}\right)}$$

وهذا ينطبق أيضاً على خوارزمية إقليدس، على الرغم من أن تحليلاً أكثر دقة أجراه أخافي وفالي أثبت أن القاسم المشترك الأكبر الثنائي يستخدم عمليات بت أقل بنسبة 60% تقريباً. ^{[ 9 ]}

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

تتناسب خوارزمية القاسم المشترك الأكبر الثنائي الموسعة ، المشابهة لخوارزمية إقليدس الموسعة ، مع النوع الأول من التوسيع، حيث أنها توفر معاملات بيزو بالإضافة إلى القاسم المشترك الأكبر: أعداد صحيحة.${\displaystyle a}$و${\displaystyle b}$بحيث${\displaystyle a\cdot {}u+b\cdot {}v=\gcd(u,v)}$[ ^{10 ] [ 11 ] [ 12 ]​}

في حالة الأعداد الصحيحة الكبيرة، يكون أفضل تعقيد تقاربي هو${\displaystyle O(M(n)\log n)}$، مع${\displaystyle M(n)}$تكلفة${\displaystyle n}$الضرب الثنائي؛ هذه العملية شبه خطية وأصغر بكثير من خوارزمية القاسم المشترك الأكبر الثنائية${\displaystyle O(n^{2})}$مع ذلك، لا تتفوق التطبيقات العملية على الخوارزميات القديمة إلا للأعداد الأكبر من 64 كيلوبت تقريبًا ( أي أكبر من 8 × 10^ ¹⁹²⁶⁵ ). ويتحقق ذلك بتوسيع خوارزمية القاسم المشترك الأكبر الثنائية باستخدام أفكار من خوارزمية شونهاج-ستراسن لضرب الأعداد الصحيحة بسرعة. ^{[ 13 ]}

تم توسيع خوارزمية القاسم المشترك الأكبر الثنائي لتشمل مجالات أخرى غير الأعداد الطبيعية، مثل الأعداد الصحيحة الغاوسية ، ^{[ 14 ]} وأعداد أيزنشتاين ، ^{[ 15 ]} والحلقات التربيعية، ^{[ 16 ] [ 17 ]} وحلقات الأعداد الصحيحة لحقول الأعداد . ^{[ 18 ]}

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

إن أمكن، قسّم الناتج على اثنين؛ وإلا، خذ المقام والبسط، واطرح الأصغر من الأكبر، وكرر ذلك بالتناوب حتى يصبح الناتج متساوياً. ثم اطرح نفس العدد من البسط والمقام.

عبارة "إن أمكن، قم بتقسيمها إلى النصف" غامضة، ^{[ 4 ]}

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

• خوارزمية إقليدية
• خوارزمية إقليدية موسعة
• المضاعف المشترك الأصغر

• كنوت، دونالد (1998). "الفقرة 4.5 الحساب الكسري". الخوارزميات شبه العددية . فن برمجة الحاسوب . المجلد  2 (  الطبعة الثالثة). أديسون-ويسلي. الصفحات 330-417 . ISBN  978-0-201-89684-8.

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

• كوهين، هنري (1993). "الفصل 1  : الخوارزميات الأساسية لنظرية الأعداد". دورة في نظرية الأعداد الجبرية الحاسوبية . نصوص الدراسات العليا في الرياضيات . المجلد  138. سبرينغر-فيرلاغ . الصفحات 12-24 . ISBN  0-387-55640-0.

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

• فالي، بريجيت (سبتمبر-أكتوبر 1998). "ديناميكيات خوارزمية إقليدس الثنائية: التحليل الوظيفي والمؤثرات" . مجلة Algorithmica . 22 (4): 660-685 . doi : 10.1007/PL00009246 . S2CID 27441335. مؤرشف من الأصل (PS) في 13 مايو 2011. 

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

• قاموس المعهد الوطني للمعايير والتكنولوجيا للخوارزميات وهياكل البيانات: خوارزمية القاسم المشترك الأكبر الثنائي
• خوارزمية قطع العقدة: خوارزمية إقليدس الثنائية على موقع cut-the-knot
• تحليل خوارزمية إقليدس الثنائية (1976)، وهي ورقة بحثية لريتشارد ب. برنت ، تتضمن صيغة معدلة تستخدم الإزاحات إلى اليسار.