Алгоритм Евклида

Безумно часто требуется вычислять наибольший общий делитель. Можно, конечно, делать как в школе: раскладывать числа на простые множители, искать пересечение множеств и перемножать все числа в результате. Но такой подход максимально неэффективен.

Здесь я рассмотрю алгоритмы быстрого и очень быстрого нахождения наибольшего общего делителя.

Наибольший общий делитель чисел $a$ и $b$ — число

\gcd(a, b) \defeq \max\limits\{ g : g \divides a \land g \divides b \}

Когда оба числа равны $0$ , результат $\gcd(0, 0)$ не определен, так как подойдет любое число. Будем в таком случае считать, что $\gcd(0, 0) \defeq 0$ . Тогда $\gcd(a, 0) = a$ .

Тут надо сразу сказать важную вещь. Наибольший общий делитель существует не только для чисел, а для всего, что может делиться. Это определение, все дальнейшие утверждения и алгоритмы будут справедливы для любых коммутативных колец с единицей, в которых есть евклидова норма.

Несколько примеров таких колец. Целые числа $\ZZ$ и евклидова норма $a \mapsto |a|$ , кольца многочленов $\RR[x]$ и евклидова норма $P \mapsto \deg P$ , гауссовы числа $\ZZ[i]$ и евклидова норма $(a + bi) \mapsto a^2 + b^2$ .

Для нахождения наибольшего общего делителя двух чисел можно применить алгоритм Евклида. Основан этот алгоритм на следующем факте

\gcd(a, b) = \cases{a & \if b = 0 \\ \gcd(b, a - b) & \otherwise}

Для ускорения вычислений можно сразу вычитать столько, сколько возможно. Получаем формулу, которую уже можно использовать

\gcd(a, b) = \cases{a & \if b = 0 \\ \gcd(b, a \bmod b) & \otherwise}

Ну вот мы и получили алгоритм Евклида.

function gcd(int a, int b) -> int:
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

Можно избавиться от небольшого оверхеда в рекурсии, переписав через цикл

function gcd(int a, int b) -> int:
    while b > 0:
        a %= b
        swap a, b
    return a

Давайте грубо оценим время работы алгоритма. Каждую итерацию мы берем остаток от деления наибольшего числа на наименьшее, поэтому наибольшее число уменьшается минимум в два раза.

Отсюда получается, что алгоритм работает за время $O\left( \log \big( \min\limits(a, b) \big) \right)$ .

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

Быстрый алгоритм Евклида

Для быстрого вычисления наибольшего общего делителя двух чисел можно применить следующий факт

\gcd(a \cdot b, a \cdot c) = a \cdot \gcd(b, c)