Re: [boost] Yet another bignum type

From: Maarten Kronenburg (M.Kronenburg_at_[hidden])
Date: 2006-11-30 18:44:04

"Oliver Kullmann"  wrote in message
> Hi,
>
> I would like to join the critics of the design, just trying
> to clarify certain things.
>
> >
> > > In my opinion software design is not mathematical proof that one
> > > design is better than another, but there is the mathematical fact
> > > that the set of unsigned integers is a subset of the integers, and
> > > the set of modular integers is a subset of the integers.
> >
> >
> > But your classes do not represent the SET of integers and the SET of
> > modular integers.  They represent the FIELDS (you include the operators
> > - and the class wouldn't be much use if they didn't.
> >

Here I disagree.
The class represents the set, and an object of that class represents an
element from that set,
whether the set is employees and secretaries, or integers and unsigned
integers.

> > The modular integers do NOT form a sub-field of the integers, which is
> > why you shouldn't use derivation to represent them.
> >
>
> In computer science we have to be very precise about what we are
speaking ---
> up to the formal details (this is different from ordinary mathematics,
where
> often handwaving is fine).
>
> There is no "the set of integers" etc.
>
> First of all, depending on your
> foundations (for general mathematics set theory is best suited) there
> are (several) *representations" of natural numbers and integers.
>
> Ordinary mathematics often (especially nowadays) actually does not go down
> to the level of representation, but just takes one representation of
> the objects as granted --- but, of course, in computer science the
> representation matters.
>
> Second, as emphasised in the above quote, for mathematics the pure sets
> don't matter, but the *structures* are of importance, while the
translation
> between structures is handled by "homomorphisms". So we have the semiring
> (N_0, +, *, 0, 1) of natural numbers (using here some fixed implementation
> --- actually we are speaking of isomorphism classes of semirings), and
> the ring (Z, +, *, 0, 1) of integers. The semiring N_0 has a natural
> embedding into Z, and thus is considered as a subsemiring in mathematical
> practice. So well, at least here there is in mathematical practice (which
> is necessarily different from what happens on a computer --- see below)
> a clear relation between natural numbers and integers.
>
> But there is nothing like "modular integers". For every positive integer m
> we have the ring Z / mZ of "integers modulo m", which has two standard
> representations :
>  - mathematically meaningful is to use the standard quotient construction
of
>    elements of Z/mZ as equivalence classes;
>  - easier to understand (but finally just a "hack") is to represent Z/mZ
as the
>    integers 0, ..., m-1.
>    (I use this representation when I teach modular arithmetic to second
year undergraduate
>    students in computer science, but only because for them handling
equivalence classes
>    is too complicated.)
>
> So here only by using some special representation of Z/mZ the *set* of
"integers modulo m" is
> a subset of N_0. But no mathematician would consider Z/mZ as somehow
contained in N_0 (or Z),
> since Z/mZ is not embedabble into Z as the fundamental structure, that is,
as a ring
> (adding +1 m times yields 0 in Z/mZ).
>
> (In the above quote by mistake "fields" are mentioned; only Z/mZ here can
be a field (namely in case m is
> a prime number).)
>
> So Z/mZ is not directly related to N_0 and Z, only there is a conversion
from Z to Z/mZ (which is
> a homomorphism), and a conversion from Z/mZ to N_0 (which is not a
homomorphism, but only a
> canonical representation).
>
> So modular arithmetic is related to natural numbers and integers only by
conversion. What about
> the natural numbers and the integers?
>
> In an earlier e-mail already the very instructive example of "squares vs.
rectangles" was mentioned
> (much nice material on it available online). The point here is that the
mathematical world is
> eternal, nothing ever gets constructed or destroyed, but everything always
already exists,
> and we only invent names to point into the infinite static object world.
And, of course, a mathematical
> object never can be modified.
>
> This does no work on a computer. There, especially when handling large
objects, objects need to be modified.
> And we need to construct objects (and destruct them).
> And then the mathematical relations break down (in general).
>
> For the relationship between N_0 and Z the breakdown can be demonstrated
by using a negation member function
> for integers, which cannot work for natural numbers (under the same
invariants).
> So, in this sense N_0 should not be derived from Z.
>
> One escape here (as already mentioned) would be to consider only
non-modifiable objects.
> But, especially regarding the large objects we potentially have to handle
here, this approach,
> which must be based on copy-semantics, would be very inefficient (and
misleading).
>
> Another escape (in order to use derivation) would be to derive N_0 from a
superclass of Z, where this
> superclass only considers the semiring-structure of Z (that is, without
additive inverse).
> This would be possible, and perhaps also somewhat sensible. But it might
complicate the
> whole design.
>
> So, to conclude, representations of N_0 should not be derived from Z (or
the other way around;
> also in generic programming the normal concept of N_0 is not a refinement
of the normal concept of Z
> (neither the other way around)).
>
> The classes N_0, Z and Z/mZ are all different classes (class templates),
where well defined conversions
> (explicit or implicit) are responsible for the relations.
>
> A final remark: C++ is very close to ordinary mathematical practice (much
more so than Java or functional programming)
> with its emphasise on copy semantics, its support for conversions (basic
handwaving in mathematics is just
> implicit conversion(!)) and its support for parameterised types (in this
way all the parameters normally hidden
> in mathematical practice can be made explicit).
>
> Object orientation does not mix very well with mathematics; of course,
it's a computer science thing, but
> must be used with great care. In a mathematical world nobody would put
elements of N_0 and Z, when
> coming from different structures, into the same container (but
mathematicians "use" the type-safe
> container in C++ style, not the type-unsafe container in Java style).
>
> Hope this was a bit helpful to clarify some points.
>
> Oliver
>
>