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

Question

[blecked88]

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

накидал вот такой код на питоне:

def extended_euclidean_truncated(a, b):
    i = 0
    r_prev, r_cur = max(a,b), min(a,b)
    x_prev, y_prev, x_cur, y_cur = 1, 0, 0, 1
    print(f"i = {i} r = {r_prev} x = {x_prev} y = {y_prev}, q = -")

    while r_cur != 0:
        i += 1

        # Модификация
        if r_cur > (r_prev >> 1):
            r_cur = r_prev - r_cur
        #############

        q = r_prev // r_cur
        r = r_prev % r_cur

        print(f'i = {i}, r = {r_cur}, x = {x_cur}, y = {y_cur}, q = {q}')
        r_cur, r_prev = r, r_cur
        x_cur, x_prev = x_prev - q*x_cur, x_cur
        y_cur, y_prev = y_prev - q*y_cur, y_cur

    # gcd = a*x+b*y, где x - это x_prev, y - это y_prev
    return max(a,b), x_prev, min(a,b), y_prev, r_prev

a, b, c, d, e = extended_euclidean_truncated(26, 49)
print(f"LINEAR REPRESENTATION: ({a})*({b})+({c})*({d})=({e})")

GCD считает правильно, но x, y - нет. Почему так? Никак не могу встроить эту модификацию таким образом, чтобы x,y тоже правильно считались.
Если убрать модификацию, то получится обычный РАЕ, работающий как надо.

Answer 1

[Wataru]

Идея этого усечения в том, что если вы ищите gcd(a, b), то можно также искать gcd(a,a-b). Вот эта замена b' = a-b у вас в коде и происходит.

Вы там поддерживаете инвариант x_i*a+y_i*b = r_i

Сответсвтенно, вам надо пересчитать x_cur и у_cur вместе с изменением r_cur.

У вас есть x_prev*a+y_prev*b = r_prev и x_cur*a+y_cur*b = r_cur. Вам надо составить линейную комбинацию r_prev - r_cur. Ну вычтите одно уравнение из другого и все.

Соответственно вам надо сделать вот это при применении вашего усечения:

x_cur = x_prev - x_cur
y_cur = y_prev - y_cur

Comments

[blecked88]

спасибо!