Re: [boost] Yet another bignum type

From: Oliver Kullmann (O.Kullmann_at_[hidden])
Date: 2006-12-04 13:24:14

On Fri, Dec 01, 2006 at 10:16:11AM -0000, Martin Bonner wrote:
> 
> One question I have though.  
> > There is no "the set of integers" etc.
> 
> What is Z if it is not "the set of integers"?  
> 
> Given the precision of the rest of your reply I am pretty sure I have
> misunderstood something here, but what?
>

Ask a mathematician to *define* Z:

 - Some (especially in these days) will not understand what you
   are talking about (I imagine).

 - Most will answer that *up to isomorphism* there is exactly one structure
   (Z, +, *, 0, 1) fulfilling some axioms --- this amounts to the situation
   in generic programming, where we have a concept of integers and associated 
   operations, and we write generic algorithms using this concept (like generic
   graph algorithms using the Boost graph library concepts (however the Z-situation
   is a bit different since all models are isomorphic here, which is not so for graphs)).

   But in our situation this is not enough --- we need a model.

 - Finally, there might be some enlightened ones left, which are actually able
   to construct Z. The standard way (most appropriate for general mathematics
   in my opinion) is based on set theory, and would first construct natural numbers
   as the set 0 := empty set and n+1 := set of numbers 0, ..., n.
   Z then would be constructed by the ordinary quotient construction (so an element
   of Z is an equivalence class of pairs of natural numbers; this is the same construction
   as to get the rational numbers from the integers, only this time addition is used instead
   of multiplication).

So as a generic concept there might be many implementations of Z, but this doesn't matter.
This covers the situation regarding the structure of Z as a commutative ring.

However, when going into the implementation, that is, really defining the *set* Z (and the
operations) there are many choices.
For a standard implementation there is a good chance for getting the above one.
However there are other choices; an extreme case (which is useful under circumstances)
starts with "the" real numbers and extracts the integers.
Another approach, more down-to-earth this time, would avoid the equivalence classes,
and would give a concrete representation.
Finally there are (in special circles) alternative set theories and alternative foundations.

The main argument about the big-number-library is (as far as I understand it) about the concepts
involved. And these ambiguities (what are "really" the integers "for us"), which are much less
critical for (ordinary) mathematics, are nevertheless similar to the "leak" of abstraction in
(ordinary) mathematics: An integer is typically more an algebraic thing, and less ambiguous, but once
you make a natural number out of it, then it suddenly is a cardinal numbers (for counting things)
and an ordinal number (for indexing things), which involve both other (different) abstractions.
Still on the algebraic side, some handwaving goes on with modular arithmetic.

Hope that helped a bit (and did not create more confusion ;-)).

Oliver