CoCoALib-0.9905 date: 23 May 2007


CoCoA::ZZ Class Reference

#include <ZZ.H>

Collaboration diagram for CoCoA::ZZ:

Collaboration graph
[legend]
List of all members.

Public Member Functions

 ZZ (const rtn &to_be_owned)
 ZZ ()
 ZZ (MachineInteger i)
 ZZ (const ZZ &from)
 ZZ (const mpz_t to_be_copied)
 ~ZZ ()
ZZoperator= (const ZZ &rhs)
ZZoperator= (const ZZ::rtn &rhs)
ZZoperator+= (const ZZ &rhs)
ZZoperator-= (const ZZ &rhs)
ZZoperator *= (const ZZ &rhs)
ZZoperator/= (const ZZ &rhs)
ZZoperator%= (const ZZ &rhs)
ZZoperator= (MachineInteger rhs)
ZZoperator+= (MachineInteger rhs)
ZZoperator-= (MachineInteger rhs)
ZZoperator *= (MachineInteger rhs)
ZZoperator/= (MachineInteger rhs)
ZZoperator%= (MachineInteger rhs)
const ZZoperator++ ()
const ZZoperator-- ()
const ZZ operator++ (int)
const ZZ operator-- (int)

Private Member Functions

 ZZ (MP_INT to_be_owned)

Private Attributes

mpz_t myRep

Friends

class rtn
mpz_t & mpzref (ZZ &N)
const mpz_t & mpzref (const ZZ &N)

Classes

class  rtn

Detailed Description

      Copyright (c)  2005,2007 John Abbott
      Permission is granted to copy, distribute and/or modify this document
      under the terms of the GNU Free Documentation License, Version 1.2;
      with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
      A copy of the licence is included in the file COPYING in this directory.



User Documentation for the class ZZ
===================================

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:
 * nothing, in which case the value is zero
 * a machine integer
 * another value of type ZZ
 * an mpz_t value (the ZZ object will make its own private copy of the value)

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.txt)
or using [operator>>] and [std::istringstream] from the C++ library.

The infix operators for ZZ are:

(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 are:

(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
   mantissa(n)  if n is zero, produces 0.0
                otherwise if n>0 a value between 0.5 and 0.999...
                otherwise (when n<0) a value between -0.5 and -0.999...
                The bits of the floating point result are the topmost
                bits of the binary representation of n.
   exponent(n)  result is a [long] whose value is the least integer e such that
                2^e > abs(n).  If n is zero, result is zero.

(G) Miscellany
   NumDigits(n, b) the number of digits n has when written in base b
                [the result may sometimes to be too large by 1]
   invmod(a, r, m) computes in a the multiplicative inverse of r modulo m,
                 if no inverse exists the function returns false (and a
                 may contain a meaningless value) otherwise it returns true.

(H) Functions violating encapuslation
   mpzref(n)   this gives a (const) reference to the mpz_t value inside
               a ZZ object.  You should use this accessor very sparingly!


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:
  * exceptions indicating exhaustion of resources are those from the
    system, this library does not catch them;
  * all other errors produce a CoCoA::ErrorInfo exception; for instance
      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 for ZZ
===============================

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?

Definition at line 42 of file ZZ.H.


Constructor & Destructor Documentation

CoCoA::ZZ::ZZ MP_INT  to_be_owned  )  [private]
 

CoCoA::ZZ::ZZ const rtn to_be_owned  )  [inline]
 

Definition at line 321 of file ZZ.H.

References CoCoA::ZZ::rtn::myRep, and myRep.

CoCoA::ZZ::ZZ  ) 
 

CoCoA::ZZ::ZZ MachineInteger  i  )  [explicit]
 

CoCoA::ZZ::ZZ const ZZ from  ) 
 

CoCoA::ZZ::ZZ const mpz_t  to_be_copied  )  [explicit]
 

CoCoA::ZZ::~ZZ  )  [inline]
 

Definition at line 289 of file ZZ.H.

References myRep.


Member Function Documentation

ZZ& CoCoA::ZZ::operator= const ZZ rhs  ) 
 

ZZ & CoCoA::ZZ::operator= const ZZ::rtn rhs  )  [inline]
 

Definition at line 328 of file ZZ.H.

References myRep.

ZZ& CoCoA::ZZ::operator+= const ZZ rhs  ) 
 

ZZ& CoCoA::ZZ::operator-= const ZZ rhs  ) 
 

ZZ& CoCoA::ZZ::operator *= const ZZ rhs  ) 
 

ZZ& CoCoA::ZZ::operator/= const ZZ rhs  ) 
 

ZZ& CoCoA::ZZ::operator%= const ZZ rhs  ) 
 

ZZ& CoCoA::ZZ::operator= MachineInteger  rhs  ) 
 

ZZ& CoCoA::ZZ::operator+= MachineInteger  rhs  ) 
 

ZZ& CoCoA::ZZ::operator-= MachineInteger  rhs  ) 
 

ZZ& CoCoA::ZZ::operator *= MachineInteger  rhs  ) 
 

ZZ& CoCoA::ZZ::operator/= MachineInteger  rhs  ) 
 

ZZ& CoCoA::ZZ::operator%= MachineInteger  rhs  ) 
 

const ZZ& CoCoA::ZZ::operator++  ) 
 

const ZZ& CoCoA::ZZ::operator--  ) 
 

const ZZ CoCoA::ZZ::operator++ int   ) 
 

const ZZ CoCoA::ZZ::operator-- int   ) 
 


Friends And Related Function Documentation

friend class rtn [friend]
 

Definition at line 51 of file ZZ.H.

mpz_t& mpzref ZZ N  )  [friend]
 

Definition at line 271 of file ZZ.H.

const mpz_t& mpzref const ZZ N  )  [friend]
 

Definition at line 276 of file ZZ.H.


Member Data Documentation

mpz_t CoCoA::ZZ::myRep [private]
 

Definition at line 47 of file ZZ.H.

Referenced by CoCoA::mpzref(), operator=(), CoCoA::ZZ::rtn::rtn(), ZZ(), and ~ZZ().


The documentation for this class was generated from the following file:
Generated on Wed May 23 13:45:01 2007 for CoCoALib by  doxygen 1.4.6