پرش به محتویات

الگوریتم اقلیدس برای پیدا کردن ب.م.م (بزرگترین مقسوم‌علیه مشترک)

فرض کن دو تا عدد صحیح نامنفی $a$ و $b$ داریم. می‌خوایم ب.م.م (بزرگترین مقسوم‌علیه مشترک) یا همون GCD شون رو پیدا کنیم. یعنی بزرگترین عددی که هم $a$ و هم $b$ بهش بخش‌پذیر باشن. معمولاً این مقدار رو با $\gcd(a, b)$ نشون میدن. اگه بخوایم خیلی ریاضی‌طور تعریفش کنیم، اینجوری میشه:

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

(اینجا، این علامت "$\mid$" یعنی بخش‌پذیری. مثلاً "$k \mid a$" یعنی "$a$ بر $k$ بخش‌پذیره")

حالا یه حالت خاص: اگه یکی از عددها صفر باشه و اون یکی نه، ب.م.م شون طبق تعریف میشه همون عدده که صفر نیست. اگه هر دوتاشون صفر باشن چی؟ اون‌وقت ب.م.م تعریف نشده (چون هر عدد گنده‌ای می‌تونه مقسوم‌علیه صفر باشه)، ولی برای اینکه خاصیت شرکت‌پذیری $\gcd$ رو حفظ کنیم، راحت‌تریم که ب.م.م دو تا صفر رو همون صفر در نظر بگیریم. اینجوری یه قانون ساده و خوشگل داریم: اگه یکی از عددها صفر بود، ب.م.م میشه اون یکی عدده.

الگوریتم اقلیدس که الان می‌خوایم در موردش حرف بزنیم، بهمون اجازه میده ب.م.م دو تا عدد $a$ و $b$ رو توی زمان $O(\log \min(a, b))$ پیدا کنیم. از اونجایی که این تابع شرکت‌پذیره، برای پیدا کردن ب.م.م بیشتر از دو تا عدد هم کارمون راحته. اینجوری حسابش می‌کنیم: $\gcd(a, b, c) = \gcd(a, \gcd(b, c))$ و همینطور الی آخر.

این الگوریتم اولین بار تو کتاب «اصول» اقلیدس (حدود ۳۰۰ سال قبل از میلاد مسیح) توضیح داده شده، ولی شاید حتی از اون هم قدیمی‌تر باشه.

الگوریتم

اولش، الگوریتم اقلیدس اینجوری فرمول‌بندی شده بود: هی عدد کوچیکه رو از بزرگه کم کن تا وقتی که یکی از عددها صفر بشه. قضیه اینه که اگه یه عددی مثل $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$ تا $b$ ازش کم کنیم. پس برای اینکه کار رو سریع‌تر کنیم، به جای $a-b$ یه راست میریم سراغ $a-\left\lfloor\frac{a}{b}\right\rfloor b$ که همون $a \bmod b$ (باقیمانده تقسیم $a$ بر $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++17 به بعد، خود C++ یه تابع استاندارد به اسم gcd داره.

پیچیدگی زمانی

پیچیدگی زمانی الگوریتم رو با قضیه‌ی Lamé تخمین می‌زنن. این قضیه یه ربط خیلی خفن بین الگوریتم اقلیدس و دنباله فیبوناچی پیدا می‌کنه:

اگه $a > b \geq 1$ باشه و $b$ از عدد فیبوناچی $n$-ام ($F_n$) کوچیکتر باشه، الگوریتم اقلیدس حداکثر $n-2$ تا فراخوانی بازگشتی لازم داره.

از این باحال‌تر اینکه میشه نشون داد این کران بالا، بهینه‌ترین حالته (یعنی از این تنگ‌تر نمیشه). وقتی $a = F_n$ و $b = F_{n-1}$ باشه، تابع gcd(a, b) دقیقاً $n-2$ بار بازگشتی صدا زده میشه. به عبارت دیگه، دو تا عدد فیبوناچی پشت سر هم، بدترین ورودی ممکن برای الگوریتم اقلیدس هستن.

از اونجایی که اعداد فیبوناچی رشد نمایی دارن، نتیجه می‌گیریم که الگوریتم اقلیدس توی زمان $O(\log \min(a, b))$ کارش رو تموم می‌کنه.

یه راه دیگه برای تحلیل پیچیدگی اینه که حواسمون باشه $a \bmod b$ وقتی $a \geq b$ باشه، حداقل ۲ برابر از $a$ کوچیکتره، پس عدد بزرگتر توی هر تکرار الگوریتم حداقل نصف میشه. اگه از همین استدلال برای محاسبه ب.م.م یه مجموعه عدد مثل $a_1,\dots,a_n \leq C$ استفاده کنیم، می‌تونیم پیچیدگی زمانی کل رو به جای $O(n \log C)$، به صورت $O(n + \log C)$ تخمین بزنیم. دلیلش اینه که هر مرحله از الگوریتم که الکی نباشه (یعنی باقیمانده صفر نشه)، کاندیدای فعلی ب.م.م رو حداقل نصف می‌کنه.

کوچکترین مضرب مشترک

حساب کردن ک.م.م (کوچکترین مضرب مشترک) یا همون LCM رو میشه با یه فرمول ساده به همون محاسبه‌ی ب.م.م ربط داد:

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

پس، ک.م.م رو هم میشه با کمک الگوریتم اقلیدس و با همون پیچیدگی زمانی حساب کرد:

اینم یه پیاده‌سازی باحال که خیلی هوشمندانه اول $a$ رو بر ب.م.م تقسیم می‌کنه تا جلوی سرریز عدد صحیح (integer overflow) رو بگیره:

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

الگوریتم GCD دودویی (Binary GCD)

الگوریتم ب.م.م دودویی یا Binary GCD یه بهینه‌سازی روی همون الگوریتم اقلیدس معمولیه.

قسمت کند الگوریتم معمولی، همون عملیات باقیمانده (modulo) گرفتنه. عمل باقیمانده، با اینکه ما معمولاً پیچیدگیش رو $O(1)$ در نظر می‌گیریم، ولی در عمل خیلی کندتر از عملیات ساده‌تری مثل جمع و تفریق یا عملیات بیتی (bitwise) هست. پس بهتره اگه میشه ازش استفاده نکنیم.

معلوم شده که میشه یه الگوریتم ب.م.م سریع طراحی کرد که اصلاً از باقیمانده استفاده نمی‌کنه. این الگوریتم روی چندتا خاصیت ساده بنا شده:

  • اگه هر دو تا عدد زوج باشن، می‌تونیم یه فاکتور ۲ از هردوشون بکشیم بیرون و ب.م.م عددهای باقی‌مونده رو حساب کنیم: $\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;
}

البته حواست باشه که اینجور بهینه‌سازی‌ها معمولاً لازم نیست و بیشتر زبون‌های برنامه‌نویسی توی کتابخونه استانداردشون تابع GCD رو دارن. مثلاً C++17 یه تابع به اسم std::gcd توی هدر numeric داره.

مسائل تمرینی