First time here? Check out the FAQ!

Ask Your Question
1

Making a quotient with Gaussian elements

asked 6 years ago

Jsevillamol gravatar image

updated 6 years ago

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?

Preview: (hide)

Comments

Could you please provide the code that defines ZI ?

tmonteil gravatar imagetmonteil ( 6 years ago )

@tmonteil I have edited the question to include that information

Jsevillamol gravatar imageJsevillamol ( 6 years ago )

1 Answer

Sort by » oldest newest most voted
1

answered 6 years ago

tmonteil gravatar image

updated 6 years ago

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)
Preview: (hide)
link

Comments

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?

Jsevillamol gravatar imageJsevillamol ( 6 years ago )

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

Jsevillamol gravatar imageJsevillamol ( 6 years ago )
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
nbruin gravatar imagenbruin ( 6 years ago )

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 6 years ago

Seen: 830 times

Last updated: Nov 12 '18