এক্সটেন্ডেড ইউক্লিডীয় অ্যালগরিদম#
ইউক্লিডীয় অ্যালগরিদম যেখানে দুটি পূর্ণসংখ্যা $a$ ও $b$-এর শুধুমাত্র গসাগু (GCD) গণনা করে, এক্সটেন্ডেড ভার্সন $a$ ও $b$-এর মাধ্যমে GCD কে উপস্থাপন করার একটি উপায়ও খুঁজে বের করে, অর্থাৎ সহগ $x$ ও $y$ যেন:
$$a \cdot x + b \cdot y = \gcd(a, b)$$এটি গুরুত্বপূর্ণ যে বেজুর অভেদ অনুযায়ী আমরা সর্বদা এমন একটি উপস্থাপনা খুঁজে পেতে পারি। উদাহরণস্বরূপ, $\gcd(55, 80) = 5$, তাই আমরা $5$ কে $55$ এবং $80$ পদবিশিষ্ট একটি রৈখিক সমন্বয় হিসেবে উপস্থাপন করতে পারি: $55 \cdot 3 + 80 \cdot (-2) = 5$
এই সমস্যার একটি আরও সাধারণ রূপ রৈখিক ডায়োফ্যান্টাইন সমীকরণ সম্পর্কিত আর্টিকেলে আলোচনা করা হয়েছে। এটি এই অ্যালগরিদমের উপর ভিত্তি করে তৈরি হবে।
অ্যালগরিদম#
এই অনুচ্ছেদে আমরা $a$ ও $b$-এর GCD কে $g$ দ্বারা চিহ্নিত করব।
মূল অ্যালগরিদমে পরিবর্তনগুলো খুবই সরল। আমরা যদি অ্যালগরিদমটি স্মরণ করি, দেখতে পাব যে অ্যালগরিদমটি $b = 0$ এবং $a = g$ দিয়ে শেষ হয়। এই প্যারামিটারগুলোর জন্য আমরা সহজেই সহগ খুঁজে পেতে পারি, যথা $g \cdot 1 + 0 \cdot 0 = g$।
এই সহগ $(x, y) = (1, 0)$ থেকে শুরু করে, আমরা রিকার্সিভ কলগুলোতে পেছনে যেতে পারি। আমাদের শুধু বুঝতে হবে $(a, b)$ থেকে $(b, a \bmod b)$-এ রূপান্তরের সময় সহগ $x$ ও $y$ কীভাবে পরিবর্তিত হয়।
ধরি আমরা $(b, a \bmod b)$-এর জন্য সহগ $(x_1, y_1)$ পেয়েছি:
$$b \cdot x_1 + (a \bmod b) \cdot y_1 = g$$এবং আমরা $(a, b)$-এর জন্য জোড়া $(x, y)$ খুঁজতে চাই:
$$ a \cdot x + b \cdot y = g$$আমরা $a \bmod b$ কে এভাবে উপস্থাপন করতে পারি:
$$ a \bmod b = a - \left\lfloor \frac{a}{b} \right\rfloor \cdot b$$$(x_1, y_1)$-এর সহগ সমীকরণে এই এক্সপ্রেশন প্রতিস্থাপন করলে পাই:
$$ g = b \cdot x_1 + (a \bmod b) \cdot y_1 = b \cdot x_1 + \left(a - \left\lfloor \frac{a}{b} \right\rfloor \cdot b \right) \cdot y_1$$এবং পদগুলো পুনর্বিন্যাস করলে:
$$g = a \cdot y_1 + b \cdot \left( x_1 - y_1 \cdot \left\lfloor \frac{a}{b} \right\rfloor \right)$$আমরা $x$ ও $y$-এর মান পেলাম:
$$\begin{cases} x = y_1 \\ y = x_1 - y_1 \cdot \left\lfloor \frac{a}{b} \right\rfloor \end{cases} $$ইমপ্লিমেন্টেশন#
int gcd(int a, int b, int& x, int& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int x1, y1;
int d = gcd(b, a % b, x1, y1);
x = y1;
y = x1 - y1 * (a / b);
return d;
}উপরের রিকার্সিভ ফাংশনটি GCD এবং সহগের মান x ও y-তে রিটার্ন করে (যেগুলো ফাংশনে রেফারেন্স দ্বারা পাঠানো হয়)।
এক্সটেন্ডেড ইউক্লিডীয় অ্যালগরিদমের এই ইমপ্লিমেন্টেশন ঋণাত্মক পূর্ণসংখ্যার জন্যও সঠিক ফলাফল প্রদান করে।
ইটারেটিভ ভার্সন#
এক্সটেন্ডেড ইউক্লিডীয় অ্যালগরিদমকে ইটারেটিভভাবেও লেখা সম্ভব। যেহেতু এটি রিকার্সন এড়ায়, কোডটি রিকার্সিভটির চেয়ে একটু দ্রুত চলবে।
int gcd(int a, int b, int& x, int& y) {
x = 1, y = 0;
int x1 = 0, y1 = 1, a1 = a, b1 = b;
while (b1) {
int q = a1 / b1;
tie(x, x1) = make_tuple(x1, x - q * x1);
tie(y, y1) = make_tuple(y1, y - q * y1);
tie(a1, b1) = make_tuple(b1, a1 - q * b1);
}
return a1;
}আপনি যদি a1 ও b1 ভেরিয়েবলগুলো ভালো করে দেখেন, লক্ষ্য করবেন যে তারা স্বাভাবিক ইউক্লিডীয় অ্যালগরিদমের ইটারেটিভ ভার্সনে ঠিক একই মান নেয়। তাই অ্যালগরিদম অন্তত সঠিক GCD গণনা করবে।
অ্যালগরিদম কেন সঠিক সহগ গণনা করে তা দেখতে, বিবেচনা করুন যে নিম্নলিখিত ইনভেরিয়েন্টগুলো যেকোনো সময়ে ধরে রাখে (while লুপ শুরু হওয়ার আগে এবং প্রতিটি ইটারেশনের শেষে):
$$x \cdot a + y \cdot b = a_1$$$$x_1 \cdot a + y_1 \cdot b = b_1$$ধরি একটি ইটারেশনের শেষে মানগুলো প্রাইম ($'$) দ্বারা চিহ্নিত, এবং ধরুন $q = \frac{a_1}{b_1}$। ইউক্লিডীয় অ্যালগরিদম থেকে, আমরা পাই:
$$a_1' = b_1$$$$b_1' = a_1 - q \cdot b_1$$প্রথম ইনভেরিয়েন্ট ধরে রাখতে, নিম্নলিখিতটি সত্য হওয়া উচিত:
$$x' \cdot a + y' \cdot b = a_1' = b_1$$$$x' \cdot a + y' \cdot b = x_1 \cdot a + y_1 \cdot b$$একইভাবে দ্বিতীয় ইনভেরিয়েন্টের জন্য, নিম্নলিখিতটি ধরে রাখা উচিত:
$$x_1' \cdot a + y_1' \cdot b = a_1 - q \cdot b_1$$$$x_1' \cdot a + y_1' \cdot b = (x - q \cdot x_1) \cdot a + (y - q \cdot y_1) \cdot b$$$a$ ও $b$-এর সহগ তুলনা করে, প্রতিটি ভেরিয়েবলের আপডেট সমীকরণ বের করা যায়, যা নিশ্চিত করে যে ইনভেরিয়েন্টগুলো সমগ্র অ্যালগরিদম জুড়ে বজায় থাকে।
শেষে আমরা জানি $a_1$-এ GCD আছে, তাই $x \cdot a + y \cdot b = g$। যার মানে আমরা প্রয়োজনীয় সহগ খুঁজে পেয়েছি।
আপনি কোড আরও অপটিমাইজ করতে পারেন, এবং কোড থেকে $a_1$ ও $b_1$ ভেরিয়েবল সরিয়ে $a$ ও $b$ পুনর্ব্যবহার করতে পারেন। তবে এটি করলে, ইনভেরিয়েন্ট নিয়ে যুক্তি দেওয়ার ক্ষমতা হারাবেন।