〰️ 🏒 🧚🏻 مرة أخرى حول GCD ، الخوارزمية الإقليدية وقليلًا عن تاريخ الخوارزميات بشكل عام. بالطبع مع أمثلة سويفت 👩🏿‍🤝‍👨🏼 ☹️ 🐴

الخوارزميات هي واحدة من المواضيع الرئيسية في البرمجة ، فهي في كل مكان (وخاصة في المقابلات ، هاها).

(هل من الممكن الاستغناء عن زر الأكورديون في مثل هذا المنصب؟)

واحدة من أكثرها شهرة هي الخوارزمية الإقليدية المسماة - ربما الطريقة الأكثر شيوعًا لإيجاد أكبر مقسوم مشترك (GCD) لاثنين من الأعداد الصحيحة غير السالبة. كما أنه غالبًا ما يحب بدء دراسة (وتعلم) الأقسام ذات الصلة في الرياضيات وعلوم الكمبيوتر .

ويعتبر دونالد كنوث ، المؤلف الشهير عن أطروحة " فن البرمجة " (وليس فقط) ، أن الخوارزمية هي الأولى في التاريخ (على الأقل فيما يتعلق بالتعاريف الحديثة). لأنه على الرغم من حقيقة أن الخوارزمية اخترعت واستخدمت من قبل ، في الواقع ، إقليدس ، الذي عاش في القرنين الرابع والثالث. قبل الميلاد (سبق ذكره من قبل أرسطو ، الذي عاش قبل قرن من الزمان) ، يصف إقليدس العملية بشكل متكرر ، وهو ما يتسق مع المعنى الحديث للكلمة.

تعود كلمة "الخوارزمية" ذاتها إلى اسم عالم الرياضيات الفارسي الخوارزمي ، الذي عاش في القرنين الثامن والتاسع. بالفعل م. ولا تعتبر بداية استخدامه بشكل قريب من العصر الحديث إلا في القرن العشرين ، وبشكل أكثر دقة - عقوده الأولى ، صعود تكنولوجيا المعلومات.

الخوارزمية الإقليدية

من أجل الفضول ، أقترح التعرف على الوصف الإقليدي للخوارزمية في تحرير Knuth. انها طويلة جدا ، وبالتالي مخبأة تحت خفض:

وصف خوارزمية إقليدية قريبة من الأصل

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

دع A و C هما رقم صحيح موجب ؛ مطلوب للعثور على GCD الخاصة بهم. إذا كان الرقم A قابلاً للقسمة على C ، فسيكون الرقم C مقسومًا مشتركًا للأرقام C و A ، لأنه يقسم نفسه. ومن الواضح أنه سيكون أكبر مقسوم ، لأنه لا يوجد رقم أكبر من الرقم C الذي يقسم C.

ولكن إذا لم يقسم C بالرقم A ، فسنطرح باستمرار أصغر من الأرقام A و C من الأكبر إلى أن نحصل على رقم يقسم بالكامل الذي تم طرحه سابقًا. يجب أن يحدث هذا عاجلاً أم آجلاً ، لأنه إذا كان الفرق مساويًا للفرق ، فسوف تقسم الوحدة على الطرح السابق.

لنفترض الآن أن E هي الباقي الإيجابية لتقسيم الرقم A على C ؛ اجعل F هو الباقي الإيجابي لتقسيم C على E ودع F يقسم E. بما أن F يقسم E و E يقسم C - F ، يقسم F أيضًا C - F. ولكنه يقسم أيضًا ، لذلك يقسم F على C ، و C تقسم A - E ؛ لذلك ، يقسم F أيضًا A - E ، ولكنه يقسم أيضًا E ؛ لذلك ، يقسم F A. وبالتالي ، F مقسوم مشترك للأرقام A و C.

أؤكد الآن أنها أيضًا أداة GCD. في الواقع ، إذا لم يكن F أكبر مقسوم مشترك للأرقام A و C ، فهناك عدد أكبر من شأنه أن يقسم كلا هذين الرقمين. دع هذا الرقم هو G.

نظرًا لأن الرقم G يقسم الرقم C ، والعدد C يقسم A - E ، يقسم G أيضًا الرقم A - E. ويقسم الرقم G أيضًا الرقم الكلي A ، لذلك يقسم الباقي E. ولكن E يقسم C - F ، لذلك G يقسم أيضا C - F. والرقم G يقسم أيضا العدد كله C ، لأنه يقسم ما تبقى من F ؛ وبالتالي ، فإن عدد أكبر يقسم أصغر ، وهذا أمر مستحيل.

وبالتالي ، لا يوجد رقم أكبر من F الذي يقسم A و C ؛ لذلك ، الرقم F هو GCD.

طبيعية. هذا المنطق يجعل الافتراض واضحًا أن أي عدد يقسم رقمين يقسم أداة GCD الخاصة بهم. وهو المطلوب

