Алгоритм Евклида — реализация на Python

Алгоритм Евклида — это алгоритм, который используется для нахождения наибольшего делителя двух целых чисел. Он часто используется как в обучающих целях, так и в прикладных задачах.

Существует несколько видов алгоритма: обычный, расширенный и бинарный. Все виды алгоритма Евклида легко реализуются на языке программирования Python.

Классический алгоритм Евклида

Этот вид алгоритма Евклида является самым простым, он был придуман более 1300 лет назад. С появлением электронно-вычислительных машин расширились возможности по применению алгоритма Евклида, возникли новые более эффективные его реализации.

Алгоритм состоит из определенного количества шагов, количество которых зависит от размера входных данных.

Реализация на Python

Существует несколько реализаций классического алгоритма Евклида, которые основаны на использовании различных операторов и возможностей языка Python (остаток от деления, вычитание, рекурсия). Эти реализации отличаются незначительно, сильные различия в эффективности наблюдаются только при специфических входных данных.

Реализация с помощью остатка от деления

Идея такой реализации достаточна проста, алгоритм уменьшает числа до тех пор, пока одно из них не станет равно нулю, а другое искомому делителю. Для этого используется цикл while, в котором большее число делится на меньшее и становится равным остатку от деления. Таким образом, функция вернёт наибольший общий делитель (НОД) её двух аргументов.

Код алгоритма Евклида на Python:

def gcd_rem_division(num1, num2):
    while num1 != 0 and num2 != 0:
        if num1 >= num2:
            num1 %= num2
        else:
            num2 %= num1
    return num1 or num2

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

В каждой новой итерации большее число становится меньшим и наоборот. Возьмём числа 168 и 105 и распишем работу программы вручную:

• 1 итерация:
  168 % 105 = 63
  105
• 2 итерация:
  63
  105 % 63 = 42
• 3 итерация:
  63 % 42 = 21
  42
• 4 итерация:
  42 % 21 = 0
  21

После 4 итерации алгоритм завершает свою работу, так как одно из чисел равно нулю, второе же число равно наибольшему общему делителю, в нашем случае это 21. Проверим работу программы:

a = gcd_rem_division(168, 105)
print(a) # Выведет 21

Реализация с помощью вычитания

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

Код вычисления НОД на Python:

def gcd_subtraction(num1, num2):
    while num1 != 0 and num2 != 0:
        if num1 >= num2:
            num1 -= num2
        else:
            num2 -= num1
    return num1 or num2

Также распишем работу программы с числами 168 и 105:

• 1 итерация:
  168 — 105 = 63
  105
• 2 итерация:
  63
  105 — 63 = 42
• 3 итерация:
  63 — 42 = 21
  42
• 4 итерация:
  21
  42 — 21 = 21
• 5 итерация:
  21 — 21 = 0
  21

Видно, что до 4 итерации результаты работы обоих версий алгоритма полностью совпадают. Отличия начинаются, когда в 4 итерации вместо 0 и 21, получается числа 21 и 21, из-за чего в алгоритме с вычитанием добавляется дополнительная итерация, но это не значит, что он работает менее эффективнее.

Проверка работы программы:

a = gcd_subtraction(168, 105)
print(a) # Выведет 21

Реализация с помощью рекурсии

Суть алгоритма схожа с реализацией через остаток от деления, однако вместо цикла while используется рекурсия.

Код программы на Python нахождения НОД с помощью рекурсии:

def gcd_recursion(num1, num2):
    if num1 == 0:
        return num2
    return gcd_recursion(num2 % num1, num1)

Первое, что стоит заметить, на ноль проверяется только num1. Важно понять, что числа постоянно меняются местами. В качестве первого числа в рекурсивный вызов функции передаётся num2 % num1, вспомним 4 итерацию в алгоритме через остаток от деления:

• 4 итерация:
  42 % 21 = 0 — num1
  21 — num2

То есть рекурсивный алгоритм проверит число num1 на ноль, получит True и вернёт значение num2, которое и будет являться наибольшим общим делителем.

Особенности алгоритма: простые числа

Если два переданных числа не имеют общих делителей, то алгоритм возвращает единицу. Действительно, ведь каждое число делится на единицу. Например, числа 35 и 18 не имеют общих делителей:

• 35 = 5 * 7 * 1
• 18 = 2 * 9 * 1 = 3 * 6 * 1

Алгоритм будет возвращать единицу, если оба переданных числа являются простыми и не равны друг другу. Простые числа делятся только на себя и на единицу.

Если алгоритм получает на вход одно простое число, это не значит, что он обязательно вернет единицу:

