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

@cypher111 · Регистрация: 29.03.2022

Студворк — интернет-сервис помощи студентам

Необходимо разработать расширенный бинарный алгоритм Евклида, то есть такой, который кроме НОД еще считает коэффициенты х и у, такие, что НОД = a*x + b*y. Например, для a = 60, b = 12, имеем: 12 = 0*60 + 1*12. Вот итеративный расширенный алгоритм Евклида:

Python
1
2
3
4
5
6
7
8
def gcd(a, b):
    x, xx, y, yy = 1, 0, 0, 1
    while b != 0:
        q = a // b
        a, b = b, a % b
        x, xx = xx, x - xx*q
        y, yy = yy, y - yy*q
    return a, x, y

Вот итеративный алгоритм Евклида (не расширенный):

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def binary_gcd(A, B):
    k = 1
    while (A != 0) and (B != 0):
        if A > B:
            q = a // b
        else:
            q = b // a
 
        while (A % 2 == 0) and (B % 2 == 0):
            A /= 2
            B /= 2
            k *= 2
 
        while A % 2 == 0:
            A /= 2
        while B % 2 == 0:
            B /= 2
 
        if A >= B:
            A -= B
        else:
            B -= A
 
    return B * k

По большому счету необходимо объединить оба этих алгоритма, но при моем варианте совмещения (строки 3, 26, 27) коэффициенты получаются не очень:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def binary_gcd(A, B):
    k = 1
    x, xx, y, yy = 1, 0, 0, 1
 
    while (A != 0) and (B != 0):
        if A > B:
            q = a // b
        else:
            q = b // a
 
        while (A % 2 == 0) and (B % 2 == 0):
            A /= 2
            B /= 2
            k *= 2
 
        while A % 2 == 0:
            A /= 2
        while B % 2 == 0:
            B /= 2
 
        if A >= B:
            A -= B
        else:
            B -= A
 
        x, xx = xx, x - xx * q
        y, yy = yy, y - yy * q
 
    return B * k, x, y

тогда, если a = 60, b = 12, алгоритм выводит (12.0, 1, -5), хотя должно быть (12.0, 0, 1). Как чинить?

@Aael · 12.09.2022, 04:23

Сообщение от cypher111

По большому счету необходимо объединить оба этих алгоритма

Так нельзя делать, эти формулы для перехода GCD(A,B)=GCD(B,A%B). Вам же нужно вывести формулы для тех переходов, которые используются в бинарном алгоритме. Попробую объяснить для рекурсивного алгоритма:

бла-бла-бла

1. Переход GCD(2A,2B) = 2 GCD(A,B). Нужно подобрать x,y которые бы удовлетворяли уравнению:
x·(2A)+y·(2B)=g, при условии что мы знаем x' и y' удовлетворящие соотношению:
x'A + y'B=g', умножаем его на 2 и сразу получаем похожее на то что ищем:
x'·(2A)+y'·(2B)=2g'=g, т.е. пара x',y' является одним из искомых частных решений и при данном переходе коэффициенты можно не менять.

Пример, ищем GCD(6,8). 6 и 8 оба чётные, значит запускаем GCD(3,4). Он возвращает x=-1,y=1,g=1 (как вариант). Это значит, что для 3,4 выполняется : (-1)·3+(1)·4=1=GCD(3,4), а нам нужно такоеже для 6 и 8. Так вот эти x и y подойдут для 6 и 8: (-1)·6+(1)·8=2=GCD(6,8)

2. Переход GCD(2A,B) = GCD(A,B) где B - нечётное. Опять же, нужно найти x,y которые:
x·(2A)+y·B=g, а мы знаем x' и y' которые:
x'·A + y'·B=g
2.1 если x' делится нацело на два, то можно сделать так:
(x'/2)·(2A) + y'·B=g, видим, что x=x'/2 и y=y' удовлетворяют нашему уранению для x и y
2.2 если x' нечётный, то к последнему уравнению добавим и вычтем A·B:
x'·A - A·B + y'·B + A·B = g, группируем:
(x'-B)·A + (y'+A)·B = g, но т.к. x' и B нечётные, то (x'-B) чётное, делаем так:
(x'-B)/2·(2A) + (y'+A)·B = g. Отсюда x=(x'-B)/2, y=y'+A - искомые x,y

3. Еще есть такой переход GCD(A,B) = GCD(A-B,B), тоже не сложно вывести.

Но, чтобы из рекусивного алгоритма сделать итеративный с константной памятью, нужно еще для этой последовательности (xi,yi) обратные формулы выписать. Ну и фишка алгоритма в том, что он использует не медленные умножение и деление, а быстрые битовые операции (>>1 вместо //2), на питоне они, возможно, с одинаковой скоростью выполняются - я не знаю..

рекурсивный алгоритм (ест память)

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def ext_gcd(a, b):
    if a == 0: return 1, 1, b
    if b == 0: return 1, 1, a
    if not a&1 | b&1:
        # оба чётные - x и y не трогаем, gcd удваеваем
        x, y, g = ext_gcd(a>>1, b>>1)
        return x, y, g<<1
    elif not a&1:
        # a - чётное, b - нечётное
        x, y, g = ext_gcd(a>>1, b)
        return (x-b>>1, y+(a>>1), g) if x&1 else (x>>1, y, g)
    elif not b&1:
        # a - нечётное, b - чётное
        x, y, g = ext_gcd(a, b>>1)
        return (x+(b>>1), y-a>>1, g) if y&1 else (x, y>>1, g)
    elif b > a:
        # оба нечётные
        x, y, g = ext_gcd(a, b-a)
        return x-y, y, g
    else:
        # оба нечётные
        x, y, g = ext_gcd(a-b, b)
        return x, y-x, g
 
a,b = 36,54
x,y,g=ext_gcd(a,b)
print(f"({x})*{a} + ({y})*{b} = {g}") # (-13)*36 + (9)*54 = 18

итеративный алгоритм с некоторыми оптимизациями

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def pwr(c, p, q, a, b): return \
    (c>>1, p+b>>1, q-a>>1) if p&1 | q&1 else \
    (c>>1, p>>1, q>>1)
 
def ext_gcd(a, b):
    u,v,s,t,r = 1,0,0,1,0
    while not a&1 | b&1: a, b, r = a>>1, b>>1, r+1
    ha,hb = a,b
    while not a&1: a,u,v = pwr(a,u,v,ha,hb)
    while a != b: u,v,a,b,s,t = \
        (u,v,a,*pwr(b,s,t,ha,hb)) if not b&1 else \
        (s,t,b,a,u,v)             if b<a     else \
        (u,v,a,b-a,s-u,t-v)
    return s,t,2**r*a
 
a,b = 36,54
x,y,g=ext_gcd(a,b)
print(f"({x})*{a} + ({y})*{b} = {g}") # (-7)*36 + (5)*54 = 18

@cypher111 · 12.09.2022, 09:28 **[ТС]**

Вот оно, оказывается, как глубоко уходит в теории. Большое спасибо, буду разбираться

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@cypher111 0 / 0 / 1 Регистрация: 29.03.2022 Сообщений: 18
	12.09.2022, 09:28 [ТС]
	Вот оно, оказывается, как глубоко уходит в теории. Большое спасибо, буду разбираться 0

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

Решение