90 lines
3.7 KiB
Python
90 lines
3.7 KiB
Python
|
||
# Обычные алгоритм Евклида:
|
||
# Основывается на утверждениях:
|
||
# 1. gcd(a, b) = gcd(b, a % b) -> Лемма
|
||
# 2. gcd(b, 0) = b -> Очевидно
|
||
def eucl_rec(a, b):
|
||
if b == 0:
|
||
return a
|
||
return eucl_rec(b, a % b)
|
||
|
||
def eucl_it(a, b):
|
||
while a % b != 0:
|
||
a, b = b, a % b
|
||
return b
|
||
###
|
||
|
||
# Расширенный алгоритм Евклида (вычисляются еще и коэф-ы линейного представления НОД)
|
||
# Для gcd любых чисел есть такие целые x, y, что a * x + b * y = gcd(a, b)
|
||
# Они тут и находятся параллельно с НОД
|
||
def ext_eucl(a, b):
|
||
r0, r1 = a, b
|
||
x0, y0, x1, y1 = 1, 0, 0, 1
|
||
while r1 != 0:
|
||
## Вычисление коэффициентов
|
||
q = r0 // r1
|
||
x0, x1 = x1, x0 - q * x1 # Присваивания происходят одновременно
|
||
y0, y1 = y1, y0 - q * y1 # Присваивания происходят одновременно
|
||
##
|
||
r1, r0 = r0 % r1, r1 # НОД вычисляется на этой строчке (см. утв. из обычного алг. Евклида)
|
||
# Инвариант который поддерживается на каждой итерации
|
||
print(f'{x0}*{a}+{y0}*{b}={r0}')
|
||
return x0, y0, r0
|
||
|
||
def ext_eucl_rec(a, b):
|
||
if b == 0:
|
||
return a, 1, 0
|
||
gcd, x, y = ext_eucl_rec(b, a % b)
|
||
# Поддержание инварианта x*a+y*b=gcd(a, b)
|
||
x = y
|
||
# Объяснение почему x = y:
|
||
# эта рекурсивная функция (если не считать x,y) выводит нечто такое
|
||
# ?*6+?*3=3 подставляем 0,1 => будет 0*6+1*3=3
|
||
# ?*9+?*6=3 подставляем 1,-1 => будет 1*9+-1*6=3
|
||
# ?*15+?*9=3 подставляем -1,2 => будет -1*15+2*9=3
|
||
# ?*39+?*15=3 подставляем 2,-5 => будет 2*39+-5*15=3
|
||
# Можно заметить что X следующей строки становится игриком предыдущей
|
||
# а вот Y уже надо подбирать
|
||
y = (gcd - x*a) // b # просто выражаем y из формулы x*a+y*b=gcd(a, b)
|
||
print(f'{x}*{a}+{y}*{b}={gcd}')
|
||
return gcd, x, y
|
||
|
||
def bin_eucl_rec(a, b):
|
||
# Базовый случай
|
||
if a == 0:
|
||
return b
|
||
if b == 0:
|
||
return a
|
||
if (a & 1) == 0 and (b & 1) == 0: # Оба числа четные
|
||
return bin_eucl_rec(a >> 1, b >> 1) << 1
|
||
if (a & 1) == 0: # a четное, b нечетное
|
||
return bin_eucl_rec(a >> 1, b)
|
||
if (b & 1) == 0: # a нечетное, b четное
|
||
return bin_eucl_rec(a, b >> 1)
|
||
if a > b: # Оба числа нечетные и a > b
|
||
return bin_eucl_rec(a - b, b)
|
||
return bin_eucl_rec(b - a, a) # Оба числа нечетные и b > a
|
||
|
||
def ext_eucl_trunc(a, b):
|
||
r0, r1 = a, b
|
||
x0, y0, x1, y1 = 1, 0, 0, 1
|
||
while r1 != 0:
|
||
## Вычисление коэффициентов
|
||
q = r0 // r1
|
||
x0, x1 = x1, x0 - q * x1 # Присваивания происходят одновременно
|
||
y0, y1 = y1, y0 - q * y1 # Присваивания происходят одновременно
|
||
##
|
||
r1, r0 = r0 % r1, r1 # НОД вычисляется на этой строчке (см. утв. из обычного алг. Евклида)
|
||
|
||
if r1 > r0 >> 1:
|
||
r1 = r0 - r1
|
||
x1 = x0 - x1
|
||
y1 = y0 - y1
|
||
|
||
# Инвариант который поддерживается на каждой итерации
|
||
print(f'{x0}*{a}+{y0}*{b}={r0}')
|
||
return x0, y0, r0
|
||
|
||
|
||
|