স্টাইন অ্যালগরিদম (Stein's Algorithm) দিয়ে GCD বের করা C++-তে

স্টাইন অ্যালগরিদম দুটি সংখ্যার GCD বের করতে ব্যবহৃত হয় কারণ এটি দুটি নন-নেগেটিভ ইন্টিজার-এর গ্রেটেস্ট কমন ডিভাইসর গণনা করে। এটি ডিভিশনকে ম্যাথমেটিক্যাল শিফট, কম্পেরিজন এবং সাবট্র্যাকশন দিয়ে রিপ্লেস করে। যদি a এবং b দুটোই ০ হয়, তবে gcd(0, 0) = ০। GCD(a,b) এর অ্যালগরিদম নিচে:

অ্যালগরিদম

শুরু
ধাপ-১: চেক করুন a এবং b দুটোই ০ কিনা, হলে gcd(0, 0) = 0।
ধাপ-২: gcd(a, 0) = a এবং gcd(0, b) = b কারণ সব কিছু ০কে ভাগ করে।
ধাপ-৩: যদি a এবং b দুটোই জোড় হয়, gcd(a, b) = 2*gcd(a/2, b/2) কারণ ২ সাধারণ ভাজক। ২ দিয়ে গুণ বিটওয়াইজ শিফট অপারেটর দিয়ে করা যায়।
ধাপ-৪: যদি a জোড় এবং b বিজোড় হয়, gcd(a, b) = gcd(a/2, b)। একইভাবে a বিজোড় এবং b জোড় হলে gcd(a, b) = gcd(a, b/2)। কারণ ২ সাধারণ ভাজক নয়।
ধাপ-৫: যদি a এবং b দুটোই বিজোড় হয়, gcd(a, b) = gcd(|a-b|/2, b)। দুটি বিজোড় সংখ্যার পার্থক্য জোড়।
ধাপ-৬: ধাপ ৩-৫ রিপিট করুন যতক্ষণ a = b বা a = 0।
শেষ

উপরের অ্যালগরিদম অনুযায়ী ২ সংখ্যার 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("Calculated GCD of numbers (24,18) is= %d\n", funGCD(a, b));
    return 0;
}

আউটপুট

চূড়ান্তভাবে সরবরাহ করা ২৪ এবং ১৮ সংখ্যার GCD স্টাইন অ্যালগরিদম দিয়ে ৬ হিসেবে গণনা হয়েছে:

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