Ask Your Question
1

Making a quotient with Gaussian elements

asked 2018-11-12 15:04:31 +0200

Jsevillamol gravatar image

updated 2018-11-12 16:26:11 +0200

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?

edit retag flag offensive close merge delete

Comments

Could you please provide the code that defines ZI ?

tmonteil gravatar imagetmonteil ( 2018-11-12 16:16:43 +0200 )edit

@tmonteil I have edited the question to include that information

Jsevillamol gravatar imageJsevillamol ( 2018-11-12 16:26:44 +0200 )edit

1 Answer

Sort by » oldest newest most voted
1

answered 2018-11-12 17:48:10 +0200

tmonteil gravatar image

updated 2018-11-12 19:28:50 +0200

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)
edit flag offensive delete link more

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 ( 2018-11-12 18:19:19 +0200 )edit

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

Jsevillamol gravatar imageJsevillamol ( 2018-11-12 18:20:47 +0200 )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
nbruin gravatar imagenbruin ( 2018-11-12 21:49:38 +0200 )edit

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: 2018-11-12 15:04:31 +0200

Seen: 662 times

Last updated: Nov 12 '18