يعطي الوصف طريقتين للعثور على أداة GCD - بالطرح والقسمة. في الواقع ، هاتان الطريقتان لتنفيذ الخوارزمية معروفة اليوم على نطاق واسع.

فيما يلي مثال لدالة مكتوبة في Swift تنفذ الطريقة الأولى:

func subtractionGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int { if let simpleGCD = simpleCasesGCD(firstNumber, secondNumber) { return simpleGCD } var firstNumber = firstNumber var secondNumber = secondNumber while firstNumber != 0, secondNumber != 0 { if firstNumber > secondNumber { firstNumber = firstNumber - secondNumber } else { secondNumber = secondNumber - firstNumber } } return firstNumber + secondNumber // One of them is 0. }

هنا ، لإعادة الاستخدام ، من أجل مصلحتي ، أحضرت في وظيفة منفصلة حالات البحث عن GCD ، عندما تكون معروفة فورًا ، دون الحاجة إلى اتباع أي خوارزمية:

 func simpleCasesGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int? { if firstNumber == secondNumber { return firstNumber // Any. } if firstNumber == 0 { return secondNumber } if secondNumber == 0 { return firstNumber } return nil }

(إذا كان رقمان يساويان ، فمن الطبيعي أن تساوي GCD لهما أيضًا. إذا كان أي من الأرقام يساوي صفرًا ، فسيكون GCD مساويًا للرقم الثاني ، لأن الصفر قابل للقسمة على أي رقم (والنتيجة هي بالطبع صفر أيضًا) ).

يمكن استخدام القيم غير السلبية فقط كمدخلات. وفقًا لذلك ، بالنسبة للسالب ، يمكنك استخدام نفس الأساليب ، ولكن مع أخذ الأرقام مودولو. (نعم ، يمكن أن يكون العامل المشترك سالبًا ، لكننا نبحث بشكل خاص عن GCD ، والأرقام الموجبة هي دائمًا أكثر من سالب.)

وهنا قد يبدو مثل تطبيق إصدار الخوارزمية حسب القسمة:

 func divisionGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int { if let simpleGCD = simpleCasesGCD(firstNumber, secondNumber) { return simpleGCD } var firstNumber = firstNumber var secondNumber = secondNumber while firstNumber != 0, secondNumber != 0 { if firstNumber > secondNumber { firstNumber = firstNumber % secondNumber } else { secondNumber = secondNumber % firstNumber } } return firstNumber + secondNumber // One of them is 0. }

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

لمقارنتها بعض الشيء ، قمت بإجراء عدة قياسات باستخدام طريقة القياس الخاصة بي measure(_:) لفئة XCTestCase "الأصلي" لاختبار التعليمات البرمجية في XCTest XCTest Xcode .

كمدخلات ، اعتدت مجموعة من أزواج من الأرقام العشوائية. تم إجراء قياسات ، بالطبع ، باستخدام نفس المجموعة لكل طريقة. أخذت انتشار الأرقام للأزواج من صفر إلى 9999. تم إجراء قياسات لعدد الحسابات (أزواج من الأرقام): واحد ، عشرة ، 100 ، 1000 ، 10000 ، 100000 ، 1،000،000 و 10،000،000. هذا الأخير جعلني أتوقع النتيجة لعدة دقائق ، لذلك قررت ذلك للتوقف.

إليك رمز توليد بسيط للإدخال:

 let pairs = (0..<100).map { _ in (Int.random(in: 0..<10000), Int.random(in: 0..<10000)) } // Generates 100 pairs.

القياس نفسه يبدو ، على سبيل المثال ، مثل هذا:

 func testSubstractionGCDPerformance() { measure() { _ = pairs.map { substractionGCD($0, $1) } } }

وها هي نتائج الإطلاق على جهاز الكمبيوتر الخاص بي:

(الطرح - الطرح ، القسمة - القسمة.)

بشكل عام ، يكون من الواضح جدًا مدى خسارة طريقة الطرح على أجهزة الكمبيوتر الحديثة.

نسخة محسّنة من خوارزمية إقليدس

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

 func improvedDivisionGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int { if let simpleGCD = simpleCasesGCD(firstNumber, secondNumber) { return simpleGCD } var firstNumber = firstNumber var secondNumber = secondNumber while firstNumber != 0, secondNumber != 0 { if firstNumber > secondNumber { let firstNumberClaim = firstNumber % secondNumber if firstNumberClaim > secondNumber / 2 { firstNumber = abs(firstNumberClaim - secondNumber) } else { firstNumber = firstNumberClaim } } else { let secondNumberClaim = secondNumber % firstNumber if secondNumberClaim > firstNumber / 2 { secondNumber = abs(secondNumberClaim - firstNumber) } else { secondNumber = secondNumberClaim } } } return firstNumber + secondNumber // One of them is 0. }

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

(المُحسّن هو الإصدار "المُحسّن".)

أكثر قليلاً عن أهمية الخوارزمية الإقليدية

تحتوي الخوارزمية أيضًا على إصدار هندسي (لإيجاد أكبر مقياس لشريحتين).

تم تعميم الخوارزمية بالطبع للعثور على GCD لأي عدد من الأرقام ، وليس فقط اثنين. باختصار ، الفكرة هي: إذا قمنا بتعيين وظيفة البحث عن GCD المكونة من رقمين على أنها gcd (a ، b) ، فقل GCD من ثلاثة أرقام gcd (a ، b ، c) تساوي gcd (gcd (a ، b) ، c). وهكذا ، بالنسبة لأي عدد من الأرقام ، يتم العثور على GCD من خلال حساب GCD التسلسلي لـ GCD للزوج السابق من الأرقام والرقم التالي. على الرغم من ذلك ، بالطبع ، يتعلق هذا بالبحث عن GCD بشكل عام ، وليس فقط الخوارزمية الإقليدية.

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

خوارزمية الإقليدية

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

باختصار ، تمت صياغة الإجابة ، في الواقع ، بواسطة نظرية Lame المتعلقة بهذه الخوارزمية. سيكون عدد الخطوات في الخوارزمية مساوياً لرقم التسلسل لأقرب رقم فيبوناتشي أكبر ، أصغر رقمين من معلمات الإدخال ناقص 2. باستخدام تدوين رياضي أكثر قليلاً ، ثم إذا كان u> v (و v> 1) ، فسيكون عدد تمريرات الخوارزمية n - 2 لـ v <Fn (Fn هو الأقرب إلى رقم F Fibonacci ، و n هو رقم التسلسل الخاص به).

تنمو أرقام فيبوناتشي أضعافا مضاعفة ، على التوالي ، لدينا وظيفة لوغاريتمية لوقت تنفيذ الخوارزمية (من أصغر رقمين للإدخال).

تظهر نفس الحسابات أن أسوأ بيانات المدخلات للخوارزمية هي رقمان فيبوناتشي متتاليين.

طريقة ثنائية لإيجاد NOD

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

تستند الخوارزمية إلى أربع حقائق:

إذا كان كل من u و v متساويان ، إذن gcd (u، v) = 2 * gcd (u / 2، v / 2)؛
إذا كنت u و v ليست كذلك ، gcd (u، v) = gcd (u / 2، v)؛
gcd (u، v) = gcd (u - v، v) (هذا يتبع من الخوارزمية الإقليدية)؛
إذا كان كل من u و v غريبًا ، فسيكون u - v متساويًا و | u - v | <الحد الأقصى (u ، v)

في ويكيبيديا ، يمكنك رؤية النسخة العودية للخوارزمية (مكتوبة في عدة أسطر بلغات البرمجة الحديثة) ، ولم أعد كتابتها على Swift. وهنا أعطي تطبيقًا تكراريًا:

 func binaryGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int { if let simpleGCD = simpleCasesGCD(firstNumber, secondNumber) { return simpleGCD } var firstNumber = firstNumber var secondNumber = secondNumber var shift = 0 while (firstNumber | secondNumber) & 1 == 0 { shift += 1 firstNumber >>= 1 secondNumber >>= 1 } while firstNumber & 1 == 0 { firstNumber >>= 1 } repeat { while secondNumber & 1 == 0 { secondNumber >>= 1 } if firstNumber > secondNumber { swap(&firstNumber, &secondNumber) } secondNumber -= firstNumber } while secondNumber != 0 return firstNumber << shift }

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

(ثنائي هو خوارزمية ثنائية.)

(أنا لا أستبعد أن الخوارزمية يمكن كتابتها بشكل أكثر كفاءة مما فعلت ، وهذا سيؤثر على النتيجة ، ولكن ماذا نحتاج إلى مترجمين؟؟

بالمناسبة ، هذه الخوارزمية ، التي اكتسبت بلا شك 15 دقيقة من شهرة بالفعل في عصر تكنولوجيا المعلومات (في جزء سابق من الحالي) ، كانت معروفة في الصين القديمة. تم العثور على وصفه في الأعمال التي يعود تاريخها إلى القرن الأول. BC بالطبع ، بعبارات مثل "تقسيم النصف" والطرح. وكذلك في سياق الحد من الكسور.

استنتاج

بأمانة ، مع هذا "البحث" البسيط ، لم أكن لأثبت شيئًا ولم أرغب في تقديم أي استنتاجات ثورية (ولم أكن كذلك). أردت فقط إرضاء فضولي ، والنظر في عمل الطرق المختلفة لحل المشكلة الكلاسيكية ، وتمديد أصابعي قليلاً. ومع ذلك ، آمل أن تكون فضوليًا أيضًا لمراقبة النتائج!