এক্সটেন্ডেড ইউক্লিডীয়ান অ্যালগোরিদম

এই টিউটোরিয়ালটি আসলে ‘একের ভেতর দুই’ টিউটোরিয়াল। কারণ, এক্সটেন্ডেড ইউক্লিডীয়ান অ্যালগোরিদম জানতে হলে ইউক্লিডীয়ান অ্যালগোরিদম কিভাবে কাজ করে সেটাও জানতে হবে। আর আমরা সবাই নিশ্চয়ই জানি, ইউক্লিডীয়ান অ্যালগোরিদম আমরা GCD (Greatest Common Divisor) বের করার কাজে ব্যবহার করি!

 

বেশি কথা না বাড়িয়ে উদাহরণে চলে যাই! খাতা কলম নিয়ে আমার সাথেই লিখতে বসে যাও, তাহলে পুরো ব্যাপারটা বুঝতে খুব সহজ হবে!

 

আচ্ছা, প্রথমে আমরা 84, 23 এর GCD বের করব ইউক্লিডীয়ান অ্যালগোরিদমের সাহায্যে!

 

84 = 3*23 + 15
23 = 1*15 + 8
15 = 1*8 + 7
8 = 1*7 + 1
7 = 7*1 + 0

 

০ পেয়ে গেলেই আমরা আর এগোতে পারব না। সেক্ষেত্রে,যেটা দিয়ে আমরা ভাগ দিচ্ছিলাম, সেটাই আমাদের GCD.  অর্থাৎ GCD(84,23) = 1

 

এইটুকু পর্যন্ত আশা করি সবাই আগে থেকেই জানতে! না জানলেও এখন তো শিখেই গেলে! 😀

 

এক্সটেন্ডেড ইউক্লিডীয়ান অ্যালগোরিদম এই ইউক্লিডীয়ান অ্যালগোরিদমেরই একটা এক্সটেনশন, যা নিচের সমীকরণে x, y এর মান বের করে দেয়ঃ

 

a*x + b*y = gcd(a,b)

 

আচ্ছা, এই সমীকরণটা যে সত্যি, সেটা জানলাম কিভাবে?  কারও এই ব্যাপারে আগ্রহ থাকলে Bézout’s identity সম্পর্কে জানতে পারো!

 

ইউক্লিডীয়ান অ্যালগোরিদম থেকে আমরা যে সমীকরণগুলো পেয়েছি, সেগুলো থেকেই আমরা এবার x, y এর মান বের করব! বলে রাখি, x অথবা y যেকোন একটা নেগেটিভ হবে, কেন সেটা একটু মাথা খাটালেই বুঝতে পারার কথা। না বুঝলে ধৈর্য ধরে বসো, x, y এর মান বের করার পরেই বুঝতে পারবে কেন!

 

8 – 1*7 = 1
(23 – 1*15)  – 1*(15 – 1*8) = 1
23 – 2*15 + 1* 8 = 1
23 – 2*(84 – 3*23) + 1*(23-1*15) = 1
23 – 2*84 + 6*23 + 1*23 – 1*15 = 1
8*23 – 2*84 – 1*15 = 1
8*23 – 2*84 – 1*(84 – 3*23) = 1
8*23 – 2*84 – 1*84 + 3*23 = 1
11*23 – 3*84 = 1
84*(-3) + 23*11 = 1

 

এখানে a = 84, b = 23, gcd(a,b) = 1, x = -3, y = 11. এটাই এক্সটেন্ডেড ইউক্লিডীয়ান অ্যালগোরিদম! কি, সহজ না? 😀

 

যেকোন a, b এর ক্ষেত্রেই এরকমভাবে x, y এর মান বের করা যাবে। কিন্তু এই উদাহরণের a, b এর একটা আলাদা বৈশিষ্ট্য আছে, এরা কো-প্রাইম। অর্থাৎ ১ ছাড়া অন্য কোন সংখ্যা দ্বারা a,b উভয়েই নিঃশেষে বিভাজ্য নয়। এক্ষেত্রে, x হচ্ছে a modulo b এর multiplicative inverse,  y হল b modulo a এর multiplicative inverse.

 

অর্থাৎ, x-1 = a%b, y-1 = b%a. ক্যালকুলেশনের সুবিধার্থে অনেক ক্ষেত্রে x, y এর মান পজিটিভ হয়ে থাকে।

 

উপরের উদাহরণে, (-3) % 23 = 20, 11 % 84 = 11

 

20-1 = 84 % 23    -> 84*20 = 1680%23 = 1
11-1 = 23%84      -> 23*11 = 253%84  = 1

 

এই মডুলার ইনভার্স অনেকক্ষেত্রেই কাজে লাগে। চাইনিজ রিমেইন্ডার থিওরাম (Chinese Remainder Theorem or CRT) তে এই মডুলার ইনভার্স কাজে লাগবে! পরবর্তী কোন টিউটোরিয়ালে CRT সম্পর্কে বিস্তারিত লেখার চেষ্টা করব! আপাতত এক্সটেন্ডেড ইউক্লিড এর মাধ্যমে x,y এর মান এবং সাথে gcd(a,b) এর মান বের করার কোডটা লিখে ফেলি!

 


#define i64 long long int

i64 ex_euclid(i64 a,i64 b, i64 &X, i64 &Y)
{
    if (b == 0)
    {
        X = 1;
        Y = 0;
        return a;
    }

    i64 xx, yy;

    i64 g = ex_euclid(b, a%b, xx, yy);

    X = yy;
    Y = xx-yy*(a/b);

    return g;
}

int main()
{
    i64 a,b,x,y;
    cin >> a >> b;
    i64 gcd = ex_euclid(a,b,x,y);
    cout << x << " " << y << " " << gcd << endl;
    return 0;
}

 

কনসেপ্টটা ঝালাই করে নিতে নিচের প্রব্লেমদুটো সলভ করে ফেলতে পারো! 😀

 

10090 – Marbles (UVA)
10104 – Euclid Problem(UVA)
Advertisements

4 thoughts on “এক্সটেন্ডেড ইউক্লিডীয়ান অ্যালগোরিদম

  1. vaiaa this parameter i64 ex_euclid(i64 a,i64 b, i64 X, i64 Y) have a littile bit mistake…
    >>>actually these are i64 &X,i64 &Y<<<
    fixed it please ..thank you 🙂

    Liked by 1 person

    1. Sorry for the mistake. It was actually in my code at first, but this ‘&’ character creates a weird thing in HTML and so during editing I accidentally erased the ‘&’ character.

      Thank you very much for finding the mistake.

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s