Хамгийн их ерөнхий хуваагчийг олох Евклидийн алгоритм¶

Сөрөг биш $a$ ба $b$ хоёр бүхэл тоо өгөгдсөн үед бид тэдгээрийн ХИЕХ (хамгийн их ерөнхий хуваагч), өөрөөр хэлбэл $a$ ба $b$ хоёуланг нь хуваадаг хамгийн том тоог олох ёстой. Үүнийг ихэвчлэн $\gcd(a, b)$ гэж тэмдэглэдэг. Математикийн хувьд дараах байдлаар тодорхойлогдоно:

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

(энд "$\mid$" тэмдэг нь хуваагдахыг илэрхийлнэ, өөрөөр хэлбэл "$k \mid a$" гэдэг нь "$k$ нь $a$-г хуваана" гэсэн үг)

Хэрэв нэг тоо нь тэг, нөгөө нь тэг биш бол тэдгээрийн хамгийн их ерөнхий хуваагч нь тодорхойлолтоор хоёр дахь тоо байна. Хоёул тэг байвал хамгийн их ерөнхий хуваагч нь тодорхойгүй (дурын том тоо байж болно), гэвч $\gcd$-ийн associativity-г хадгалахын тулд түүнийг мөн тэг гэж тодорхойлох нь тохиромжтой. Эндээс энгийн дүрэм гарна: хэрэв нэг тоо нь тэг бол хамгийн их ерөнхий хуваагч нь нөгөө тоо байна.

Доор авч үзэх Евклидийн алгоритм нь $a$ ба $b$ хоёр тооны хамгийн их ерөнхий хуваагчийг $O(\log \min(a, b))$-д олох боломж олгодог. Энэ функц нь associativity-тай тул хоёроос олон тооны ХИЕХ-ийг олохын тулд $\gcd(a, b, c) = \gcd(a, \gcd(b, c))$ гэх мэтчилэн тооцоолж болно.

Энэ алгоритмыг анх Евклидийн "Эхлэлүүд" номд (МЭӨ 300 оны орчим) тайлбарласан боловч алгоритм үүнээс ч эрт үүссэн байх магадлалтай.

Алгоритм¶

Анх Евклидийн алгоритмыг дараах байдлаар томьёолсон: нэг тоо нь тэг болтол том тооноос бага тоог хасах. Үнэхээр хэрэв $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{хэрэв }b = 0 \\ \gcd(b, a \bmod b),&\text{эсрэг тохиолдолд.}\end{cases}$$

Implementation¶

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

Using the ternary operator in C++, we can write it as a one-liner.

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

And finally, here is a non-recursive implementation:

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

Note that since C++17, gcd is implemented as a standard function in C++.

Time Complexity¶

Алгоритмын ажиллах хугацааг Ламегийн теоремоор үнэлдэг бөгөөд энэ теорем нь Евклидийн алгоритм ба Фибоначчийн дараалал хоёрын хооронд гайхалтай холбоо тогтоодог:

Хэрэв $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)}$$

Ингэснээр ХБЕҮ-г Евклидийн алгоритм ашиглан ижил time complexity-тэйгээр тооцоолж болно:

$a$-г эхлээд ХИЕХ-д хуваах замаар бүхэл тооны халилтаас ухаалгаар зайлсхийсэн боломжит хэрэгжүүлэлтийг энд үзүүлэв:

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

Хоёртын ХИЕХ¶

Хоёртын ХИЕХ алгоритм нь ердийн Евклидийн алгоритмын оновчлол юм.

Ердийн алгоритмын удаан хэсэг нь модулийн үйлдлүүд юм. Модулийн үйлдлийг бид $O(1)$ гэж үздэг ч нэмэх, хасах, битийн үйлдэл зэрэг энгийн үйлдлүүдээс хамаагүй удаан байдаг. Тиймээс тэдгээрээс зайлсхийвэл дээр.

Модулийн үйлдлээс зайлсхийсэн хурдан ХИЕХ алгоритм зохиох боломжтой нь тогтоогдсон. Энэ нь хэдэн шинж чанарт тулгуурладаг:

Хэрэв хоёр тоо хоёулаа тэгш бол хоёулангаас нь хоёрыг ялган авч, үлдсэн тоонуудын ХИЕХ-ийг тооцоолж болно: $\gcd(2a, 2b) = 2 \gcd(a, b)$.
Хэрэв нэг тоо нь тэгш, нөгөө нь сондгой бол тэгш тооноос 2 үржигдэхүүнийг хасаж болно: $b$ сондгой бол $\gcd(2a, b) = \gcd(a, 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++17 нь numeric толгой файлд std::gcd функцтэй.