এক্সটেন্ডেড ইউক্লিডীয় অ্যালগরিদম#
ইউক্লিডীয় অ্যালগরিদম যেখানে দুটি পূর্ণসংখ্যা $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$ পুনর্ব্যবহার করতে পারো। তবে এটা করলে, ইনভেরিয়েন্ট নিয়ে যুক্তি দেওয়ার ক্ষমতা হারাবে।