গসাগু (গরিষ্ঠ সাধারণ ফ্যাক্টর) নির্ণয়ের ইউক্লিডীয় অ্যালগরিদম#

দুটি অঋণাত্মক পূর্ণ সংখ্যা $a$ ও $b$ দেওয়া আছে, আমাদের এদের জিসিডি (গরিষ্ঠ সাধারণ ফ্যাক্টর বা গসাগু) বের করতে হবে, অর্থাৎ সেই বৃহত্তম সংখ্যা যা $a$ ও $b$ উভয়ের ফ্যাক্টর। একে সাধারণত $\gcd(a, b)$ দ্বারা প্রকাশ করা হয়। গাণিতিকভাবে এটা এভাবে ডিফাইন করা:

$$\gcd(a, b) = \max \{k > 0 : (k \mid a) \text{ and } (k \mid b) \}$$

(এখানে “$\mid$” চিহ্নটি বিভাজ্যতা নির্দেশ করে, অর্থাৎ “$k \mid a$” মানে “$k$, $a$-কে বিভাজ্য করে”)

যখন একটি সংখ্যা শূন্য এবং অপরটি অশূন্য, তখন সংজ্ঞা অনুসারে তাদের গসাগু হলো দ্বিতীয় সংখ্যাটা। যখন দুটি সংখ্যাই শূন্য, তখন তাদের গসাগু অসংজ্ঞায়িত (এটা যেকোনো বৃহৎ সংখ্যা হতে পারে), কিন্তু $\gcd$-এর সাহচর্য ধর্ম বজায় রাখতে এটাকেও শূন্য হিসেবে ডিফাইন করা সুবিধাজনক। এটা আমাদের একটি সহজ নিয়ম দেয়: যদি একটি সংখ্যা শূন্য হয়, তাহলে গসাগু হলো অপর সংখ্যাটা।

ইউক্লিডীয় অ্যালগরিদম, যা নিচে আলোচনা করা হয়েছে, দুটি সংখ্যা $a$ ও $b$-এর গসাগু $O(\log \min(a, b))$ সময়ে বের করতে পারে। যেহেতু ফাংশনটি সাহচর্য ধর্ম মেনে চলে, তাই দুইয়ের অধিক সংখ্যার গসাগু বের করতে আমরা $\gcd(a, b, c) = \gcd(a, \gcd(b, c))$ এভাবে করতে পারি।

এই অ্যালগরিদমটা প্রথম বর্ণিত হয়েছিল ইউক্লিডের “Elements” গ্রন্থে (আনুমানিক ৩০০ খ্রিস্টপূর্বাব্দ), তবে সম্ভবত এই অ্যালগরিদমের উৎপত্তি আরও আগে।

অ্যালগরিদম#

মূলত, ইউক্লিডীয় অ্যালগরিদম এভাবে প্রণয়ন করা হয়েছিল: বড় সংখ্যা থেকে ছোট সংখ্যা বিয়োগ করতে থাকো যতক্ষণ না একটি সংখ্যা শূন্য হয়। আসলে, যদি $g$, $a$ ও $b$ উভয়কে বিভাজ্য করে, তাহলে এটা $a-b$-কেও বিভাজ্য করে। অন্যদিকে, যদি $g$, $a-b$ ও $b$-কে বিভাজ্য করে, তাহলে এটা $a = b + (a-b)$-কেও বিভাজ্য করে, যার অর্থ হলো $\{a, b\}$ ও $\{b, a-b\}$-এর সাধারণ ফ্যাক্টরের সেট একই।

লক্ষ্য করো যে, $b$-কে $a$ থেকে কমপক্ষে $\left\lfloor\frac{a}{b}\right\rfloor$ বার বিয়োগ না করা পর্যন্ত $a$ বড় সংখ্যা থেকে যায়। তাই গতি বাড়াতে, $a-b$-এর পরিবর্তে $a-\left\lfloor\frac{a}{b}\right\rfloor b = a \bmod b$ ব্যবহার করা হয়। তখন অ্যালগরিদমটা অত্যন্ত সহজভাবে লেখা যায়:

$$\gcd(a, b) = \begin{cases}a,&\text{if }b = 0 \\ \gcd(b, a \bmod b),&\text{otherwise.}\end{cases}$$

ইমপ্লিমেন্টেশন#

int gcd (int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd (b, a % b);
}

C++-এর টার্নারি অপারেটর ব্যবহার করে আমরা এটা এক লাইনে লিখতে পারি।

int gcd (int a, int b) {
    return b ? gcd (b, a % b) : a;
}

এবং সবশেষে, এখানে একটি নন-রিকার্সিভ ইমপ্লিমেন্টেশন দেওয়া হলো:

