Информатика / математика и код

Расширенный алгоритм Евклида

Поиск не только НОД, но и способа его разложения.

Теоретическое обоснование

Сегодня я попытаюсь разобрать алгоритм Евклида в его расширенном варианте. Что это значит? Что значит "расширенный"? Это просто. Вот мы нашли НОД(a,b)=d, но нам надо узнать вот что:

$$ ax + by = d $$

То есть, нам надо найти такой x и такой y, при умножении на которое у нас получится d (см. формулу выше). Вот пример. Найдем НОД(3,12) и он равен 3, потому что как 12, так и 3 делятся на 3. Хорошо, мы его нашли, выпишем:

$$ 3x + 12y = 3 $$

Где a=3, b=12, d=НОД(3,12). И как теперь узнать, какие будут x, y? Автор классной книги, его звать Кнут (и пряник, ага), нашел этот отличный метод и назвал его "Расширенный алгоритм Евклида". Начнем по-порядку. Сначала надо вспомнить то выражение, которое мы разбирали в прошлой статье про алгоритм Евклида:

$$ a = bq + r $$

Где НОД(a,b) = НОД(b,r). Это было доказано ранее. Теперь посмотрим, как происходит обычно поиск НОД по этому алгоритму. Как мы помним, чтобы перейти к следущей итерации, надо разделить "a" на "b", получить q, и остаток, и применить их как новые "a" и "b".


Шаг Поиск НОД Разложение остатков Описание
1 \( a = bq_1 + r_1 \) \( r_1 = ax_1 + by_1 \) \( q_1 = [a / b], \ r_1 = a - bq_1 \), теперь они вместо \((a, b)\)
2 \( b = r_1q_2 + r_2 \) \( r_2 = ax_2 + by_2 \) \( q_2 = [b / r_1], \ r_2 = b - r_1q_2 \), теперь они вместо \((b, r_1)\)
3 \( r_1 = r_2q_3 + r_3 \) \( r_3 = ax_3 + by_3 \) \( q_3 = [r_1 / r_2], \ r_3 = r_1 - r_2q_3 \), теперь они вместо \((r_1, r_2)\)
4 \( r_2 = r_3q_4 + r_4 \) \( r_4 = ax_4 + by_4 \) \( q_4 = [r_2 / r_3], \ r_4 = r_2 - r_3q_4 \), теперь они вместо \((r_2, r_3)\)
....
\(n - 1\) \( r_{n-3} = r_{n-2}q_{n-1} + r_{n-1} \) \( r_{n-1} = ax_{n-1} + by_{n-1} \) \( q_{n-2} = [r_{n-3} / r_{n-2}], \ r_{n-1} = r_{n-3} - r_{n-2}q_{n-1} \), теперь они вместо \((r_{n-3}, r_{n-2})\)
\(n\) \( r_{n-2} = r_{n-1}q_{n} \) \( r_{n} = 0 \) Точка остановки

Все, что происходит тут - это просто магия. Обычная магия, которая происходит в фентези. Ложим в пробирку немного математических ингредиентов и начинаем смешивать. Немного выстоять... и зелье готово!

Теперь немного придется включить воображение и приглядеться к формулам. Мы заметили, что:

$$ r_{n} = r_{n-2} - r_{n-1}q_{n} $$

И еще то, что:

$$ r_{j} = ax_j + by_j $$

И поэтому \(r_{j-2} = ax_{j-2} + by_{j-2}\) и \(r_{j-1} = ax_{j-1} + by_{j-1}\).

Давайте теперь подставим в формулу выше формулу ту, что ниже:

$$ r_{n} = (ax_{j-2} + by_{j-2}) - (ax_{j-1} + by_{j-1})q_{n} $$

Раскроем скобки и перегруппируем:

$$ r_{n} = a(x_{j-2} - x_{j-1}q_{n}) + b(y_{j-2} - by_{j-1}q_{n}) $$

Теперь приглядимся внимательно... так вот что мы видим? Мы видим, что коэффициентами перед a и b у нас стоят \(x_j\) и \(y_j\)!:

$$ x_j = x_{j-2} - x_{j-1}q_{n} \\ y_j = y_{j-2} - y_{j-1}q_{n} $$

Да это просто шикарно! То есть, чтобы вычислить следующий \(x_{j+1}\) и \(y_{j+1}\), нужно всего лишь знать предыдущие 2! Вот в этом и есть сила расширенного алгоритма Евклида.

Тут встает вопрос. Вот мы хотим вычислить \(x_{1}\) и \(y_{1}\), то есть, нам нужны коэффициенты (\(x_{0}\), \(y_{0}, x_{-1}\), \(y_{-1}\)), и где их достать? А тут все просто. Взглянем на таблицу. У нас \(r_3 = r_1 - r_2q_3\), то если мы попробуем найти \(r_2\), то в таком случае \(r_1=a\), и \(r_2=b \), судя по таблице.

Это значит, что:

$$ r_{-1}=ax_{-1}+by_{-1}=a \\ r_{0}=ax_{0}+by_{0}=b $$

Отсюда:

$$ x_{-1}=1, y_{-1}=0 \\ x_{0}=0, y_{0}=1 $$

Вот такой вот он, расширенный алгоритм Евклида. И результатом НОД будет \(r_{n-1} = ax_{n-1} + by_{n-1}\).

Программная реализация

А теперь время программного обеспечения.

// Расширенный НОД
int extnod(int a, int b, int* x, int* y) {

    int q, r;
    int x2 = 1, y2 = 0, // x(i-2)=1, y(i-2)=0
        x1 = 0, y1 = 1; // x(i-1)=0, y(i-1)=1

    do {

        // Алгоритм Евклида
        q = a / b;
        r = a % b;
        a = b; b = r;

        // Расширенный алгоритм Евклида
        *x = x2 - x1*q; // x(i) = x(i-2) - x(i-1)*q
        *y = y2 - y1*q; // y(i) = y(i-2) - y(i-1)*q

        // "Сдвиг истории" назад
        x2 = x1; y2 = y1; // Старый x(i-1), y(i-1) перемещается в x(i-2), y(i-2)
        x1 = *x; y1 = *y; // Новый  x(i), y(i) становится x(i-1), y(i-1)

    } while (r > 0); // Перебирать, пока не станет r = 0

    // И записать разультат, где x = x(i-1), y = y(i-1)
    // т.к. ранее мы "сдвинули" в (x2, y2) старые (x1, y1)
    *x = x2; *y = y2;

    // Вернуть значение НОД
    return a;
}

Яндекс.Метрика