Найти наибольший общий делитель (GCD) в гауссовых целых числах с SymPy

Question

Я пытаюсь найти GCD из двух гауссовых целых чисел, используя Sympy, но не могу получить правильный результат.Например, функция

gcd(2+I,5, gaussian = True)

должна возвращать 2+I (I - мнимая единица), поскольку (2+I)*(2-I)=5 в гауссовых целых числах.Однако он возвращает 1.

Answer 1

Похоже, gcd недостаточно осведомлен о гауссовых целых числах (т. Е. Об ошибке).Вы можете использовать свою собственную функцию, основанную на евклидовом алгоритме.

from sympy import sympify, I, expand_mul
def my_gcd(a, b):
    a, b = map(sympify, (a, b))
    if abs(a) < abs(b):
        a, b = b, a
    cr, ci = (a/b).as_real_imag()
    if cr.is_integer and ci.is_integer:
        return -b if b.could_extract_minus_sign() else b
    c = int(round(cr)) + I*int(round(ci))
    return my_gcd(a - expand_mul(b*c), b)

Тестирование:

my_gcd(30, 18)   #  6
my_gcd(5, 2+I)   #  2+I
my_gcd(30, 18+4*I)   # 4 + 2*I

Проверка последнего из них: 30 = (4+2*I)*(6-3*I) и 18+4*I = (4+2*I)*(4-I).