• 5 и 15: число 5 является простым, а 15 — нет, алгоритм вернет наибольший общий делитель 5.
• 5 и 21: число 5 — простое, а 21 — нет, будет возвращена единица, потому что 21 не делится на 5.
• 3 и 21: число 3 — простое, 21 — нет, будет возвращено число 3, потому что 21 делится на 3.

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

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

Расширенный алгоритм также находит наибольший общий делитель, а ещё он определяет два коэффициента x и y, такие что:

ax + by = gcd(a,b), где gcd – это функция по нахождения НОД.

Иными словами, алгоритм находит наибольший делитель и его линейное представление.

gcd – это аббревиатура, которую часто используют для обозначения функции по назначению НОД:

• g – Greatest (наибольший);
• c – Common (общий);
• d – Divisor (делитель).

Реализация на Python

Код программы выглядит так:

def gcd_extended(num1, num2):
    if num1 == 0:
        return (num2, 0, 1)
    else:
        div, x, y = gcd_extended(num2 % num1, num1)
    return (div, y - (num2 // num1) * x, x)

Проверяем работу кода:

a = gcd_extended(426, 334)
print(f'Делитель равен {a[0]}, x = {a[1]}, y = {a[2]}')

Делитель равен 2, x = 69, y = -88

Подставим полученные коэффициенты в формулу, тогда:

69*426-334*88 = 2

Действительно, коэффициенты и делитель найдены правильно. Но как работает алгоритм?

Сначала проверяется, равно ли первое число нулю, если это так, то второе число является делителем, а коэффициенты равны 0 и 1, так как «num1 * x + num2 * y = y» в том случае, если y = 1, а левое произведение равно нулю.

Функция возвращает три числа: делитель, коэффициент x и коэффициент y. Для её реализации используется рекурсия, делитель получается тем же образом, что и в классическом рекурсивным алгоритме, а коэффициенты рекурсивно вычисляются по формулам:

• x = y — (num2 // num1) * x
• y = x

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

Суть бинарного алгоритма точно такая же — найти наибольший делитель. От классического он отличается только способом реализации.

Сложность алгоритма по прежнему определяется функций O(h²), однако реальные тесты показывают, что бинарный алгоритм эффективнее классического на 60%, это обусловлено различиями в реализациях обычных арифметических операций и сдвигов.

Реализация на Python

Бинарный алгоритм имеет довольно сложную реализацию по сравнению со всеми предыдущими, однако это окупается его эффективностью.

Код на Python:

def binary_gcd(num1, num2):
    shift = 0
    # Если одно из чисел равно нулю, делитель - другое число
    if num1 == 0:
        return num2
    if num2 == 0:
        return num1
    # Если num1 = 1010, а num2 = 0100, то num1 | num2 = 1110
    # 1110 & 0001 == 0, тогда происходит сдвиг, который фиксируется в shift
    while (num1 | num2) & 1 == 0:
        shift += 1
        num1 >>= 1
        num2 >>= 1
    #Если True, значит num1 - четное, иначе - нечетное
    while num1 & 1 == 0:
        # если нечетное, сдвигаем на один бит
        num1 >>= 1
    while num2 != 0:
        # пока число нечётное, сдвигаем на один бит
        while num2 & 1 == 0:
            num2 >>= 1
        # если первое число больше второго
        if num1 > num2:
            # меняем их местами
            num1, num2 = num2, num1
        #теперь первое число меньше второго, вычитаем
        num2 -= num1
    # возвращаем число, перед этим сдвинув его биты на shift
    return num1 << shift

Результат выполнения не будет отличаться от результатов, полученных другими реализациями.

Тест скорости выполнения

Для выполнения теста воспользуемся функцией monotonic модуля time. Подробнее про неё и про то, как засечь время выполнения программы описано здесь.

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

Код проверки следующий:

start = time.monotonic()
for i in range(10000):
    binary_gcd(168024, 105023)
result = time.monotonic() - start
print("binary time : {:>.3f}".format(result) + " seconds")
start = time.monotonic()
for i in range(10000):
    gcd_rem_division(168024, 105023)
result = time.monotonic() - start
print("standard time: {:>.3f}".format(result) + " seconds")

Результат теста выглядит следующим образом:

binary time : 0.219 seconds
standard time: 0.094 seconds

Из результатов видно, что реализация классического алгоритма на Python быстрее, чем бинарного. Так что лучше на Python использовать классический алгоритм Евклида, а если программировать на C++ и важна скорость выполнения, то тогда использовать бинарный.

Заключение

Алгоритм Евклида позволяет эффективно находить общие делители чисел. За много лет его существования было придумано несколько различных видов, которые могут отличаться по способу реализации и эффективности.

Любой вид алгоритма Евклида можно реализовать на языке Python без использования сторонних библиотек.