Алгоритм евклида реализация python

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

Расширенный алгоритм Евклида вычисляет НОД двух заданных целых чисел и их коэффициенты Безу.

На языке Си [ править ]

#include int main() int a, b, p=1, q=0, r=0, s=1, x, y; scanf("%d %d",&a,&b); while (a && b)  if (a>=b)  a = a - b; p = p - r; q = q - s; > else  b = b - a; r = r - p; s = s - q; > > if (a)  x = p; y = q; >else  x = r; y = s; > printf("%d %d\n",x,y); return 0; > 

На языке Python, итерационная версия [ править ]

def bezout(a, b): '''An implementation of extended Euclidean algorithm. Returns integer x, y and gcd(a, b) for Bezout equation: ax + by = gcd(a, b). ''' x, xx, y, yy = 1, 0, 0, 1 while b: q = a // b a, b = b, a % b x, xx = xx, x - xx*q y, yy = yy, y - yy*q return (x, y, a) 

На языке Python, рекурсивная версия [ править ]

def bezout_recursive(a, b): '''A recursive implementation of extended Euclidean algorithm. Returns integer x, y and gcd(a, b) for Bezout equation: ax + by = gcd(a, b). ''' if not b: return (1, 0, a) y, x, g = bezout_recursive(b, a % b) return (x, y - (a // b) * x, g) 

На языке Racket, итеративная версия [ править ]

(define (bezout-gcd a b) ; Переменные на каждом шаге алгоритма: ; r-1 - r_ = a * s + b * t; ; r-2 - r_ = a * u + b * v. (define (step r-2 s t r-1 u v) (if (zero? r-1) ; Если r-1 = 0, то НОД(a, b) = r-2 и его коэффициенты Безу (КБ) найдены, ; возврат этой тройки (values r-2 s t) ; Иначе, нужно вычислить: ; - следующий остаток r = r-1 - r-2 * q (1); ; - и КБ для r, по выражению (1) и известным КБ для r-1, r-2. ; На следующем шаге: ; - r-2 ← r-1 (с коэффициентами u и v), ; - и r-1 ← r с новыми коэффициентами. (let-values (((q r) (quotient/remainder r-2 r-1))) (step r-1 u v r (- s (* q u)) (- t (* q v)))))) ; На первом шаге алгоритма остатками являются a и b с очевидными начальными ; КБ. (step a 1 0 b 0 1)) 

Источник

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

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

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

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

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

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

Сложность алгоритма выражается функцией O(h2), где h – это количество десятичных цифр в наименьшем числе, наибольший делитель которых ищется алгоритмом.

Реализация на 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 итерацию в алгоритме через остаток от деления:

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация на 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'Делитель равен , x = , y = ') Делитель равен 2, x = 69, y = -88

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

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

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

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

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

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

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

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

Однако ускорение бинарного по сравнению с классическим алгоритмом справедливо не для кода написанного на Python. Ниже, после описания его реализации проведём тест скорости выполнения для Python.

Реализация на 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 
Результат выполнения не будет отличаться от результатов, полученных другими реализациями.
Тест скорости выполнения
Для выполнения теста воспользуемся функцией 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 без использования сторонних библиотек.
 
Источник
 
Читайте также:  Python module package name