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

الگوریتم اقلیدس برای محاسبه بزرگترین مقسوم‌علیه مشترک

با داشتن دو عدد صحیح نامنفی $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$" به این معنی است که "$k$ عدد $a$ را می‌شمارد")

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

الگوریتم اقلیدس که در ادامه مورد بحث قرار می‌گیرد، به ما اجازه می‌دهد بزرگترین مقسوم‌علیه مشترک دو عدد $a$ و $b$ را در زمان $O(\log \min(a, b))$ پیدا کنیم. از آنجایی که این تابع شرکت‌پذیر است، برای پیدا کردن GCD بیش از دو عدد، می‌توانیم به این صورت عمل کنیم: $\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\}$ یکسان هستند.

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

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

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

اگر $a > b \geq 1$ و $b < F_n$ برای یک $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$ است، بنابراین عدد بزرگتر در هر تکرار الگوریتم حداقل به نصف کاهش می‌یابد. با به کار بردن این استدلال در موردی که GCD مجموعه‌ای از اعداد $a_1,\dots,a_n \leq C$ را محاسبه می‌کنیم، این امر به ما امکان می‌دهد زمان اجرای کل را به جای $O(n \log C)$ به صورت $O(n + \log C)$ تخمین بزنیم، زیرا هر تکرار غیربدیهی الگوریتم، کاندیدای فعلی GCD را حداقل با ضریب ۲ کاهش می‌دهد.

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

محاسبه کوچکترین مضرب مشترک (که معمولاً با LCM نشان داده می‌شود) را می‌توان با استفاده از فرمول ساده زیر به محاسبه GCD کاهش داد:

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

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

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

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

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

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

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

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

  • اگر هر دو عدد زوج باشند، می‌توانیم یک فاکتور دو را از هر دو خارج کرده و GCD اعداد باقی‌مانده را محاسبه کنیم: $\gcd(2a, 2b) = 2 \gcd(a, b)$.
  • اگر یکی از اعداد زوج و دیگری فرد باشد، می‌توانیم فاکتور ۲ را از عدد زوج حذف کنیم: $\gcd(2a, b) = \gcd(a, b)$ اگر $b$ فرد باشد.
  • اگر هر دو عدد فرد باشند، کم کردن یکی از دیگری، GCD را تغییر نمی‌دهد: $\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 دارد.

مسائل تمرینی