# Making a quotient with Gaussian elements

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?

edit retag close merge delete

Could you please provide the code that defines ZI ?

( 2018-11-12 09:16:43 -0500 )edit

@tmonteil I have edited the question to include that information

( 2018-11-12 09:26:44 -0500 )edit

Sort by » oldest newest most voted

There is indeed an issue since the _floordiv_ method of the elements thinks that ZI is a field, see:

sage: a._floordiv_?
Docstring:
Return the quotient of self and other. Since these are field
elements, the floor division is exactly the same as usual division.


That said, you can write the integer division yourself: just replace

q = r0 // r1


with

q = ZI(real(r0/r1).round() + I*imag(r0/r1).round())


and you will get:

The GCD of 47*I - 87 and 43*I - 90 is 1
Its Bézout coefficients are -8*I - 39 and 6*I + 39


EDIT Regarding the comments, you can add the quotient function as the parameter of your function, which defaults to the // function as follows:

# Extended Euclides Algorithm
def extended_euclides(a,b,quo=lambda a,b:a//b):
r0 = a; r1 = b
s0 = 1; s1 = 0
t0 = 0; t1 = 1
while r1 != 0:
q = quo(r0,r1)
r0, r1 = r1, r0 - q * r1
s0, s1 = s1, s0 - q * s1
t0, t1 = t1, t0 - q * t1
return r0, s0, t0


So that you can do:

sage: extended_euclides(7,2)
(1, 1, -3)


but also

sage: ZI = QuadraticField(-1, 'I').ring_of_integers()
....: a = ZI(-87 + 47*I); b = ZI(-90 + 43*I)

sage: extended_euclides(a,b,quo=lambda a,b: ZI(real(a/b).round() + I*imag(a/b).round()))
(1, -8*I - 39, 6*I + 39)

more

The problem with that approach is that I need my solution to be general (ie work also with normal integers and other euclidean domains), so I cant directly reference ZI in the code. Any alternatives?

( 2018-11-12 11:19:19 -0500 )edit

Also I would accept as a solution something along the lines of "use this other definition of the gaussian integers"

( 2018-11-12 11:20:47 -0500 )edit
1

One reason that Euclidean division isn't available by default on ZI is because as far as sage is concerned, it's a quadratic ring, and those generally are not euclidean rings. There are some quadratic rings that are, but most of them are only euclidean with rather obscure euclidean norms. The fact that Z[i] is euclidean with the "standard" norm is really quite anomalous among quadratic rings.

If you're interested in studying euclidean rings you probably should write some utility functions yourself to help you with it (or search if such utilities are already available). You could even consider writing a new ring subclass for Euclidean rings. To illustrate that sage doesn't know that ZI is a euclidean domain:

sage: ZI in EuclideanDomains()
False

( 2018-11-12 14:49:38 -0500 )edit