Arithmetic(3) Arithmetic(3)
11 March 1990
NAME
arithmetic, Zadd, Zsub, Zminus, Zmult, Zdivalg, Zgcd, Zeq, Zlessoreq,
Collect, Showme, Shcopy, Size, Constant, Initial - arithmetic with
arbitrary length integers or polynomials
SYNOPSIS
#include integer.h
#include polynomial.h
#include Ztools.h
unsigned short *Zadd(a, b)
unsigned short *a, *b;
unsigned short *Zsub(a, b)
unsigned short *a, *b;
unsigned short *Zminus(a)
unsigned short *a;
unsigned short *Zmult(a, b)
unsigned short *a, *b;
unsigned short *Zdivalg(a, b, r)
unsigned short *a, *b, *r;
void Zgcd(a, b, g, aa, bb)
unsigned short *a, *b, *g;
unsigned short *aa, *bb;
char Zeq(a, b)
unsigned short *a, *b;
char Zlessoreq(a, b)
unsigned short *a, *b;
void Initial(m)
unsigned short m;
char Collect(msg, a)
char *msg;
unsigned short *a;
void Showme(msg, a)
char *msg;
unsigned short *a;
void Fshowme(fp, msg, a)
FILE *fp;
char *msg;
unsigned short *a;
unsigned short *Constant(a)
long a;
void Shcopy(a, b)
unsigned short *a, *b;
unsigned short Size(a)
unsigned short *a;
void bailout(msg)
char *msg;
DESCRIPTION
These routines provide a uniform interface for computations involving
either arbitrary precision integers or polynomials over finite fields.
Both integers and polynomials are stored in little-endian order as an
- 1 - Formatted: April 27, 2024
Arithmetic(3) Arithmetic(3)
11 March 1990
array of unsigned shorts. The value of the first short in the array is
the offset of the most significant digit; in the case of polynomials,
this is the highest degree coefficient, in the case of integers, it is
a signbit. These routines use the storage management package called
"warehouse", consisting of the routines release(), capture(), and
makeWH() to have enough storage available for their computations.
Thus, any program which uses these routines must begin with a call to
Initial() which makes available some prlminary scratch computation
areas. In the case of polynomials, the parameter to Initial() is the
modulus of the finite field over which the polynomials are to be
computed. Zadd(), Zsub(), and Zmult() return a pointer to a very long
integer or polynomial which is the sum, difference, or product,
respectively, of their arguments. Zminus() returns the negative of its
argument. Zdivalg() computes the quotient of the dividend a by the
divisor b and returns it. If the value of ptr is not NULL, then the
remainder is stored at that location. The conventions used by
Zdivalg() are: in the case of integers, the remainder always has the
same sign as the dividend, and in the case of polynomials, the
quotient is always monic. In both cases, the relation a = b q + r
holds. Zgcd() computes the greatest common divisor of a and b and
stores it in the location pointed to by g. The values of a/g and b/g,
are stored in aa and bb, respectively. Zeq() returns a non-zero value
if its arguments are equal, and zero otherwise. Zlessoreq() returns a
non-zero value if its first argument is less than or equal to its
second argument, and zero otherwise. Some additional utilities are
supplied to make common treatment of integers and polynomials easier.
Collect() is an input routine which prints its message msg on standard
output and then reads an integer or polynomial and stores it at the
location pointed to by a. Both integers and polynomials are entered in
big-endian order. Different coefficients of polynomials are separated
by whitespace (which means, in this case, any non-digit characters)
and are reduced modulo m before being stored. Integers are entered in
digits written to the base 2^16 = 65536 which are also separated by
whitespace; they may be preceeded an optional sign. Note that, at this
time, decimal input is not supported except for numbers whose size is
less than 65536. Lines may be continued by using the ampersand
character (&) at the end of a line. Showme() is an output routine
which writes its message to standard output and follows it by an
integer or polynomial written with the same conventions as used by
Collect(). Fshowme() is to Showme() as fprintf() is to printf().
Constant() returns a properly formatted very long integer or
polynomial with the value represented by its argument. The argument
must have absolute value bounded by 2^16 = 65536. In general, the
value of Constant() should be copied to a safe location, since it re-
uses the same storage space. Shcopy() copies the array of its first
argument int the location pointed to by its second argument. It
assumes that there is enough room at the second location; it is the
programmer's responsibility to ensure that this is, in fact, the case.
Note, for example, that the integer constant 1 takes up three memory
locations: one for a description of how many digits it needs, one for
the value, and one for the signbit.
- 2 - Formatted: April 27, 2024
Arithmetic(3) Arithmetic(3)
11 March 1990
LIBRARIES
These routines are implemented in one of two ways. Those which are
fundamentally different for integers and polynomials are written as
separate functions, and compiled as separate libraries. Those which
could conveniently be written as one function are compiled in yet a
third library; the interface is handled via macro definitions in the
header files. The standard way to write a routine which will work with
either integers or polynomials is to put
#ifdef INTEGERS
#include integer.h
#elif defined POLYNOMIALS
#include polynomial.h
#else
some line to make the compiler complain
#endif
at the top of the relevant files, and then to have two separate
compiliations cc -DINTEGERS ... -lZ -lU cc -DPOLYNOMIALS ... -lP -lU
DIAGNOSTICS
Illegal operations detected by these routines result in a call to a
routine called bailout() which prints a message and then exits.
FILES
integer.h
polynomial.h
utility.h
Ztools.h
libP.a
libZ.a
libU.a
SEE ALSO
warehouse(3), rational(3), quadratic(3)
- 3 - Formatted: April 27, 2024
