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?