support for Gaussian integers

[velnias75]

By Melchoir via Reddit

A Gaussian integer is a complex number where the real and imaginary parts are both integers. In other words, a thing of the form a+bi where a and b are integers. I think it can even be implemented as std::complex. Some salient points are:

• The Euclidean algorithm works on Gaussian integers.
• There is a modulus operator and a norm function.
• There is no natural ordering! If one implements a Gaussian integer class in C++, one might define somewhat arbitrary operators <, >, etc. so that standard sorting-based algorithms work, but those operators shouldn't be used to implement the Euclidean algorithm. A ratio of two Gaussian integers is called a Gaussian rational. It has the form (a+bi)/(c+di). Mathematically, this is the same as ((a+bi)(c-di))(c2+d2), so you can also think of a Gaussian rational as a ratio of a Gaussian integer over an ordinary integer. For example, (1+0i)/(1+1i) is equal to (1-1i)/2. In that sense, it only takes three integers to specify a Gaussian rational. It might seem wasteful to use four integers. However, it will frequently happen that some (a+bi)/(c+di) is representable using a given storage type, while ((a+bi)(c-di))(c2+d2) overflows in the numerator and/or the denominator.

Gaussian integers and Gaussian rationals are both interesting types. It would be nice if one could define a Gaussian integer type and, with a little extra effort, get the rational type by applying your template to it. In the terminology of pure mathematics, your template implements a field of fractions, which is meaningful for any integral domain, including the ordinary integers.

I understand the point about designing the template for completeness. My point is that as a potential user of the library, I would be worried that, for example, the implementation of Rational::operator+= secretly performs some normalization that depends on the existence of T::operator<. This information is impossible to get just from reading the code, and I would dread having to test it out myself, only to pull my hair out deciphering the compiler's error messages. Even if it compiles, I would be worried that it makes some assumption about the behavior of the < operator that is violated by my storage type, and the compiler wouldn't even be able to detect that. This might very well be the case for the Gaussian integers, which I would count as an "exotic" storage type.

Eh... I would try adding support for Gaussian integers myself, but it feels like it might be a lot of work. :)

[velnias75]

Without an Gauss integer class I have simply to less knowlegde to even begin with work :-(

I tried to use std::complex, but I fail because except of the for basic arithmetic operators almost everything is missing.

Instantiation fails already because I have no GCD for it.

[velnias75]

Gaussian integers on Stackoverflow