🎣 🌅 👃🏿 जीसीडी के बारे में एक बार फिर, यूक्लिडियन एल्गोरिथ्म और सामान्य रूप से एल्गोरिदम के इतिहास के बारे में थोड़ा सा। बेशक स्विफ्ट उदाहरणों के साथ 💬 😴 🧙🏼

एल्गोरिदम प्रोग्रामिंग में केंद्रीय विषयों में से एक है , वे हर जगह हैं (विशेष रूप से साक्षात्कार, हाहा में)।

(क्या इस तरह के पोस्ट में बटन समझौते के बिना करना संभव है?)

सबसे प्रसिद्ध में से एक तथाकथित यूक्लिडियन एल्गोरिथ्म है - दो गैर-नकारात्मक पूर्णांकों के सबसे बड़े सामान्य भाजक (GCD) को खोजने का शायद सबसे आम तरीका है। वह अक्सर गणित और कंप्यूटर विज्ञान के प्रासंगिक वर्गों का अध्ययन (और सीखना) शुरू करना पसंद करते हैं।

और डोनाल्ड नॉथ , ग्रंथ के कुख्यात लेखक " प्रोग्रामिंग की कला " (और न केवल), यहां तक कि एल्गोरिथ्म को इतिहास में पहला (कम से कम आधुनिक परिभाषाओं के संबंध में) मानता है। क्योंकि, इस तथ्य के बावजूद कि एल्गोरिथ्म का आविष्कार किया गया था और पहले इस्तेमाल किया गया था, वास्तव में, यूक्लिड , जो IV-III शताब्दियों में रहते थे। ईसा पूर्व (यह पहले से ही अरस्तू द्वारा उल्लेख किया गया था, जो एक सदी पहले रहते थे), यूक्लिड ने प्रक्रिया का पुनरावृत्त रूप से वर्णन किया है, जो शब्द के आधुनिक अर्थ के अनुरूप है।

"अल्गोरिथम" शब्द फारसी गणितज्ञ अल-ख्वारिज़मी के नाम पर वापस जाता है, जो आठवीं-नौवीं शताब्दी के आसपास रहता था। पहले से ही ए.डी. और आधुनिक एक के करीब एक अर्थ में इसके उपयोग की शुरुआत को केवल 20 वीं शताब्दी माना जाता है, अधिक सटीक रूप से - इसके पहले दशक, सूचना प्रौद्योगिकी का उदय।

यूक्लिडियन एल्गोरिथ्म

जिज्ञासा के लिए, मेरा सुझाव है कि आप नथ के संपादन में एल्गोरिथ्म के यूक्लिडियन विवरण के साथ खुद को परिचित करें। यह काफी लंबा है, इसलिए कट के नीचे छिपा हुआ है:

यूक्लिडियन एल्गोरिथ्म विवरण मूल के करीब है

प्रस्ताव। दिए गए दो सकारात्मक पूर्णांकों के लिए, उनके सबसे बड़े सामान्य भाजक को खोजें।

A और C को दो पूर्णांक पूर्णांक दिए गए हैं; उनके GCD को खोजना आवश्यक है। यदि संख्या A C से विभाज्य है, तो संख्या C C और A का एक सामान्य विभाजक है, क्योंकि यह स्वयं को विभाजित करता है। और जाहिर है, यह सबसे बड़ा विभाजक होगा, क्योंकि सी को विभाजित करने वाली संख्या सी से बड़ी कोई संख्या नहीं है।

लेकिन अगर C नंबर A को विभाजित नहीं करता है, तो हम लगातार संख्या A और C के छोटे को बड़े से घटाएंगे जब तक कि हमें एक संख्या नहीं मिलती है जो पिछले घटाए गए भाग को पूरी तरह से विभाजित करती है। यह जल्दी या बाद में होना चाहिए, क्योंकि यदि अंतर एक के बराबर है, तो यूनिट पिछले घटाए गए हिस्से को विभाजित करेगा।

अब मान लीजिए कि E, C द्वारा संख्या A को विभाजित करने का सकारात्मक शेष है; F को E से C को विभाजित करने का सकारात्मक शेष है और F को E से विभाजित करते हैं। चूंकि F, E और E को विभाजित करता है C - F, F को भी C - F से विभाजित करता है। लेकिन यह स्वयं को भी विभाजित करता है, इसलिए F को C से विभाजित करता है, और सी ए - ई को विभाजित करता है; इसलिए, एफ भी ए - ई को विभाजित करता है, लेकिन यह भी ई को विभाजित करता है; इसलिए, F, A को विभाजित करता है। परिणामस्वरूप, F, A और C की संख्या का एक सामान्य विभाजक है।