int gcd (int a, int b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

লক্ষ্য করো যে C++১৭ থেকে gcd একটি স্ট্যান্ডার্ড ফাংশন হিসেবে C++-এ ইমপ্লিমেন্ট করা আছে।

টাইম কমপ্লেক্সিটি#

অ্যালগরিদমের রানিং টাইম লামের থিওরেম দ্বারা অনুমান করা হয়, যা ইউক্লিডীয় অ্যালগরিদম ও ফিবোনাচ্চি সিকোয়েন্সের মধ্যে একটি চমকপ্রদ সম্পর্ক স্থাপন করে:

যদি $a > b \geq 1$ এবং কোনো $n$-এর জন্য $b < F_n$ হয়, তাহলে ইউক্লিডীয় অ্যালগরিদম সর্বাধিক $n-2$ বার রিকার্সিভ কল করে।

তদুপরি, দেখানো সম্ভব যে এই থিওরেমের ঊর্ধ্বসীমা অপটিমাল। যখন $a = F_n$ এবং $b = F_{n-1}$, তখন $gcd(a, b)$ ঠিক $n-2$ বার রিকার্সিভ কল করবে। অন্যভাবে বলতে গেলে, পরপর দুটি ফিবোনাচ্চি সংখ্যা ইউক্লিডের অ্যালগরিদমের জন্য সবচেয়ে খারাপ ইনপুট।

যেহেতু ফিবোনাচ্চি সংখ্যাগুলো এক্সপোনেনশিয়ালি বৃদ্ধি পায়, তাই আমরা পাই যে ইউক্লিডীয় অ্যালগরিদম $O(\log \min(a, b))$ সময়ে কাজ করে।

কমপ্লেক্সিটি অনুমানের আরেকটি উপায় হলো এটা লক্ষ্য করা যে $a \geq b$ হলে $a \bmod b$, $a$-এর তুলনায় কমপক্ষে $2$ গুণ ছোট, তাই অ্যালগরিদমের প্রতিটি ইটারেশনে বড় সংখ্যাটা কমপক্ষে অর্ধেক হয়ে যায়। এই যুক্তি প্রয়োগ করে, যখন আমরা $a_1,\dots,a_n \leq C$ সংখ্যার সেটের জিসিডি নির্ণয় করি, তখন মোট রানটাইম $O(n \log C)$-এর পরিবর্তে $O(n + \log C)$ হিসেবে অনুমান করা যায়, কারণ অ্যালগরিদমের প্রতিটি অ-তুচ্ছ ইটারেশনে বর্তমান জিসিডি ক্যান্ডিডেট কমপক্ষে $2$ গুণ হ্রাস পায়।

Least Common Multiple (LCM)#

LCM নির্ণয়কে নিচের সহজ সূত্রের সাহায্যে জিসিডি নির্ণয়ে রূপান্তরিত করা যায়:

$$\text{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)}$$

সুতরাং, ইউক্লিডীয় অ্যালগরিদম ব্যবহার করে একই টাইম কমপ্লেক্সিটিতে LCM নির্ণয় করা যায়:

এখানে একটি সম্ভাব্য ইমপ্লিমেন্টেশন দেওয়া হলো, যা চতুরতার সাথে প্রথমে $a$-কে জিসিডি দিয়ে ভাগ করে ইন্টিজার ওভারফ্লো এড়ায়:

int lcm (int a, int b) {
    return a / gcd(a, b) * b;
}

বাইনারি জিসিডি#

বাইনারি জিসিডি অ্যালগরিদম হলো সাধারণ ইউক্লিডীয় অ্যালগরিদমের একটি অপটিমাইজেশন।

সাধারণ অ্যালগরিদমের ধীর অংশটি হলো মডুলো অপারেশন। মডুলো অপারেশন, যদিও আমরা সেগুলোকে $O(1)$ হিসেবে দেখি, যোগ, বিয়োগ বা বিটওয়াইজ অপারেশনের মতো সহজ অপারেশনগুলোর তুলনায় অনেক ধীর। তাই এগুলো এড়িয়ে চলাই ভালো।

দেখা যায় যে, মডুলো অপারেশন ছাড়াই একটি দ্রুত জিসিডি অ্যালগরিদম ডিজাইন করা সম্ভব। এটা কয়েকটি বৈশিষ্ট্যের উপর ভিত্তি করে:

যদি দুটি সংখ্যাই জোড় হয়, তাহলে আমরা উভয় থেকে ২ বের করে আনতে পারি এবং বাকি সংখ্যাগুলোর জিসিডি নির্ণয় করতে পারি: $\gcd(2a, 2b) = 2 \gcd(a, b)$।
যদি একটি সংখ্যা জোড় এবং অপরটি বিজোড় হয়, তাহলে জোড় সংখ্যাটা থেকে ২ ফ্যাক্টরটা সরিয়ে ফেলা যায়: $\gcd(2a, b) = \gcd(a, b)$ যদি $b$ বিজোড় হয়।
যদি দুটি সংখ্যাই বিজোড় হয়, তাহলে একটি সংখ্যা থেকে অপরটি বিয়োগ করলে জিসিডি পরিবর্তন হবে না: $\gcd(a, b) = \gcd(b, a-b)$

শুধুমাত্র এই বৈশিষ্ট্যগুলো এবং GCC-এর কিছু দ্রুত বিটওয়াইজ ফাংশন ব্যবহার করে আমরা একটি দ্রুত ভার্সন ইমপ্লিমেন্ট করতে পারি:

int gcd(int a, int b) {
    if (!a || !b)
        return a | b;
    unsigned shift = __builtin_ctz(a | b);
    a >>= __builtin_ctz(a);
    do {
        b >>= __builtin_ctz(b);
        if (a > b)
            swap(a, b);
        b -= a;
    } while (b);
    return a << shift;
}

লক্ষ্য করো যে, এই ধরনের অপটিমাইজেশন সাধারণত প্রয়োজন হয় না, এবং বেশিরভাগ প্রোগ্রামিং ল্যাঙ্গুয়েজে ইতিমধ্যেই তাদের স্ট্যান্ডার্ড লাইব্রেরিতে একটি জিসিডি ফাংশন রয়েছে। যেমন, C++১৭-এ numeric হেডারে std::gcd নামে এমন একটি ফাংশন আছে।