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

@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 **[ТС]**

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

Новые блоги и статьи Все статьи Все блоги /
Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .

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

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

Решение