Steve Witham writes:
GCD of Gaussian integers looks slightly trickier than the ordinary version. My brain says "I don't want to learn a whole new skill!" and I have to tell it, "You put your shoes on, stop hiding in your comfort zone, go outside and have some math-fun young man."
As I mentioned in my earlier mail, the Euclidean algorithm works perfectly well with Gaussian integers, provided you have the proper remainder function. Here's the core of the Python code for my Gaussian GCD method: while v2 != 0: v1, v2 = v2, v1.irem(v2) This is followed by a step that forces the result into a canonical form by multiplying by the proper unit, but that part is trivial. The irem method just returns: v1 - v2 * v1.idiv(v2) The idiv method is only slightly trickier. It divides v1 by v2 to obtain a Gaussian rational, then for both the real and imaginary rationals, it does an integer divide of the numerator by the denominator to obtain integer real and imaginary parts. Different results can be obtained depending on how the integer divide is done (i.e., how the result is rounded). For my version, I used floor(v + 1/2). This minimizes the norm of the difference between the Gaussian rational result and the Gaussian integer result. Specifically, if the (exact) Gaussian rational result is x + i*y, and the (rounded) Gaussian integer result is m * i*n, then this guarantees that: -1/2 <= x - m < 1/2 -1/2 <= y - n < 1/2 which is achieved with: m = floor(x + 1/2) n = floor(y + 1/2) Tom