Re: [boost] Yet another bignum type

From: Oliver Kullmann (O.Kullmann_at_[hidden])
Date: 2006-11-30 13:08:48

Hi,

I would like to join the critics of the design, just trying
to clarify certain things.

On Thu, Nov 30, 2006 at 04:26:10PM -0000, Martin Bonner wrote:
> ----Original Message----
> From: boost-bounces_at_[hidden]
> [mailto:boost-bounces_at_[hidden]] On Behalf Of Maarten Kronenburg
> Sent: 30 November 2006 12:09 To: boost_at_[hidden]
> Subject: Re: [boost] Yet another bignum type
> 
> > 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.
> 
> 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