C++ এ GCD খোঁজার জন্য স্টেইনের অ্যালগরিদম

স্টেইনের অ্যালগরিদম সংখ্যার GCD আবিষ্কারের জন্য ব্যবহৃত হয় কারণ এটি দুটি অ-ঋণাত্মক পূর্ণ সংখ্যার সেরা নিয়মিত ভাজক গণনা করে। এটি গণিতের গতিবিধি, পরীক্ষা এবং বিয়োগ দিয়ে ভাগ প্রতিস্থাপন করে। যদি an এবং b উভয়ই 0 হয়, gcd হল শূন্য gcd(0, 0) =0। GCD(a,b) এর জন্য নিম্নরূপ অ্যালগরিদম;

অ্যালগরিদম

START
   Step-1: check If both a and b are 0, gcd is zero gcd(0, 0) = 0.
   Step-2: then gcd(a, 0) = a and gcd(0, b) = b because everything divides 0.
   Step-3: check If a and b are both even, gcd(a, b) = 2*gcd(a/2, b/2) because 2 is a common divisor. Multiplication with 2 can be done with a bitwise shift operator.
   Step-4: If a is even and b is odd, gcd(a, b) = gcd(a/2, b). Similarly, if a is odd and b is even, then gcd(a, b) = gcd(a, b/2). It is because 2 is not a common divisor.
   Step-5: If both a and b are odd, then gcd(a, b) = gcd(|a-b|/2, b). Note that difference of two odd numbers is even
   Step-6: Repeat steps 3–5 until a = b, or until a = 0.
END

উপরের অ্যালগরিদমের দৃষ্টিতে 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); // Swap u and v.
         y = (y - x);
   }
   while (y != 0);
      return x << k;
}
int main(){
   int a = 24, b = 18;
   printf("Calculated GCD of numbers (24,18) is= %d\n", funGCD(a, b));
   return 0;
}

আউটপুট

অবশেষে, দুটি সরবরাহকৃত সংখ্যা 24 এবং 18-এর GCD নিম্নরূপ স্টেইনের অ্যালগরিদম প্রয়োগ করে 6-এ গণনা করা হয়;

Calculated GCD of numbers (24,18) is= 6