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.
Constructors:
A value of type ZZ
may be created from:
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
) or
using operator>>
and std::istringstream
from the C++ library.
+ the sum - the difference * the product / floor quotient (divisor must be positive) % least non-negative remainder (divisor must be positive) = assignment
+=, -=, *=, /=, %= definitions as expected; LHS must be of type ZZ
==, !=, <, <=, >, >= comparison (using the normal arithmetic ordering)See also the
cmp
function below.
++, -- (prefix) use these if you can ++, -- (postfix) avoid these if you can, as they create temporaries
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).
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.
power(a, b) returns a to the power b; powermod(a, b, m) returns a to the power b modulo m;
cmp(a, b) returns an ``int`` which is < 0 if a < b, == 0 if a == b, > 0 if a > b.
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)
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.
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.
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 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 |
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.
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?