Re: euclidean algorithm over Q[i]

Jeremy Watts wrote:
"Chip Eastham" <hardmath@xxxxxxxxx> wrote in message
news:1166276481.508680.8020@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Jeremy Watts wrote:
"Chip Eastham" <hardmath@xxxxxxxxx> wrote in message
news:1166245043.467094.262880@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

G. A. Edgar wrote:
In article <62tgh.6569$Dr3.1078@xxxxxxxxxxxxxxxxxxxx>, Jeremy Watts
<stevie4545@xxxxxxxxxxx> wrote:

how does the euclidean algorithm proceed for numbers in Q[i] ? my
knowledge
of abstract algebra's basic to say the least so i hope i am using
the
correct term. i mean for complex numbers with rational real &
complex
parts
ie. of form a/b + c/d i a,b,c,d in Z

i'm sure i have seen this somewhere but cant find reference to it
anywhere.

thanks



Q[i] is a field, so greatest common divisors are easy.
Any nonzero element divides any other nonzero element.

Z[i], the Gaussian integers, may be what you remember seeing.

--
G. A. Edgar
http://www.math.ohio-state.edu/~edgar/

And if the OP is interested in the Gaussian integers Z[i],
it is helpful to bear in mind that a Euclidean domain is
possessed of a norm. The "remainder" term is to have
norm less than the divisor in each application of the
division algorithm. Of course Z[i] is not an ordered ring,
so its important to pick the remainder to have minimum
norm as its defining characteristic.

The norm of z = a + bi is a^2 + b^2 in Z[i].

More discussion here:

yes of course, thank you both. the reason i'm asking this is because
i've
written a pretty simplistic algorithm in java that carries out
polynomial
GCD, just using polynomial long division and the euclidean algorithm.

i've been comparing the output with what 'wims' gives

http://wims.unice.fr/wims/wims.cgi?session=XKF67EF2A7.1&+lang=en&+module=too
l%2Farithmetic%2Fbezout.en

and they agree, apart from the final value for the gcd. which i assume
'wims' is getting somehow by avoiding intermediate 'coefficient swell'.
i
have read that if you use 'pseudo division' rather than standard long
division you can get around this problem when working in the rationals

Are you using the Euclidean algorithm to compute
GCD's of univariate polynomials over Q[i]?

Hi Chip, yes i am using the Euclidean algorithm to compute gcd's of
univariate polynomials over Z,Z[i] and Q[i]

The statement that "they agree, apart from the final
value for the gcd" is a bit unsettling! I would assume
normalization to monic polynomials resolves any
ambiguity, and you are asking if there is strategic
advantage to using 'pseudo division' to avoid large
sized intermediate results.

when you say 'normalization to a monic' what do you mean by that? sorry if
that sounds a bit basic. is this what 'pseudo division' does?

When I say "normalization to a monic", I meant that
you should compare the two results (yours and the
one obtained by the wims software) by dividing each
through by their leading coefficients. The answers
should then agree. Since the coefficients are in Q(i),
a field, and the leading coefficient is nonzero, this is
always possible.

I'm not sure what 'pseudo division' may mean, as
there are various alternative algorithms to using as
the Euclidean algorithm does repeated steps of a
"division algorithm" in which the quotient and some
remainder "smaller" than the divisor are extracted.

Working over Z[i] rather than Q(i), and using least
common multiples of leading coefficients (with
subtraction to reduce degree) seems like a good
strategy for minimizing coefficient sizes, and it
could reasonably be called 'pseudo division'.

However note the article I referred you to on
"heuristic GCD", which claims that this very
different approach is widely adopted by CAS
packages.

regards, chip

.