अब मैं पुष्टि करता हूं कि यह जीसीडी भी है। वास्तव में, यदि F, A और C की सबसे बड़ी सामान्य भाजक नहीं है, तो एक बड़ी संख्या है जो इन दोनों संख्याओं को विभाजित करेगी। ऐसे नंबर G को दें।

चूंकि संख्या G संख्या C को विभाजित करती है, और संख्या C A - E को विभाजित करती है, G भी संख्या A - E को विभाजित करता है। संख्या G, संपूर्ण संख्या A को भी विभाजित करता है, इसलिए यह शेष E को विभाजित करता है। लेकिन E, E को C - F से विभाजित करता है, इसलिए G C को भी विभाजित करता है - F. और संख्या G को भी पूर्ण संख्या C से विभाजित करता है, क्योंकि यह शेष F को विभाजित करता है; इस प्रकार, एक बड़ी संख्या एक छोटे को विभाजित करती है, और यह असंभव है।

इस प्रकार, ए और सी को विभाजित करने वाले एफ से अधिक कोई संख्या नहीं है; इसलिए, संख्या F GCD है।

परिणाम। यह तर्क इस धारणा को स्पष्ट करता है कि दो संख्याओं को विभाजित करने वाली कोई भी संख्या उनके GCD को विभाजित करती है। QED

विवरण जीसीडी को खोजने के दो तरीके देता है - घटाव और विभाजन द्वारा। दरअसल, एल्गोरिथ्म को लागू करने के इन दो तरीकों को आज व्यापक रूप से जाना जाता है।

यहां स्विफ्ट में लिखे गए फ़ंक्शन का एक उदाहरण है जो पहली विधि को लागू करता है:

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. }

यहाँ, पुन: उपयोग के लिए, अपनी खातिर, मैं एक अलग फ़ंक्शन में लाया, जीसीडी की खोज के मामले, जब यह तुरंत जाना जाता है, बिना किसी एल्गोरिथ्म का पालन करने की आवश्यकता के बिना:

 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 }

(यदि दो संख्याएँ समान हैं, तो स्वाभाविक रूप से उनका जीसीडी भी उनके बराबर है। यदि संख्याओं में से कोई भी शून्य है, तो जीसीडी दूसरी संख्या के बराबर होगी, क्योंकि शून्य किसी भी संख्या से विभाज्य है (परिणाम के साथ, निश्चित रूप से, शून्य भी) )।

केवल गैर-नकारात्मक मानों का उपयोग इनपुट के रूप में किया जा सकता है। तदनुसार, नकारात्मक के लिए, आप समान विधियों का उपयोग कर सकते हैं, लेकिन संख्याओं को ले जा सकते हैं। (हां, सामान्य कारक भी नकारात्मक हो सकता है, लेकिन हम विशेष रूप से जीसीडी के लिए देख रहे हैं, और सकारात्मक संख्या स्पष्ट रूप से हमेशा नकारात्मक से अधिक है।)

और यहाँ यह विभाजन द्वारा एल्गोरिथ्म के संस्करण के कार्यान्वयन की तरह लग सकता है:

 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(_:) XCTest Xcode XCTest में कोड परीक्षण के लिए "देशी" ढांचे XCTestCase वर्ग की XCTestCase ।

इनपुट के रूप में, मैंने यादृच्छिक संख्याओं के जोड़े की एक सरणी का उपयोग किया। माप, निश्चित रूप से, प्रत्येक विधि के लिए एक ही सरणी का उपयोग करके किया गया था। मैंने जोड़े के लिए संख्याओं के प्रसार को शून्य से 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 (a, b) के रूप में खोज करने के कार्य को नामित करते हैं, तो कहते हैं, तीन नंबर gcd (a, b, c) का GCD, gcd (gcd (a, b), c) के बराबर है। और इसी तरह, किसी भी संख्या के लिए GCD क्रमिक रूप से पिछली संख्याओं के GCD के GCD और अगली संख्या की गणना करके पाया जाता है। हालांकि, ज़ाहिर है, यह सामान्य रूप से जीसीडी के लिए खोज की चिंता करता है, न कि केवल यूक्लिडियन एल्गोरिथ्म।

