cmat is an exact arithmetic calculator program, written in ANSI C.
It is designed to perform many of the standard arithmetical operations
that can be carried out exactly, without approximations, on matrices and
polynomials whose coefficients are either rational numbers, complex rational
numbers, or elements of Z_{p} - the finite field of p elements,
where p is a prime less than R0
=2^{16}=65536.
The C source files are available as a compressed tar file from http://www.numbertheory.org/cmat/.
It is assumed that the gnu C compiler is available. Otherwise all references to gcc in the three makefiles should be replaced by cc.
To install the program, transfer the file cmat.tar.gz to the user's home directory and type the following UNIX commands:
gunzip cmat.tar
tar xvf cmat.tar
rm cmat.tar
cmat has been developed on Pyramid and Sun machines, so there are bound to be glitches in the compilation on other UNIX machines. However a UNIX guru should be able to make the few changes necessary to allow compilation to proceed smoothly.
The file config.h contains default paths which are set up on the assumption that the four executable programs live in the directory /usr/local/bin while the *.dat files live in the directory /usr/local/lib/cmat.
To change the number M0
of stored
global variables of each arithmetical type, the file integer.h should be edited and
the programs recompiled.
1. Files. There are various *.h files:
as well as definitions of constants R0,T0,M0,Z0,Y0,BUFLEN
and
some abbreviations.
There are various *.dat files:
.cmatrc sets up the directory paths:
cmat=. for the executable programs and
datpath=. for the *.dat files.
parse.y is a yacc file which produces a file parse.c for use in parsing simple arithmetic expressions suitable for use as formulae for the (i,,j)th element of a matrix. This line of the Makefile can be removed if one does not have yacc and the default file parse.c can be used.
2. The arithmetic data types.
The basic structure is the MPI (multiple precision integer) M which has three components: an unsigned integer M.D, a variable array of M.D+1 unsigned integers:
M.V[0],...,M.V[M.D],
where each of these array elements must be less thanR0
. There is a third structure component M.S, which records the
sign. If m is the integer represented by the MPI M, there is a corresponding
representation of m to base R0
:
m=M.S(M.V[0]+...+M.V[M.D]R0^{M.D}).
A rational number is represented by a structure M called an MPR. Here M.N and M.D are pointers to MPI's representing the numerator and denominator, respectively. The denominator must be positive and the numerator and denominator relatively prime.A complex rational number m is represented by a structure M called an MPCR. Here M.R and M.I are pointers to MPR's representing the real and imaginary parts of m.
Polynomials are represented by linked lists along the lines of H. Flanders, Scientific Pascal, pp. 175-185, 342-357, Reston 1984, (Second Edition Birkhäuser, 1995):
POLYI, POLYR, POLYCI, POLYCR, POLYm,
each terminated by the NULL pointer. Only the non-zero terms of the polynomial are recorded. The zero polynomial is represented by the NULL pointer.
Matrices of scalars are represented by structures:
MPMATI, MPMATR, MPMATCI, MPMATCR, MPMATm.
If M is such a structure, the components M.R and M.C record the number of rows and columns, while the component M.V corresponds to a two-dimensional array of scalars of variable size.
There are also correspondingly matrices with polynomial elements:
MPMATPI, MPMATPR, MPMATPCI, MPMATPCR, MPMATPm.
It is important to remember that for the polynomial structure POLYm and
matrices MPMATm and MPMATPm, the coefficients are always understood to be
unsigned integers less than a prime p (the modulus), with p < R0
. It is
the user's responsibility to keep track of the various moduli used and to
perform calculations with arithmetic objects only having the same prime modulus.
3. Other Global Variables.
Up to M0
objects of each type can be created and stored as global variables:
M0
-1];
M0
-1];
M0
-1];
M0
-1];
M0
-1];
M0
-1;
M0
-1];
M0
-1];
M0
-1];
M0
-1];
M0
-1];
These arrays always contain the appropriate zero object until replaced by either an object entered by the user or one resulting from a calculation.
4. Saving for future sessions.
When each of the programs cmatr, cmatcr, cmatm is run, the following files are respectively opened in the user's current directory:
5. Memory bank. We use a memory banking algorithm implemented by Peter Adams. Previously, MPI's and other data structures were malloced and freed whenever they were required, which proved to be very time consuming. About 50% of the execution time was spent in calls to malloc() and free().
Now, rather than freeing when we have finished using them, we place them on a list of free MPI's (and corresponding lists for other data structures). When another MPI is required, if there is one of an appropriate size on the list, it can be used rather than calling malloc().
Any suggestions for improvement, as well as bug reports, should be reported to the author:
K. R. Matthews
20th June 2006