A Few C++ Templates for Basic Operations in Euclidean Domains:
Definition: A commutative ring R with 1 is called a Euclidean domain if
(0.) for r, s in R, if r*s=0, then r=0 or s=0;
and there is a degree function abs : R except {0} ---->{0,1,2,...} such that:
(1.) for non-zero r, s in R, abs(r) < or = abs(r*s) , and
(2.) if n, p are in R with p non-zero, then there are q, r in R such that n=p*q+r where either
r=0 ( p|n, p divides n ) or abs(r) < abs(p) (the remainder has smaller degree than the divisor).
We will write q=n/p and r=n%p. Elements r, s of R are said to be associates if both r|s and s|r.
( C.f. any good algebra textbook, e.g. T.W.Hungerford, Algebra.)
Examples abound. Two familiar examples are:
(1.) Ordinary integers: abs(n) is the ordinary absolute value of n.
(2.) Polynomials in x with (say) Rational, Real or Complex coefficients: abs(f(x))=degree of f(x).
What follows is not part of a big software package, but merely intended to be a convenient generic interface to any Euclidean datatypes you may have on hand. In all of the files listed, preference has been given to generality and notational convenience over speed, but then, you can always write a template specialization to handle a particular ring. I have assumed that your ring class defines +, -, *, /, %, and the corresponding assignment operators, as well as iostream operators. I like to overload the [ ] -operator to mean "integer power" for ring objects. It has the right order of precedence, and I believe that reading "subscript" as "superscript" requires only a small mental adjustment. Powers are computed by the "Russian peasent method". The functions that follow return 0 without complaint when division fails unless otherwise indicated, so it is your responsibility to avoid division by 0.
You will find a few templated C++ functions for basic operations in Euclidean domains here: Euclid.h
A word about the unfortunately named function Inverse(Euclidean& u, const Euclidean& Chi). This rarely returns this actual inverse of u (mod Chi). For any u, Chi in a Euclidean domain, there is an element v such that u*v=G.C.D.{u,Chi} (mod Chi). Inverse returns this v and puts the G.C.D. in u. Even if u happens to be invertable (mod Chi), v is only guaranteed to be an associate of the inverse of u. Invert(u,Chi) returns true and replaces u with the actual inverse of u if u is invertable (mod Chi). Otherwise, u is assigned the aforementioned v and Invert returns false .
Note: "Mod-ing-out by zero" is not an error with these functions, but is defined to have no effect.
Also note: G.C.D.{0,n} = n = G.C.D.{n,0} .
A Gaussian integer is a complex number with integral real and imaginary parts. The Gaussian integers are a Euclidean domain where abs(z) is the square of the ordinary complex absolute value of z. You will find a templated Gaussian integer class which takes an integer type parameter here: Gaussian.h
The class parameter should be some type that represents ordinary integers. In particular < and abs should make sense. They are very easy to use. For example:
Gaussian<int> x (4,-7); // x:=4-7i .
Gaussian<int> y=3; // y:=3 .
x*=y; // Now, x=12-21i .
cout<<x<<"\n"; // Prints "12-21i" .
Gaussian<int> z=Ldivide(x,y); // z:=4-7i, x:=0 (the remainder), y remains 3 .
cout<<abs(z)<<"\n"; // Prints "65" .
Im(y)=6; // Now, y=3+6i .
Every Euclidean domain is a Principal ideal domain (PID), meaning that every ideal is generated by a single element. So each of its quotient rings can be described by a single element; i.e. they all look "cyclic". You will find a templated class to implement quotients of Euclidean domains here: Cyclic.h
For this class, the operator / is "honest-to-goodness division", i.e. (x/y)*y=x when x/y exists, otherwise 0 is returned without complaint. You can use the operator | to test for divisibility: y|x returns true when y divides x, false otherwise. You can use the member function Inv to test for invertability. For instance, y.Inv(z) puts the inverse of y in z and returns true when y is invertable, otherwise it returns false and puts its best attempt at inverting y in z. y remains unchanged.
The constructor Cyclic takes two template parameters: a type parameter PID, which should be a Euclidean domain, and an optional integer index to distinguish Cyclic types with the same PID.
Note: The ideal is initialized to {0} at compile-time, and PID/{0} is isomorphic to PID. The static member function SetZero can be used to change the generator of the ideal at run-time. For example:
#include "Cyclic.h"
int main( )
{ // ...
Cyclic<int,1> x=5;
Cyclic<int,2> y=6;
Cyclic<int,1>::SetZero(18);
int z;
cin>>z, Cyclic<int,2>::SetZero(z);
cout<<x[-2]<<" (mod "<<Cyclic<int,1>::Zero( )<<")\n"; // Prints "13 (mod 18)" .
// ...
return 0; }
"Cyclic.h" uses the templated functions defined in "Euclid.h".
It is always possible to form the field of fractions of a Euclidean domain; e.g. the rationals from the integers. (C.f. any good algebra textbook.) You will find class which takes a single Euclidean domain template parameter, PID, and implements the field of fractions of PID here: Fraction.h
Note: Division by 0 is not necessarily an error in Fraction<PID>. You may think of "1/0" as "infinity" if you like. "0/0" does cause problems, however, so avoid producing it.
"Fraction.h" uses the templated functions defined in "Euclid.h".
Send any comments, questions, suggestions, criticisms, improvements, additions and especially algorithms, template specializations and Euclidean domains to:
tothmichael@provide.net