The class BigInt
is intended to represent (signed) integers of
practically unlimited range; it is currently based on the
implementation in 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 BigInt
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 BigInt
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 BigInt
and a machine
integer. The result is always of type BigInt
(with the sole
exception of remainder by a machine integer). Do remember, though,
that operations between two machine integers are handled directly by
C++, and problems of overflow can occur.
It is important not to confuse values of type BigInt
with values of type
RingElem
which happen to belong to the ring RingZZ
. In summary, the
operations available for RingElem
are those applicable to elements of
any ordered commutative ring, whereas the range of operations on BigInt
values is wider (since we have explicit knowledge of the type).
A value of type BigInt
may be created from:
BigInt
mpz_t
value; in this case the ctor call must have first
argument CopyFromMPZ
and the second argument is the mpz_t
value to be copied
No constructor for creating a BigInt
from a std::string
(or a
char*
) is provided. This is for two reasons: (A) a technical
ambiguity in BigInt(0)
since 0
is valid as a char*
; (B) conversion
from a decimal string representation is sufficiently costly that it
should be highly visible. Conversion from a string to a value of type
BigInt
can be effected using the convert
function (see convert
) or
using operator>>
and std::istringstream
from the C++ library.
See IntOperations
mpzref(n)
-- this gives a (const) reference to the mpz_t
value inside a BigInt
object.
You should use this accessor very sparingly (but
it is handy for calling GMP functions directly).
The implementation is structurally very simple, just rather long and
tedious. The value of a BigInt
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 two functions
called 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 MachineInt
to understand how
that class is used.
Currently functions which return BigInt
values will copy the result (upon
each return) -- an attempt to avoid the waste with proxy classes caused a
problem see
The official GMP interface is certainly more efficient, so the CoCoA library will presumably eventually switch to using GMP directly.
No bit operations: bit setting and checking, and/or/xor/not.
The code is long, tedious and unilluminating. Are there any volunteers to improve it?
2012
BigInt
and MachineInt
together into IntOperations
-
2011
ZZ
renamed into BigInt
:
avoid confusion with RingZZ
and its name in CoCoA system
random
has changed (was random(lo,hi)
):
see RandomZZStream
, RandomLongStream