## Gaussian Integers, Part 1

### November 4, 2014

Gaussian integers are complex numbers of the form *a* + *b i* where both *a* and *b* are integers. They obey the normal laws of algebra for addition, subtraction and multiplication. Division works, too, but is a little bit complicated:

Addition: (*a* + *b i*) + (*x* + *y i*) = (*a* + *x*) + (*b* + *y*) *i*.

Subtraction: add the negative: (*a* + *b i*) − (*x* + *y i*) = (*a* − *x*) + (*b* − *y*) *i*.

Multiplication: cross-multiply, with *i* ^{2} = −1: (*a* + * b i*) × (*x* + *y i*) = (*a x* − *b y*) + (*a y* + *b x*) *i*.

Quotient: multiply by the conjugate of the divisor, then round: (*a* + *b i*) ÷ (*x* + *y i*) = ⌊(*a x* + *b y*) / *n*⌉ + ⌊(*b x* − *a y*) / *n*⌉ *i*, where *n* = *x* ^{2} + *y* ^{2}.

Remainder: compute the quotient, then subtract quotient times divisor from dividend.

Your task is to write a small library of functions for operating on Gaussian integers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Haskell: http://codepad.org/1VZIecvt

Question1: is the quotient not like this (ax+by) +(ay-bx)i ?

Question2: is it ok to use floor instead of round?

Then in Scala:

class GaussianInteger(val a: Int, val b: Int) {

def addition(that: GaussianInteger): GaussianInteger = new GaussianInteger(a + that.a, b + that.b)

def subtraction(that: GaussianInteger): GaussianInteger = new GaussianInteger(a – that.a, b – that.b)

def crossMultiply(that: GaussianInteger): GaussianInteger = new GaussianInteger(a * that.a – b * that.b, a * that.b + b * that.a)

def quotient(that: GaussianInteger): GaussianInteger = {

val n = that.a * that.a + that.b * that.b

new GaussianInteger((a * that.a – b * that.b) / n, (b * that.a – a * that.b) / n)

}

def remainder(that: GaussianInteger): GaussianInteger = subtraction(quotient(that))

override def toString: String = a + ” + ” + b + “i”

}

The quotient is ((ax+by) + (bx-ay)i) / n; the code was right, I fixed the description. Using floor instead of round doesn’t work, because the norm of the result must be less than half the norm of the divisor, by convention; see the discussion of the Division Theorem in the paper linked from the solution page.

Using Scheme’s complex numbers, I get addition and multiplication for free. I find that Gambit-C does Gaussian rationals exactly, and for it the norm is automatically real. In Guile I had to take the real part explicitly. (I needed the norm to be real in order to test that the remainder is smaller than the divisor.)

(define (zi-conjugate a) (make-rectangular (real-part a) (- (imag-part a))))

(define (zi-norm a) (real-part (* a (zi-conjugate a)))) ;imag-part is zero

(define (zi-quotient a b)

(let ((q (/ (* a (zi-conjugate b)) (zi-norm b))))

(make-rectangular (round (real-part q)) (round (imag-part q)))))

`(define (zi-remainder a b) (- a (* b (zi-quotient a b))))`

Printing the quotient and remainder from the paper:

(write (cons (zi-quotient 27-23i 8+i) (zi-remainder 27-23i 8+i))) (newline)

The Gambit-C interpreter (gsi) prints this, where the absence of decimal points indicates that the components are exact integers (with a zero real component omitted):

(3-3i . -2i)

Guile prints this, where the presence of the decimal points indicates that the computation may have used inexact methods (floating point, I’m sure):

(3.0-3.0i . 0.0-2.0i)

Floating point might fail (rounding, overflowing), but my limited tests, with all components small, were fine even in Guile.