GCD बहुपद खोजने के लिए एल्गोरिथ्म का एक सामान्यीकरण भी है। लेकिन यह पहले से ही इस सरल पोस्ट के दायरे से परे है, और कुछ हद तक, गणित का मेरा ज्ञान।

यूक्लिडियन एल्गोरिथ्म जटिलता

एल्गोरिथ्म की अस्थायी जटिलता की जांच लंबे समय से की गई है, न कि आपके विनम्र सेवक की तुलना में जल्दी और बहुत अधिक सीखा पुरुषों द्वारा। हालांकि, सवाल लंबे समय से बंद है और एक जवाब मिल गया है। दरअसल, पिछली सदी से पहले बीच में वापस। गेब्रियल लंगड़ा ।

संक्षेप में, उत्तर तैयार किया जाता है, वास्तव में, इस एल्गोरिथ्म से संबंधित लैम प्रमेय द्वारा। एल्गोरिथ्म में चरणों की संख्या निकटतम बड़ी फाइबोनैचि संख्या के अनुक्रम संख्या के बराबर होगी , इनपुट मापदंडों की दो संख्याओं में सबसे छोटी माइनस 2. थोड़ी अधिक पारंपरिक गणितीय संकेतन का उपयोग करना, फिर अगर u> v (और v> 1), तो एल्गोरिथ्म के पास की संख्या n - 2 के लिए होगी। v <Fn (Fn निकटतम v फाइबोनैचि संख्या है, और n इसकी अनुक्रम संख्या है)।

क्रमशः फाइबोनैचि संख्या तेजी से बढ़ती है, हमारे पास एल्गोरिथम के निष्पादन समय का एक लघुगणक कार्य है (दो इनपुट संख्याओं में से छोटा)।

इसी गणना से पता चलता है कि एल्गोरिथ्म के लिए सबसे खराब इनपुट डेटा लगातार दो फाइबोनैचि संख्याएं हैं।

एनओडी खोजने के लिए द्विआधारी विधि

जीसीडी की खोज के बारे में बात करते हुए, यह पिछली शताब्दी के 60 के दशक में पहले से प्रस्तावित एल्गोरिथ्म का उल्लेख करने योग्य है, जिसके बारे में एक निश्चित जोसेफ स्टीन ने कहा, जिसके बारे में मुझे वेब पर कोई जानकारी नहीं मिली। यह (एल्गोरिथ्म) द्विआधारी अंकगणित के लिए उन्मुख है और इसमें विभाजन ऑपरेशन शामिल नहीं हैं। एल्गोरिथ्म केवल समता की जाँच और रुकने के साथ संचालित होता है, जो अकेले बाइनरी अंकगणितीय की क्षमताओं के साथ संभव है।

एल्गोरिथ्म चार तथ्यों पर आधारित है:

यदि 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)

विकिपीडिया पर आप एल्गोरिथ्म का पुनरावर्ती संस्करण देख सकते हैं (आधुनिक प्रोग्रामिंग भाषाओं में कई पंक्तियों में लिखा गया है), मैंने इसे स्विफ्ट पर फिर से नहीं लिखा। और यहाँ मैं एक पुनरावृत्त कार्यान्वयन देता हूँ:

 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 मिनट की प्रसिद्धि प्राप्त की (वर्तमान एक से पहले के हिस्से में), प्राचीन चीन में जाना जाता था। उनका वर्णन पहली शताब्दी में वापस काम करने वाले कार्यों में पाया जाता है। ईसा पूर्व बेशक, "आधा विभाजन" और घटाव जैसे शब्दों में। और भिन्नों को कम करने के संदर्भ में भी।

निष्कर्ष

ईमानदारी से, इस सरल "शोध" के साथ मैं कुछ भी साबित नहीं करने जा रहा था और कोई क्रांतिकारी निष्कर्ष नहीं निकालना चाहता था (और मैंने ऐसा नहीं किया था!)। मैं सिर्फ अपनी जिज्ञासा को संतुष्ट करना चाहता था, शास्त्रीय समस्या को हल करने के लिए विभिन्न तरीकों के काम को देखता हूं, और अपनी उंगलियों को थोड़ा बढ़ाता हूं। फिर भी, मुझे आशा है कि आप परिणाम देखने के लिए उत्सुक थे!