स्टीन का एल्गोरिदम संख्याओं के GCD की खोज के लिए उपयोग किया जाता है क्योंकि यह दो गैर-ऋणात्मक पूर्ण संख्याओं के सर्वोत्तम नियमित भाजक की गणना करता है। यह विभाजन को गणितीय बदलावों, परीक्षाओं और घटाव से बदल देता है। यदि दोनों a और b 0 हैं, तो gcd शून्य है gcd(0, 0) = 0। GCD(a,b) के लिए एल्गोरिदम निम्नानुसार है;
एल्गोरिदम
शुरुआत चरण-1: जांचें यदि a और b दोनों 0 हैं, तो gcd शून्य है gcd(0, 0) = 0। चरण-2: तब gcd(a, 0) = a और gcd(0, b) = b क्योंकि सब कुछ 0 को विभाजित करता है। चरण-3: जांचें यदि a और b दोनों सम हैं, तो gcd(a, b) = 2*gcd(a/2, b/2) क्योंकि 2 एक सामान्य भाजक है। 2 से गुणा बिटवाइज़ शिफ्ट ऑपरेटर से किया जा सकता है। चरण-4: यदि a सम है और b विषम है, तो gcd(a, b) = gcd(a/2, b)। इसी तरह, यदि a विषम है और b सम है, तो gcd(a, b) = gcd(a, b/2)। ऐसा इसलिए है क्योंकि 2 एक सामान्य भाजक नहीं है। चरण-5: यदि a और b दोनों विषम हैं, तो gcd(a, b) = gcd(|a-b|/2, b)। ध्यान दें कि दो विषम संख्याओं का अंतर सम होता है चरण-6: चरण 3-5 को तब तक दोहराएं जब तक a = b, या a = 0 न हो जाए। अंत
उपरोक्त एल्गोरिदम के दृष्टिकोण से 2 संख्याओं के GCD की गणना करने के लिए, निम्नलिखित C++ कोड लिखा गया है;
उदाहरण
#include <bits/stdc++.h> using namespace std; int funGCD(int x, int y){ if (x == 0) return y; if (y == 0) return x; int k; for (k = 0; ((x | y) && 1) == 0; ++k){ x >>= 1; y >>= 1; } while ((x > 1) == 0) x >>= 1; do { while ((y > 1) == 0) y >>= 1; if (x > y) swap(x, y); // u और v को स्वैप करें। y = (y - x); } while (y != 0); return x << k; } int main(){ int a = 24, b = 18; printf("संख्याओं (24,18) का परिकलित GCD है= %d\n", funGCD(a, b)); return 0; }आउटपुट
अंत में, स्टीन के एल्गोरिदम को लागू करके दो आपूर्ति की गई संख्या 24 और 18 का GCD 6 में गणना की जाती है;
संख्याओं (24,18) का परिकलित GCD है= 6
