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

দুটি অঋণাত্মক পূর্ণ সংখ্যা $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$ গুণ হ্রাস পায়।

লিস্ট কমন মাল্টিপল (ল.সা.গু)#

লিস্ট কমন মাল্টিপল (সাধারণত এলসিএম হিসেবে পরিচিত) নির্ণয়কে নিম্নলিখিত সহজ সূত্রের সাহায্যে জিসিডি নির্ণয়ে রূপান্তরিত করা যায়:

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

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

এখানে একটি সম্ভাব্য ইমপ্লিমেন্টেশন দেওয়া হলো, যা চতুরতার সাথে প্রথমে $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 নামে এমন একটি ফাংশন আছে।