ZZ

© 2005,2007 John Abbott
GNU Free Documentation License, Version 1.2



index page

User documentation

Generalities

The class ZZ is intended to represent (signed) integers of practically unlimited range; it is currently based on the GMP "big integer" library. This code forms the interface between CoCoALib and the big integer library upon which it relies. It seems most unlikely that GMP will be displaced from its position as the foremost library for big integer arithmetic; as a consequence the class ZZ may eventually be replaced by GMP's own C++ interface.

The usual arithmetic operations are available with standard C++ syntax but generally these incur run-time overhead since results are returned through temporaries which are created and destroyed silently by the compiler. Thus if the variables a, b and c are each of type ZZ then a = b+c; is a valid C++ statement for placing the sum of b and c in a, BUT the sum is first computed into a hidden temporary which is then copied to a, and then finally the temporary is destroyed.

There is an important exception to the natural syntax: ^ does NOT denote exponentiation; you must use the function power instead. We have chosen not to define operator^ to perform exponentiation because it is too easy to write misleading code: for instance, a*b^2 is interpreted by the compiler as (a*b)^2. There is no way to make the C++ compiler use the expected interpretation.

A single arithmetic operation and assignment may be effected slightly faster using a less natural notation; this approach avoids using the hidden temporaries required with the natural notation. Thus instead of a = b+c; one can write add(a, b, c);. The reason for offering both syntaxes is to allow simpler and more natural code to be written for first versions; the time-critical parts can then be recoded using the faster but less natural notation (after suitable profiling tests, of course).

Arithmetic may also be performed between a ZZ and a machine integer. The result is always of type ZZ. Do remember, though, that operations between two machine integers are handled directly by C++, and problems of overflow can occur.

The Functions Available For Use

Constructors: A value of type ZZ may be created from:

No constructor for creating a ZZ from a std::string (or a char*) is provided. This is for two reasons: a technical ambiguity in ZZ(0) since 0 is valid as a char*; conversion from a decimal string representation is sufficiently costly that it should be highly visible. Conversion from a string to a value of type ZZ can be effected using the convert function (see convert) or using operator>> and std::istringstream from the C++ library.

Infix operators for ZZs

(A) normal arithmetic (potentially inefficient because of temporaries)
    +    the sum
    -    the difference
    *    the product
    /    floor quotient (divisor must be positive)
    %    least non-negative remainder (divisor must be positive)
    =    assignment

(B) arithmetic and assignment
   +=, -=, *=, /=, %=   definitions as expected; LHS must be of type ZZ

(C) arithmetic ordering
    ==, !=, <, <=, >, >=  comparison (using the normal arithmetic ordering)
See also the cmp function below.

(D) increment/decrement
    ++, -- (prefix)   use these if you can
    ++, -- (postfix)  avoid these if you can, as they create temporaries

Functions applicable to ZZs

(A) procedures for arithmetic (assignment is always to leftmost argument(s))
     add(a, b, c)       <--->  a = b+c
     sub(a, b, c)       <--->  a = b-c
     mul(a, b, c)       <--->  a = b*c
     div(a, b, c)       <--->  a = b/c  (floor division, divisor must be positive)
     mod(a, b, c)       <--->  a = b%c  (least non-negative remainder, divisor must be positive)
     quorem(a, b, c, d) <--->  a = c/d, b = c%d  (divisor must be positive)
     divexact(a, b, c)  <--->  a = b/c  (fast, but division must be exact)
  
     power(a, b, c)     <--->  a = b^c
     powermod(a, b, c, m) <---> a = b^c mod m
     neg(a, b)          <--->  a = -b
     abs(a, b)          <--->  a = abs(b)
     gcd(a, b, c)       <--->  a = gcd(b, c)  non-negative gcd
     lcm(a, b, c)       <--->  a = lcm(b, c)  non-negative lcm
     exgcd(g, c_a, c_b, a, b) <--->  g = gcd(a, b), c_a, c_b are set so that
                                     g = c_a*a + c_b*b and
                                     abs(c_a) < abs(b) and
                                     abs(c_b) < abs(a).

(B) query functions (all take 1 argument)
     IsZero   true iff number is zero
     IsEven   true iff number is even
     IsOdd    true iff number is odd
     IsPPrime true iff number satisfies a probabilistic primality test
              (an optional second argument (type: ``unsigned int``) specifies
               how many iterations to perform; the default value is 25)
     sign(n)  gives -1 (machine integer) to mean n is negative,
                     0 (machine integer) to mean n is zero,
                    +1 (machine integer) to mean n is positive.

(C) Exponentiation (the exponent of the power must be non-negative)
     power(a, b)          returns a to the power b;
     powermod(a, b, m)    returns a to the power b modulo m;

(D) the cmp function
     cmp(a, b)      returns an ``int`` which is
                      < 0    if a < b,
                      == 0   if a == b,
                      > 0    if a > b.

(E) sundry standard functions
     factorial(n)    factorial for non-negative n
     binomial(n, r)  binomial coefficient (r must fit into a long)
     fibonacci(n)    nth Fibonacci number
     abs(n)          the absolute value of n
     log(n)          natural logarithm of the absolute value of n (as a ``double``)
     random(lo, hi)  a random integer N s.t. lo <= N <=  hi; error if lo > hi.
     gcd(a, b)       greatest common divisor (result is >= 0)
     lcm(a, b)       least common multiple (result is >= 0)

(F) Conversion functions
(G) Miscellany
(H) Functions violating encapuslation

Error Conditions and Exceptions

Error conditions are signalled by exceptions. Examples of error conditions are impossible arithmetic operations such as division by zero, overly large arguments (e.g. second argument to binomial must fit into a machine "long"), and exhaustion of resources.

Currently the exception structure is very simplistic:

ERR::ArgTooBig value supplied is too large for the answer to be computed
ERR::BadArg unsuitable arg(s) supplied (or input number too large)
ERR::BadNumBase the base must be between 2 and 36
ERR::DivByZero division by zero
ERR::ExpTooBig exponent is too large
ERR::IntDivByNeg inexact integer division by a negative divisor
ERR::NegExp negative exponent
ERR::ZeroModulus the modulus specified is zero

Maintainer Documentation

The implementation is structurally very simple, just rather long and tedious. The value of a ZZ object is represented as an mpz_t; this is a private data member, but to facilitate interfacing with code which uses mpz_t values directly I have supplied the functions mpzref which allow access to this data member.

The output function turned out to be trickier than one might guess. Part of the problem was wanting to respect the ostream settings.

Of course, input is a mess. Nothing clever here.

Check also the documentation for MachineInteger to understand how that class is used.

Bugs, Shortcomings, etc.

The official GMP interface is certainly more efficient, so the CoCoA library will eventually switch to using GMP directly.

The power functions should handle power(0,0) correctly; maybe they should also allow high powers of -1,0,1 (without complaining about the exponent being too big).

No bit operations: bit setting and checking, and/or/xor/not.

Only partial access to all the various division functions offered by the C interface to GMP. Many other GMP functions are not directly accessible.

The code is long, tedious and unilluminating. Are there any volunteers to improve it?