Revision history [back]

I want to implement the euclidean algorithm for arbitrary euclidean domains.

In particular, I want it to work with Gaussians.

# Extended Euclides Algorithm
def extended_euclides(a,b):
    r0 = a; r1 = b
    s0 = 1; s1 = 0
    t0 = 0; t1 = 1

    while r1 != 0:
        q = r0 // r1
        r0, r1 = r1, r0 - q * r1
        s0, s1 = s1, s0 - q * s1
        t0, t1 = t1, t0 - q * t1

    return r0, s0, t0

When I run

# Gaussian integers example
a = ZI(-87 + 47*I); b = ZI(-90 + 43*I)
r,s,t = extended_euclides(a,b)
print("The GCD of {} and {} is {}".format(a,b,r))
print("Its Bézout coefficients are {} and {}".format(s,t))
assert(r == s*a + t*b)

I get the output

The GCD of 47*I - 87 and 43*I - 90 is 43*I - 90
Its Bézout coefficients are 0 and 1

Which is wrong. My understading of what is happening is that the quotient // is not giving me the integer quotient, but promoting it to rational quotient.

How do I compute the gaussian integer quotient?

I want to implement the euclidean algorithm for arbitrary euclidean domains.

In particular, I want it to work with Gaussians.

# Extended Euclides Algorithm
def extended_euclides(a,b):
    r0 = a; r1 = b
    s0 = 1; s1 = 0
    t0 = 0; t1 = 1

    while r1 != 0:
        q = r0 // r1
        r0, r1 = r1, r0 - q * r1
        s0, s1 = s1, s0 - q * s1
        t0, t1 = t1, t0 - q * t1

    return r0, s0, t0

When I run

# Gaussian integers example
ZI = QuadraticField(-1, 'I').ring_of_integers()
a = ZI(-87 + 47*I); b = ZI(-90 + 43*I)
r,s,t = extended_euclides(a,b)
print("The GCD of {} and {} is {}".format(a,b,r))
print("Its Bézout coefficients are {} and {}".format(s,t))
assert(r == s*a + t*b)

I get the output

The GCD of 47*I - 87 and 43*I - 90 is 43*I - 90
Its Bézout coefficients are 0 and 1

Which is wrong. My understading of what is happening is that the quotient // is not giving me the integer quotient, but promoting it to rational quotient.

How do I compute the gaussian integer quotient?