The file ring.H introduces several classes used for representing rings
and their elements. A normal user of the CoCoA library will use
mostly the classes ring
and RingElem
. An object of type
ring
represents a mathematical ring with unity, and objects of
type RingElem
represent values from some ring. While the CoCoA
library was conceived primarily for computing with commutative rings,
the possibility of having certain non-commutative rings exists.
A variable of type ring
is effectively constant: its value may not
be changed, and it cannot be assigned to. In contrast, a variable of
type RingElem
may change its value but only within the ring to
which it is associated: this ring is specified when the variable is
created. Here are a couple of code snippets to give an idea:
VALID CODE | INVALID CODE |
---|---|
ring R = RingZ(); |
ring R; // no! |
RingElem a(R), b(R); |
|
a = 2; |
RingElem a = 2; // no! |
b = a+7; |
RingElem(2); // no! |
if (a-b != -7) cout << "MISTAKE!\n"; |
There are fuller example programs in the examples/
directory.
The primary use for a variable of type ring
is simply to specify
the ring to which RingElem variables are associated. However, for some
computations the best algorithm to use may depend on certain properties
of the ring. Let R denote a variable of type ring
: here are the
properties you can ask about:
characteristic(R) |
returns the characteristic of R (as a ZZ ) |
IsCommutative(R) |
a boolean, true iff R is commutative |
IsIntegralDomain(R) |
a boolean, true iff R has no zero divisors |
IsGCDDomain(R) |
a boolean, true iff R is a GCD domain (NB all fields are GCD domains) |
IsOrderedDomain(R) |
a boolean, true iff R is arithmetically ordered |
IsField(R) |
a boolean, true iff R is a field |
symbols(R) |
a std::vector of the symbols in R (e.g. Q[x,y,z] contains the symbols x,y, and z) |
NOTE: a pragmatic approach is taken: e.g. IsGCDDomain
is true only if
GCDs can actually be computed using the CoCoA library. IsQuotientRing
is true only if R is internally implemented as a quotient ring
(e.g. Z/0Z is; Z is not). In general the function "IsXYZ" should be
read as "Is internally implemented as XYZ".
These query functions tell you how the ring is implemented:
IsZ(R) |
a boolean, true iff R is actually a ring of integers |
IsFractionField(R) |
a boolean, true iff R is actually a field of fractions |
IsPolyRing(R) |
a boolean, true iff R is actually a polynomial ring |
IsQuotientRing(R) |
a boolean, true iff R is actually a quotient ring |
NOTE: Warning: for example if R = Z[x]/ideal(x)
then
R
is obviously isomorphic to the ring of integers but
IsZ(R)
gives FALSE
, and
IsQuotientRing(R)
gives TRUE
.
You can get the zero and one of a ring directly using the following:
zero(R) |
the zero element of R |
one(R) |
the one element of R |
A variable of type RingElem
must be associated to a ring upon its
creation. Thereafter the ring to which it is associated cannot be
changed during the lifetime of the value, but the value inside the ring
can be changed. RingElem
s are designed to be easy and safe to use;
this incurs a certain run-time overhead, so a faster alternative is
offered (see below in section "Fast and Ugly Code").
See also some example programs in the directory "examples/" for how to
use RingElem
s.
assume R
is a ring
,
n
a machine integer, and
N
a (big) integer of type ZZ
RingElem r1(R); |
an element of R, initially zero |
RingElem r2(R, n); |
an element of R, initially the image of n |
RingElem r3(R, N); |
an element of R, initially the image of N |
RingElem r4(r1); |
a copy of r1, element of the same ring |
RingElem r4 = r1; |
(alternative syntax, discouraged) |
zero(R) |
the zero element of R |
one(R) |
the one element of R |
Let r1
be a (possibly const) RingElem
, and
let N
be a variable of type ZZ
owner(r1) |
the ring to which r1 is associated |
IsZero(r1) |
true iff r1 is zero |
IsOne(r1) |
true iff r1 is one |
IsMinusOne(r1) |
true iff -r1 is one |
IsInteger(N, r1) |
true iff r1 is the image of an integer (if true, a preimage is placed in N) |
IsRational(N, D, r1) |
true iff r1 is the image of a rational (if true, N/D becomes a preimage) |
IsUnit(r1) |
true iff r1 has a multiplicative inverse |
IsDivisible(r1, r2) |
true iff r1 is divisible by r2 |
raw(r1) |
(see below, section "Fast and Ugly Code") |
R->myIsPrintAtom(r1) |
true iff r1 does not need brackets when a numer or denom of a fraction |
R->myIsPrintedWithMinus(r1) |
true iff the printed form of r1 begins with a minus sign |
Let r
be a non-const RingElem
,
and r1
, r2
be potentially const RingElem
s.
Assume they are all associated to the same ring.
Then the operations available are: (meanings are obvious)
cout << r1 |
output value of r1 (decimal only, see notes) |
r1 == r2 |
equality test |
r1 != r2 |
not-equal test |
r = r1 |
assignment |
-r1 |
negation (unary minus) |
r1 + r2 |
sum |
r1 - r2 |
difference |
r1 * r2 |
product |
r1 / r2 |
quotient, division must be exact (see IsDivisible) |
r += r1 |
equivalent to r = r + r1 |
r -= r1 |
equivalent to r = r - r1 |
r *= r1 |
equivalent to r = r * r1 |
r /= r1 |
equivalent to r = r / r1 |
gcd(r1, r2) |
an associate of the gcd (if ring is gcd domain, o/w error) |
power(r1, n) |
n -th power of r1 ; n may be long or ZZ |
If the ring is an ordered domain then these functions may also be used.
Here r1
and r2
must belong to an ordered ring.
sign(r1) |
value is -1, 0 or +1 according as r1 is negative, zero or positive |
abs(r1) |
absolute value of r1 |
floor(r1) |
greatest integer <= r1 |
ceil(r1) |
least integer >= r1 |
NearestInteger(r1) |
returns nearest integer (ZZ ) to r1 , halves round towards +infinity. |
cmp(r1, r2) |
returns a value <0, =0, >0 according as r1-r2 is <0, =0, >0. |
CmpDouble(r1, z) |
compare a ring elem with a double , result is <0, =0, >0 according as r1-z is <0, =0, >0 |
r1 < r2 |
standard inequalities |
r1 > r2 |
... |
r1 <= r2 |
... |
r1 >= r2 |
... |
Operations combining elements of different rings will cause a run-time error.
In all functions involving two RingElem
s either r1
or r2
may be replaced
by a machine integer, or by a big integer
(an element of the class ZZ
). The integer value is automatically mapped
into the ring owning the RingElem
in the same expression.
The exponent n
in the power function may be zero or negative, but a
run-time error will be signalled if one attempts to compute a negative
power of a non-invertible element or if one attempts to raise zero to
the power zero. NB You cannot use ^
to compute powers -- see Bugs section.
An attempt to perform an inexact division or to compute a GCD not in a GCD domain will produce a run-time error.
The printing of ring elements is always in decimal regardless of the
ostream
settings (this is supposed to be a feature rather than a bug).
At this point, if you are new to CoCoALib, you should probably look
at some of the example programs in the examples/
directory.
One would normally expect to use the type const RingElem&
for
read-only arguments which are RingElem
s, and RingElem&
for
read-write arguments. Unfortunately, doing so would lead to problems
with the CoCoA library. INSTEAD you should use the type
ConstRefRingElem
for read-only arguments, and the type
RefRingElem
for read-write arguments.
If you are curious to know why this non-standard quirk has to be used,
read on. Internally, ring element values are really smart pointers to
the true value. Now the const
keyword in C++ when applied to a
pointer makes the pointer const while the pointed-to value remains
alterable -- this is not the behaviour we want for const RingElem&
.
To get the desired behaviour we have to use another type: the type
we have called ConstRefRingElem
.
You might wonder why Ref
appears in the names RefRingElem
and
ConstRefRingElem
. It indicates that you are working with a reference
to a value which is owned by another object (e.g. a variable of type
RingElem
, or maybe a matrix
).
The rest of this section is for more advanced use of rings and
RingElem
s (e.g. by CoCoA library contributors). If you are new to
CoCoA, you need not read beyond here.
A convention of the CoCoA library is that the class RingBase
is to be
used as an abstract base class for all rings. You are strongly urged to
familiarize yourself with the maintainer documentation if you want to
understand how and why rings are implemented as they are in the CoCoA
library.
WE DO NOT RECOMMEND that you use what is described in this section. If you are curious to know a bit more how rings are implemented, you might find this section informative.
RingElem
s are designed to be easy and pleasant to use, but this
convenience has a price: a run-time performance penalty (and a memory
space penalty too).
Both penalities may be avoided by using raw values but at a
considerable loss of programming convenience and safety. You should
consider using raw values only if you are desperate for speed; even
so, performance gains may be only marginal except perhaps for
operations on elements of a simple ring (e.g. a small finite field).
A RingElem object contains within itself an indication of the owning ring, and a raw value which is a pointer to where the real representation of the ring element value lies. These raw values may be accessed via the raw function. They may be combined arithmetically by calling member functions of the owning ring. For instance, if x,y,z are all RingElem objects all BELONGING TO EXACTLY THE SAME RING then we can achieve
x = y+z;
slightly faster by calling
owner(x)->my.Add(raw(x), raw(y), raw(z));
It should now be clear that the syntax involved is cumbersome and
somewhat obscure. For the future maintainability of the code the
simpler x = y+z;
has many advantages. Furthermore, should x,y,z
somehow happen not all to lie in the same ring then x = y+z;
will act
in a reasonable way, whereas the supposedly faster call will likely lead
to many hours of debugging grief. The member functions for arithmetic
(e.g. myAdd
) DO NOT PERFORM sanity checks on their arguments:
e.g. attempting to divide by zero could well crash the program.
If you use a debugging version of the CoCoA Library then some member functions do use assertions to check their arguments. This is useful during development, but must not be relied upon since the checks are absent from the non-debugging version of the CoCoA Library. See the file config.txt for more information.
This fast, ugly, unsafe way of programming is made available for those who desperately need the speed. If you're not desperate, don't use it!
Read the section Fast and Ugly Code before using any of these!
Let r
be a non-const raw value, and r1
, r2
potentially
const raw values. Assume they are all owned by the ring R
.
Then the functions available are:
R->myNew() |
construct a new element of R, value=0 |
R->myNew(n) |
construct a new element of R, value=n |
R->myNew(N) |
construct a new element of R, value=N |
R->myNew(r1) |
construct a new element of R, value=r1 |
R->myDelete(r) |
destroy r, element of R (frees resources) |
R->mySwap(r, s) |
swaps the two values (s is non-const raw value) |
R->myAssignZero(r) |
r = 0 |
R->myAssign(r, r1) |
r = r1 |
R->myAssign(r, n) |
r = n (n is a long) |
R->myAssign(r, N) |
r = n (N is a ZZ ) |
R->myNegate(r, r1) |
r = -r1 |
R->myAdd(r, r1, r2) |
r = r1+r2 |
R->mySub(r, r1, r2) |
r = r1-r2 |
R->myMul(r, r1, r2) |
r = r1*r2 |
R->myDiv(r, r1, r2) |
r = r1/r2 (division must be exact) |
R->myIsDivisible(r, r1, r2) |
r = r1/r2, and returns true iff division was exact |
R->myIsUnit(r1) |
IsUnit(r1) |
R->myGcd(r, r1, r2) |
r = gcd(r1, r2) |
R->myPower(r, r1, n) |
r = power(r1, n) BUT n MUST be non-negative!! |
R->myIsZero(r1) |
r1 == 0 |
R->myIsZeroAddMul(r, r1, r2) |
((r += r1*r2) == 0) |
R->myIsEqual(r1, r2) |
r1 == r2 |
R->myOutput(out, r1) |
out << r1 |
R->mySequentialPower(r, r1, n) |
normally it is better to use R->myPower(r, r1, n) |
R->myBinaryPower(r, r1, n) |
normally it is better to use R->myPower(r, r1, n) |
(NB consider consulting also QuotientRing, FractionField and PolyRing)
The design underlying rings and their elements is more complex than I would have liked, but it is not as complex as the source code may make it appear. The guiding principles are that the implementation should be flexible and easy/pleasant to use while offering a good degree of safety; extreme speed of execution was not a goal (as it is usually contrary to good flexibility) though an interface offering slightly better run-time efficiency remains.
Regarding flexibility: in CoCoALib we want to handle polynomials whose
coefficients reside in (almost) any commutative ring. Furthermore, the
actual rings to be used will be decided at run-time, and cannot
restricted to a given finite set. We have chosen to use C++ inheritance
to achieve the implementation: the abstract class RingBase
defines the
interface that every concrete ring class must offer.
Regarding ease of use: since C++ allows the common arithmetic operators
to be overloaded, it is essential that these work as expected for
elements of arbitrary rings -- with the caveat that /
means exact
division, being the only reasonable interpretation. Due to problems of
ambiguity arithmetic between elements of different rings is forbidden:
e.g. let f in Q[x,y] and g in Z[y,x], where should f+g reside?
The classes in the file ring.H are closely interrelated, and there is no obvious starting point for describing them -- you may find that you need to read the following more than once to comprehend it. Here is a list of the classes:
ring |
value represents a ring; it is a smart pointer |
RingBase |
abstract class defining what a ring is |
RingElem |
value represents an element of a ring |
RefRingElem |
reference to a RingElem |
ConstRefRingElem |
const-reference to a RingElem |
RingElemConstRawPtr |
raw pointer to a const ring value |
RingElemRawPtr |
raw pointer to a ring value |
The class RingBase
is of interest primarily to those wanting to
implement new types of ring (see relevant section below); otherwise you
probably don't need to know about it. Note that RingBase
includes an
intrusive reference counter -- so every concrete ring instance will have
one. RingBase
also includes a machine integer field containing a
unique numerical ID -- this is so that distinct copies of otherwise
identical rings can be distinguished when output (e.g. in OpenMath).
The class ring
is used to represent mathematical rings (e.g. possible
values include Z, Q, or Q[x,y,z]). An object of type ring
is just a
reference counting smart pointer to a concrete ring implementation
object -- so copying a ring is fairly cheap. In particular two rings
are considered equal if and only if they refer to the same identical
concrete ring implementation object. In other files you will find
classes derived from ring
which represent special subclasses of rings,
for instance PolyRing
is used to represent polynomial rings. The
intrusive reference count, which must be present in every concrete ring
implementation object, is defined as a data member of RingBase
.
The classes RingElem
, RefRingElem
and ConstRefRingElem
are related
by inheritance: they are very similar but differ in important ways. The
three classes are used for representing values in rings (e.g 1 as an
element Z, or 1 as an element of Q[x], etc). In each case an object of
that C++ type comprises two components: one is the identity of ring to
which the element belongs, and the other is the value in that ring (the
value is stored in a format that only the owning ring can comprehend).
All operations on ring elements are effected by member functions of the
ring to which the value belongs.
The difference between ConstRefRingElem
and RefRingElem
is quite
simple: you cannot change the value of a ConstRefRingElem
, for
instance you cannot assign to it, while you are free to change the value
of a RefRingElem
.
The difference between a RefRingElem
and a RingElem
is also quite
simple, but possibly harder to grasp. A variable of type RingElem
is
the owner of the value that it represents: that value will be destroyed
when the variable passes out of scope. In contrast, a variable of type
RefRingElem
is not the owner; it merely refers to value belonging to
some other structure (e.g. a RingElem
, or a matrix, or a polynomial).
So you can create a RingElem
from nothing, whereas you must already
have a ring element to be able to create a RefRingElem
which refers to
it.
Why bother to distinguish between RingElem
and RefRingElem
? The
main reason was to allow matrices and iterators of polynomials to be
implemented cleanly and efficiently. Clearly a matrix
should be the
owner of the values appearing as its entries, but we also want a way of
reading the matrix entries without having to copy them. Furthermore,
the matrix can use a compact representation: the ring to which its
elements belong is stored just once, and not once for each element.
The reason that ConstRefRingElem
and RefRingElem
are distinct
classes is that neither const RefRingElem&
nor const RingElem&
achieves what one might reasonably expect. Since a RingElem
is
effectively a pointer to the value represented, applying a C++ const
keyword merely makes the pointer const while leaving the pointed-to
value modifiable. Consider the following procedure
void CannotChange(const RefRingElem& x) { RefRingElem writable(x); // writable reference to value of x writable = writable+1; }
The above procedure will add one to the value of its argument even though it would seem that it should not be alter the value.
The inheritance structure between ConstRefRingElem
, RefRingElem
and
RingElem
implements the similarities and differences between these
classes while also allowing ConstRefRingElem
and RefRingElem
to be
used as types of parameters to functions and procedures. Given that
matrix entry accessors return a ConstRefRingElem
it is important not
to use RingElem&
or const RingElem&
as the parameter type because
compilation would fail if a matrix entry were passed as parameter.
As already hinted above, the internal data layouts for objects of types
RingElem
, RefRingElem
and ConstRefRingElem
are identical -- this
is guaranteed by the C++ inheritance mechanism. The subfield indicating
the ring to which the value belongs is simply a const ring
, which is just a
reference counting smart pointer. The subfield indicating the value is
a raw pointer of type void* const
; however, when the raw pointer value
is to be handled outside a ring element object then it is wrapped up as
a RingElemRawPtr
or RingElemConstRawPtr
-- these are simply wrapped
copies of the void*
. Make a careful note of the exact type of the
data member myValuePtr
: the pointer is constant while the pointed to
value is not constant. The constness of the pointer is ABSOLUTELY
CRUCIAL to the correct behaviour of RefRingElem
. The fact that the
pointed-to value is not const may seem contradictory (for an object of
type ConstRefRingElem
), but it allows slightly easier implementation
of the non-constant derived classes RefRingElem
and RingElem
; the
friend raw
function puts in the necessary constness when it is called.
The classes RingElemRawPtr
and RingElemConstRawPtr
are used for two
reasons. One is that if a naked void*
were used outside the ring
element objects then C++ would find the call RingElem(R, 0)
ambiguous
because the constant 0
can be interpreted either as an integer
constant or as a null pointer: there are two constructors which match
the call equally well. The other reason is that it discourages
accidentally creating a ring element object from any old pointer; it
makes the programmer think -- plus I feel uneasy when there are naked
void*
pointers around. Note that the type of the data member myPtr
is simply void*
as opposed to void const*
which one might reasonably
expect. I implemented it this way as it is simpler to add in the missing
constness in the member function RingElemConstRawPtr::myRawPtr
than it
would be to cast it away in the myRawPtr
function of RingElemRawPtr
.
In ConstRefRingElem
why did I chose to make the data member
myValuePtr
of type void* const
rather than ``RingElemRawPtr
const``?
Recall that ring
is essentially a smart pointer to a RingBase
object, i.e. concrete implementation of a ring. Access to the
implementation is given via operator->
. If necessary, the pointer may
also be read using the member function myRingPtr
: this is helpful for
defining functions such as IsPolyRing
where access to the pointer is
required but operator->
cannot be used.
The class RingBase
declares a number of pure virtual functions for
computing with ring elements. Since these functions are pure they must
all be fully defined in any instantiable ring class (e.g. RingZImpl or
RingFpImpl). These member functions follow certain conventions:
void*
pointing to the actual value). A read-only
arg is of type RingElemConstRawPtr
, while a writable arg is of type
RingElemRawPtr
. When there are writable args they normally appear
first. For brevity there are typedefs ConstRawPtr
and RawPtr
in
the scope of RingBase
or any derived class.
In a few cases there are non-pure virtual member functions in
RingBase
. They exist either because there is a simple universal
definition or merely to avoid having to define inappropriate member
functions (e.g. gcd functions when the ring cannot be a gcd domain).
Here is a list of them:
IamGCDDomain() |
defaults to true |
IamOrderedDomain |
defaults to false |
myIsUnit(x) |
by default checks that 1 is divisible by x |
myGcd(lhs, x, y) |
gives an error: either NotGcdDom or NYI |
myGcdQuot(lhs, xquot, yquot, x, y) |
gives an error: either NotGcdDom or NYI |
myExgcd(lhs, xcofac, ycofac, x, y) |
gives an error: either NotGcdDom or NYI |
myIsPrintAtom(x) |
defaults to false |
myIsPrintedWithMinus(x) |
gives a SERIOUS error |
myIsMinusOne(x) |
defaults to myIsOne(-x); calculates -x |
myIsZeroAddMul(lhs, y, z) |
computes lhs += y*z in the obvious way, and calls myIsZero |
myCmp(x, y) |
gives NotOrdDom error |
mySign(x) |
simply calls myCmp(x, 0), then returns -1,0,1 accordingly |
There are three non-virtual member functions for calculating powers: one uses the sequential method, the other two implement the repeated squaring method (one is an entry point, the other an implementation detail). These are non-virtual since they do not need to be redefined; they are universal for all rings.
For the moment I shall assume that the intended meaning of the pure virtual functions is obvious (given the comments in the source code).
Recall that arithmetic operations on objects of type RingElem
,
RefRingElem
and ConstRefRingElem
are converted into member function
calls of the corresponding owning ring. Here is the source code for
addition of ring elements -- it typifies the implementation of
operations on ring elements.
RingElem operator+(ConstRefRingElem x, ConstRefRingElem y) { const ring& Rx = owner(x); const ring& Ry = owner(y); if (Rx != Ry) error(CoCoAError(ERR::MixedRings, "RingElem + RingElem")); RingElem ans(Rx); Rx->myAdd(raw(ans), raw(x), raw(y)); return ans; }
The arguments are of type ConstRefRingElem
since they are read-only,
and the return type is RingElem
since it is new self-owning value
(it does not refer to a value belinging to some other structure].
Inside the function we check that the rings of the arguments are
compatible, and report an error if they are not. Otherwise a temporary
local variable is created for the answer, and the actual computation is
effected via a member function call to the ring in which the values
lie. Note the use of the raw
function for accessing the raw pointer
of a ring element. In summary, an operation on ring elements intended
for public use should fully check its arguments for compatibility and
correctness (e.g. to avoid division by zero); if all checks pass, the
result is computed by passing raw pointers to the appropriate member
functions of the ring involved -- this member function assumes that the
values handed to it are compatible and valid; if not, "undefined
behaviour" will result (i.e. a crash if you are lucky).
Most of the member functions of a ring are for manipulating raw values
from that same ring, a few permit one to query properties of the ring.
The type of a raw value is RingBase::RawValue
, which helpfully
abbreviates to RawValue inside the namespace of RingBase. Wherever
possible the concrete implementations should be exception safe, i.e. they
should offer either the strong exception guarantee or the no-throw
guarantee (according to the definitions in Exceptional C++ by Sutter).
Shouldn't there be hints and notes about creating your own new type of concrete ring???
I have chosen not to use operator^
for computing powers because of a
significant risk of misunderstanding between programmer and compiler.
The syntax/grammar of C++ cannot be changed, and operator^
binds less
tightly than (binary) operator*
, so any expression of the form a*b^c
will be parsed as (a*b)^c
; this is almost certainly not what the
programmer intended. To avoid such problems of misunderstanding I
have preferred not to define operator^
; it seems too dangerous.
How to swap RefRingElem
s? Must be careful when trying to swap a
RefRingElem
with a RingElem
to avoid possible orphans (memory
leaks) or doubly owned values.
Note about comparison operators (<,<=,>,>=, and !=). The C++ STL
does have templates which will define all the relational operators
efficiently assuming the existence of operator<
and operator==
.
These are defined in the namespace std::rel_ops
in the standard
header file <utility>. I have chosen NOT to use these because they can
define only homogeneous comparisons; so the comparisons between
ConstRefRingElem
and int
or ZZ
would still have to be written out
manually, and I prefer the symmetry of writing them all out.
See p.69ff of Josuttis for details.
Printing rings is unsatisfactory. Need a mechanism for specifying a print name for a ring; and also a mechanism for printing out the full definition of the ring avoiding all/some print names. For instance, R = Q(x), S = R[a,b]; S could print as S, R[a,b] or Q(x)[a,b]. We should allow at least the first and the last of these possibilities.
The function myAssignZero
was NECESSARY because myAssign(x, 0)
was
ambiguous (ambiguated by the assignment from an mpz_t
). It is no longer
necessary, but I prefer to keep it (for the time being).
The requirement to use the type ConstRefRingElem
for function arguments
(which should normally be const RingElem&
is not ideal, but it seems hard
to find a better way. It is not nice to expect users to use a funny type
for their function arguments. How else could I implement access to
coefficients in a polynomial via an iterator, or access to matrix elements?
Would we want ++ and -- operators for RingElem
s???
I had hoped to place the auto_ptrs myZeroPtr
and myOnePtr
in RingBase, but
this caused trouble when rings are destroyed: the concrete ring was
destroyed before the zero and one elements were destroyed. It seems much
safer simply to duplicate the code for each ring implementation class.
Should (some of) the query functions return bool3
values?
What about properties which are hard to determine?
There used to be an IsFinite(R)
function in the documentation, but it
did not exist in the code. Should it exist?
How to generate random elements from a ring?
Note the slightly unusual return types for operator+=
etc;
it seemed daft to have a reference-to-reference. In contrast, I left
the return type for RingElem::operator=
as RingElem&
; it felt
very odd thinking of some other type RefRingElem
as the return type.
The dtor for ConstRefRingElem
is deliberately not virtual; idem for
RefRingElem
. This could potentially cause trouble if you convert a
pointer to RingElem
into a pointer to RefRingElem
; but if you do that,
you'd better be doubly sure about what you're doing anyway.
Anna thinks that NearestInteger
could handle specially elements of RingZ
rather than doing the full wasteful computation. Not sure if the extra
code and complication would really make a difference in practice.
This all needs to be sorted out!
How to decide whether a value can be mapped into the current_ring?
If the rings are marked as being equivalent isomorphically then we can just use the obvious isomorphism. A more interesting case is when a value resides in a ring which is a natural subring of the current_ring e.g. Z inside Q(sqrt(2))[x,y,z].
One could argue that to create Q(sqrt(2))[x,y,z]
we had to follow this path
Z
--> fraction field Q
Q
--> polynomial ring (1 indet) or DUP extension Q[gensym]
Q[gensym]
--> quotient by gensym^2-2 to get Q(sqrt(2))
Q(sqrt(2))
--> polynomial ring (3 indets) Q(sqrt(2))[x,y,z]
From this it ought to be easy to identify natural embeddings of Z
,
Q
, and (possibly) Q(sqrt(2))
in Q(sqrt(2))[x,y,z]
. We do
not get an embedding for Q[gensym] since we had to generate the symbol
gensym and no one else can create the same gensym. Because of this
it is not altogether clear that an independently created copy of
Q(sqrt(2))
can be embedded automatically, since that copy would
have a different symbol/gensym. Now if the algebraic extension were
achieved directly...
Would we want Q[x]/(x^2-2)
to be regarded as isomorphically equivalent
to Q[y]/(y^2-2)
? In fact there are two possible isoms: x <---> y
and x <---> -y
. I think that these should not be viewed as isom
automatically, especially as there is more than one possible choice.
In contrast, if R = Q[x]/(x^2-2)
, and S = Q[x]/(36-18x^2)
, and
T = Q[x]/(x^2-2)
. It is clear that Q[x]
can be mapped into
each of R
, S
and T
in a natural way. Of course, in each
case x
stands for sqrt(2), and it wouldn't be too hard to spot
that R
and T
are identical; it is not quite as simple to see
that R
and S
are isom. Presumably with a little more effort
one could create examples where it could be jolly hard to spot that
two such rings are just the same ring. For this reason, I think no
attempt should be made to spot such natural isoms between
independent rings. Had T
been created from R
(e.g. by
making copy via assignment) then they would no longer be independent,
and a natural isom could be deduced automatically. Now I think about
it, a facility to make a copy of a ring WITHOUT the natural isom
should be made available.
There is also a need for a way to specify that one ring embeds
naturally into another (and via which homomorphism), or indeed that
they are isomorphic. Isomorphism could be expressed by giving two
inverse homs -- the system could then check that the homs are inverse
on the generators, how it would check that the maps are homs is not so
clear (perhaps the only maps which can be created are homs). Oooops,
this would allow one to declare that Z
and Q
(or Z[x]
and
Q[x]
) are isom..... need to think more about this!
A similar mechanism will be needed for modules (and vector spaces). A module should naturally embed into a vector space over the fraction field of the base ring....
Conceivably someone might want to change the natural embedding between two rings. So a means of finding out what the natural embedding is will be necessary, and also a way replacing it.
There is also a general question of retracting values into subrings.
Suppose I have computed 2 in Q(x)
, can I get the integer 2 from
this? In this case I think the user must indicate explicitly that a
retraction is to occur. Obviously retraction can only be into rings
on the way to where the value currently resides.
Other points to note:
Q(x) = Z(x) = FrF(Z[x]) == FrF(FrF(Z)[x])
Q(alpha) = FrF(Z[alpha]) though denoms in Q(alpha) can be taken in Z
Q[alpha]/I_alpha = FrF(Z[alpha]/I_alpha) BUT the ideal on LHS is an ideal inside Q[alpha] whereas that on RHS is in Z[alpha]. Furthermore Z[alpha]/I_alpha is hairy if the min poly of alpha is not monic!