Агуулгыг алгасах

Өргөтгөсөн Евклидийн алгоритм

Евклидийн алгоритм нь сөрөг биш $a$ ба $b$ хоёр бүхэл тооны хамгийн их ерөнхий хуваагчийг (ХИЕХ) л тооцоолдог бол өргөтгөсөн хувилбар нь ХИЕХ-ийг $a$ ба $b$-ээр илэрхийлэх аргыг, өөрөөр хэлбэл дараах нөхцөлийг хангах $x$ ба $y$ коэффициентүүдийг бас олдог:

$$a \cdot x + b \cdot y = \gcd(a, b)$$

Безугийн адилтгал-ын дагуу ийм илэрхийллийг үргэлж олж чадна гэдгийг анхаарах нь чухал. Жишээ нь $\gcd(55, 80) = 5$ тул $5$-г $55$ ба $80$ гишүүдтэй шугаман комбинац хэлбэрээр илэрхийлж болно: $55 \cdot 3 + 80 \cdot (-2) = 5$

Энэ бодлогын илүү ерөнхий хэлбэрийг Шугаман Диофантын тэгшитгэл өгүүлэлд авч үзсэн. Тэр өгүүлэл энэ алгоритм дээр тулгуурлана.

Алгоритм

Энэ хэсэгт бид $a$ ба $b$-ийн ХИЕХ-ийг $g$ гэж тэмдэглэнэ.

Анхны алгоритмд оруулах өөрчлөлт нь маш энгийн. Алгоритмыг эргэн санавал алгоритм $b = 0$ ба $a = g$ үед дуусдаг. Эдгээр параметрийн хувьд коэффициентүүдийг амархан олж болно, тухайлбал $g \cdot 1 + 0 \cdot 0 = g$.

Эдгээр $(x, y) = (1, 0)$ коэффициентээс эхлээд рекурсив дуудалтуудыг ухраан явж болно. Бидний хийх ёстой зүйл бол $(a, b)$-ээс $(b, a \bmod b)$ рүү шилжих үед $x$ ба $y$ коэффициентүүд хэрхэн өөрчлөгдөхийг тодорхойлох явдал юм.

$(b, a \bmod b)$-ийн хувьд $(x_1, y_1)$ коэффициентүүдийг оллоо гэж үзье:

$$b \cdot x_1 + (a \bmod b) \cdot y_1 = g$$

мөн бид $(a, b)$-ийн хувьд $(x, y)$ хосыг олохыг хүсэж байна:

$$ a \cdot x + b \cdot y = g$$

$a \bmod b$-г дараах байдлаар илэрхийлж болно:

$$ a \bmod b = a - \left\lfloor \frac{a}{b} \right\rfloor \cdot b$$

Энэ илэрхийллийг $(x_1, y_1)$-ийн коэффициентийн тэгшитгэлд орлуулбал:

$$ g = b \cdot x_1 + (a \bmod b) \cdot y_1 = b \cdot x_1 + \left(a - \left\lfloor \frac{a}{b} \right\rfloor \cdot b \right) \cdot y_1$$

ба гишүүдийг эмхэтгэсний дараа:

$$g = a \cdot y_1 + b \cdot \left( x_1 - y_1 \cdot \left\lfloor \frac{a}{b} \right\rfloor \right)$$

Бид $x$ ба $y$-ийн утгыг оллоо:

$$\begin{cases} x = y_1 \\ y = x_1 - y_1 \cdot \left\lfloor \frac{a}{b} \right\rfloor \end{cases} $$

Implementation

int gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

The recursive function above returns the GCD and the values of coefficients to x and y (which are passed by reference to the function).

This implementation of extended Euclidean algorithm produces correct results for negative integers as well.

Iterative version

It's also possible to write the Extended Euclidean algorithm in an iterative way. Because it avoids recursion, the code will run a little bit faster than the recursive one.

int gcd(int a, int b, int& x, int& y) {
    x = 1, y = 0;
    int x1 = 0, y1 = 1, a1 = a, b1 = b;
    while (b1) {
        int q = a1 / b1;
        tie(x, x1) = make_tuple(x1, x - q * x1);
        tie(y, y1) = make_tuple(y1, y - q * y1);
        tie(a1, b1) = make_tuple(b1, a1 - q * b1);
    }
    return a1;
}

If you look closely at the variables a1 and b1, you can notice that they take exactly the same values as in the iterative version of the normal Euclidean algorithm. So the algorithm will at least compute the correct GCD.

To see why the algorithm computes the correct coefficients, consider that the following invariants hold at any given time (before the while loop begins and at the end of each iteration):

$$x \cdot a + y \cdot b = a_1$$
$$x_1 \cdot a + y_1 \cdot b = b_1$$

Let the values at the end of an iteration be denoted by a prime ($'$), and assume $q = \frac{a_1}{b_1}$. From the Euclidean algorithm, we have:

$$a_1' = b_1$$
$$b_1' = a_1 - q \cdot b_1$$

For the first invariant to hold, the following should be true:

$$x' \cdot a + y' \cdot b = a_1' = b_1$$
$$x' \cdot a + y' \cdot b = x_1 \cdot a + y_1 \cdot b$$

Similarly for the second invariant, the following should hold:

$$x_1' \cdot a + y_1' \cdot b = a_1 - q \cdot b_1$$
$$x_1' \cdot a + y_1' \cdot b = (x - q \cdot x_1) \cdot a + (y - q \cdot y_1) \cdot b$$

By comparing the coefficients of $a$ and $b$, the update equations for each variable can be derived, ensuring that the invariants are maintained throughout the algorithm.

At the end we know that $a_1$ contains the GCD, so $x \cdot a + y \cdot b = g$. Which means that we have found the required coefficients.

You can even optimize the code more, and remove the variable $a_1$ and $b_1$ from the code, and just reuse $a$ and $b$. However if you do so, you lose the ability to argue about the invariants.

Дасгал бодлогууд