\chapter{Overview of the {\bf \ref{PARI}} System}

\section{Introduction.}

The PARI system is a package which is capable of doing formal computations
on recursive types at high speed; it is primarily aimed at number
theorists, but can be used by people whose primary need is speed.

Although quite an amount of symbolic manipulation is possible in PARI, this
system does very badly compared to much more sophisticated systems like
Reduce, Macsyma, Maple, Mathematica or Scratchpad (now Axiom) on such
manipulations (e.g. multivariate
polynomials, formal integration, etc\dots). On the other hand, the two
main advantages of the system is its speed (which can be between 5 and
100 times better on many computations than the above mentioned systems),
and the possibility of using directly data types which are familiar
to mathematicians.

It is possible to use PARI in two different ways:

\quad 1) as a library, which can be called from any upper-level language
application (for instance written in C, C$++$, Pascal or Fortran);

\quad 2) as a sophisticated programmable calculator, named {\bf GP}, which
contains most of the standard control instructions of a standard language
like C.

The use of GP is explained in chapters 2 and 3, and the programming in library
mode is explained in chapters 3, 4 and 5. In the present chapter 1, we give
an overview of the system.

\subsectitle{Implementation notes.}

Version \vers{} of the PARI package contains essentially four versions. The 
first one is a specific implementation for 68020/68030/68040/68060 based
computers which contains a kernel (for
the elementary arithmetic operations on multiprecise integers and real numbers,
and binary/decimal conversion routines) entirely  written in MC68020 assembly
language (around 7000 lines), the rest being at present entirely written in 
ANSI C with a C++-compatible syntax (previous versions were written in K\&R C,
but this has now been abandoned).
The system runs on SUN-3/xx, Sony News, NeXT cubes and on 680x0 based
Macs with x$\ge$2. It should be very easy to port on any other 680x0 based
machine like for instance the Apollo Domain workstations.

Note that the assembly language source code uses the SUN syntax,
which for some strange reason differs from the Motorola standard used by
most other 680x0 machines in the world. On the Mac disquettes, we have
included a program which automatically converts
from the SUN syntax into the standard one, at least for the needed PARI
assembly file. On the Unix distribution, we have included other versions
of the assembly file, using different syntaxes. 

The second version is a specific implementation for SPARC version 7 based
workstations, like the SPARCstation 1, 1+, 2 and the Solbourne 4000. This
version contains only a few hundred lines of assembly code, and is usually
slightly faster on the SPARCstation 1+ than on a SUN-3/60 or SUN-3/80.
A variant of this version for SPARC version 8 (both Supersparc and Microsparc)
is also included, see appendix A for more details.

The third version is a specific implementation for the Hewlett-Packard HP-PA
architecture. Like the Sparc versions, this contains a few hundred lines of 
assembly code, and is quite fast.

Finally, a fourth version is written entirely in C, and should be portable with
not too much trouble to any 32-bit computer having no real memory constraints.
It is again at least 2 times slower than the SPARC version. This version has 
been tested for example on the DECstations 3100 and 5000. A 64-bit version
is currently under development and should be available soon.

In addition to Unix workstations and Macs, Pari has been ported to a 
considerable number of smaller and larger machines, for example the VAX,
68000-based machines like the Atari, Mac Classic or Amiga 500, 68020 machines
such as the Amiga 2500 or 3000, and even to MS-DOS 386 or better machines, 
using the {\tt djgpp} port of the GNU C compiler and DOS-extender.

\section{The PARI \ref{types}.}

The crucial word in PARI is \ref{recursivity}: most types
which are handled are recursive. For example, the basic type {\bf
\ref{Complex}} exists. However, the components (i.e. the real and imaginary part)
of
such a ``complex number'' can be of any type. The only sensible ones are
integers
(we are then in $\Bbb Z[i]$), rational numbers ($\Bbb Q[i]$), real numbers
($\Bbb R[i]=\Bbb C$), or even elements of $\Bbb Z/n\Bbb Z$
($(\Bbb Z/n\Bbb Z)[i]$ when this makes sense), or $p$-adic numbers when
$p\equiv 3 \mod 4$ ($\Bbb Q_{p}[i]$).

This feature must of course not be used too rashly: for example you
are in principle allowed to create objects which are ``complex numbers of
complex numbers'', but don't expect PARI to make sensible use of such
objects: you will mainly get nonsense.

On the other hand, one thing which {\sl is\/} allowed is to have components
of different, but compatible, types. For example, taking again complex
numbers, the real part could be of type integer, and the imaginary part
of type rational.

By compatible, we mean types which can be freely mixed in operations like
$+$ or $*$. For example if the real part is of type real, the imaginary
part cannot be of type integermod (integers modulo a given number $n$).

Let us now describe the types. As explained above, they are built
recursively from basic types which are as follows. We use the letter $T$
to designate any type; the type number corresponds to the internal
representation of the type.\medskip
\settabs
\+xxx&typexxxxxx&xxxxxxxxxxxxxxxxxxx&xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxx\cr
\+&type 1:& $\Bbb Z$& \ref{Integer}s (with arbitrary precision)\cr
\+&type 2:& $\Bbb R$& \ref{Real number}s (with arbitrary precision)\cr
\+&type 3:& $\Bbb Z/n\Bbb Z$& \ref{Integermod}s (integers modulo $n$)\cr
\+&type 4:& $\Bbb Q$& \ref{Rational number}s (in irreducible form)\cr
\+&type 5:& $\Bbb Q$& Rational numbers (in non necessarily irreducible form)\cr
\+&type 6:& $T[i]$& \ref{Complex number}s \cr
\+&type 7:& $\Bbb Q_p$&  $p$-adic\sref{p-adic number} numbers\cr
\+&type 8:& $T[w]$& \ref{Quadratic number}s (where $[\Bbb Z[w]:\Bbb Z]=2$)\cr
\+&type 9:& $T[X]/P(X)T[X]$& \ref{Polymod}s (polynomials modulo $P$)\cr
\+&type 10:& $T[X]$& \ref{Polynomial}s\cr
\+&type 11:& $T((X))$& \ref{Power series} (finite Laurent series)\cr
\+&type 13:& $T(X)$& \ref{Rational function}s (in irreducible form)\cr
\+&type 14:& $T(X)$& Rational functions (in non necessarily irreducible 
form)\cr
\+&type 17:& $T^n$& Row (i.e. horizontal) \sref{Row vector}vectors\cr
\+&type 18:& $T^n$& Column (i.e. vertical) \sref{Column vector}vectors\cr
\+&type 19:& ${\curl M}_{m,n}(T)$& Matrices.\sref{Matrix}\cr

In addition, there exist type 15 for binary quadratic forms of positive
discriminant, type 16 for binary quadratic forms of negative discriminant
\sref{Binary quadratic form}
which can be used in specific operations, but which may disappear in future
versions, hence their use is not documented in this manual.

Let us look closely at these types.

\subsec{Integers and reals}:\sref{Integer}\sref{Real number}
they are of arbitrary and varying length
(each number having coded
internally its own length or precision) with the following mild restrictions:
integers must be in absolute value less than $2^{1048480}$ (i.e. roughly
315623 digits).
The precision of real numbers is also at most 315623 significant decimal
digits, and the
binary exponent must be in absolute value less than $2^{23}=8388608$.

Note that PARI has been optimized so that it works as fast as possible on
numbers with
40 to 100 decimal digits. In particular, no fancy multiplication technique is
used.
Hence, although it is possible to use PARI to do computations with 300000
decimal digits, much better programs can be written for these loooong numbers.

Integers and real numbers are completely non recursive types and are sometimes
called the {\bf \ref{leaves}}.

\subsec{Integermods, rational numbers (irreducible or not),
$p$-adic numbers, polymods, and
rational functions}:\sref{Integermod}\sref{Rational number}\sref{p-adic number}
\sref{Polymod} they are recursive, but in a forced manner:

For integermods or polymods, there are two components: the modulus, which
must be of type integer (resp. polynomial), and the number (resp. polynomial).

For rational numbers or rational functions, there are also only two
components: the numerator
and the denominator, which must both be of type integer (resp. polynomial).

Finally, $p$-adic numbers have three components: the prime $p$, the
``modulus'' $p^k$,
and an approximation to the $p$-adic number. Here $\Bbb Z_p$ is considered as
$\varprojlim \Bbb Z/p^k\Bbb Z$, and $\Bbb Q_p$ as its field of fractions.
Like real numbers, the codewords contain also the information on the
precision
of the number (which is in fact redundant with $p^k$, but it is apparently more
efficient to keep this redundancy).

\subsec{Complex numbers ($a+bi$) and quadratic numbers}: \sref{Complex number}
\sref{Quadratic number}quadratic numbers are numbers of the form $a+bw$,
where $w$ is such that $[\Bbb Z[w]:\Bbb Z]=2$, and more precisely $w=\sqrt
d/2$ when
$d\equiv 0 \mod 4$, and $w=(1+\sqrt d)/2$ when $d\equiv 1 \mod 4$, where $d$
is
the discriminant of a quadratic order.

 Complex and quadratic numbers are partially recursive: the two components
$a$ and $b$ can be of type integer, real, rational, integermod or $p$-adic,
and can
be mixed, subject to the limitations mentioned above. For example,
$a+bi$ with $a$ and $b$ $p$-adic is in $\Bbb Q_p[i]$, but this is equal to
$\Bbb Q_p$
when $p\equiv 1 \mod 4$, hence we must exclude these $p$ when one explicitly
uses
a complex $p$-adic type.

\subsec{Polynomials, power series, vectors and matrices}: 
\sref{Polynomial}\sref{Power series}\sref{Vector}\sref{Matrix}
they are completely recursive:
their components can be of any type, and types can be mixed
(however beware when doing operations). Note in particular that a polynomial
in two variables is simply a polynomial with polynomial coefficients.

Note that in the present version \vers{} of PARI, there is a bug in the handling
of power series of power series (i.e. power series in several variables).
However power series of polynomials (which are power series in several
variables of a special type) are OK. The reason for this bug is known,
but it is difficult to correct because the mathematical problem itself
contains some amount of imprecision.

\subsec{Exact and imprecise objects}: \sref{imprecise object}we have already
said that integers and reals are called the \ref{leaves} because they are
ultimately
at the end of every branch of a tree representing a PARI object. Another
important notion is that of an {\bf \ref{exact object}}: by definition,
numbers of basic type real, $p$-adic or power series are imprecise, and we
will
say that a PARI object having one of these imprecise types anywhere in its
tree
is not exact. All other PARI objects will be called exact. This is a very
important notion since no numerical analysis is involved when dealing with
exact objects.

\subsec{What is \ref{zero}?}: this is a crucial question in all computer
systems. The answer we give in PARI is the following. For exact types,
all zeros are equivalent and are exact, so are usually represented as
an integer zero. The problem becomes
nontrivial for imprecise types. For $p$-adics the answer is as
follows: every $p$-adic number (including 0) has an exponent $e$ and a
``mantissa'' $u$ which is a $p$-adic unit, except when the number is zero (in
which case $u$ is zero), the mantissa having a certain ``precision'' $k$ (i.e.
is defined modulo $p^k$). Then this $p$-adic zero is understood to be
equal to $O(p^e)$, i.e. there is an infinite number of zeros. The number $k$
is thus irrelevant.

For power series the situation is similar, with $p$ replaced
by $X$, i.e. a power series zero will be $O(X^e)$, the number $k$ (here the
length of the power series) being also irrelevant.

For real numbers, the precision $k$ is also irrelevant,
and a real zero will in fact be $O(2^e)$ where $e$ is now usually a
negative binary exponent. This of course will be printed as usual for
a real number ($0.0000\cdots$ in {\tt f} format or $0.Exx$ in {\tt e} format)
and not with a $O()$ symbol as with $p$-adics or power series.

\subsec{Scalar types}:\sref{scalar type} basic types with type number less than or equal
to 9 will be called scalar types because they essentially occur as
coefficients of some more complicated object. Note that type 9, i.e. polymod,
is used to define algebraic extensions of a base ring, and as such is
a scalar type.

\section{Operations and functions.}

\subsec{The PARI philosophy}.
The basic philosophy which governs PARI is that operations and functions
should first give as exact a result as possible, and second, be permitted
if they make any kind of sense.

More specifically, if you do an operation (not a transcendental one)
between exact objects, you will get an exact object. For example,
dividing 1 by 3 does not give $0.33333\cdots$ as you could expect,
but simply the rational number $(1/3)$. If you really want the result
in type real, evaluate $1./3$ or add $0.$ to $(1/3)$.

The result of operations between imprecise objects will be as precise
as possible. Consider for example one of the most difficult cases, that is
the addition of two real numbers $x$ and $y$. The \ref{accuracy} of the result is
{\it a priori\/} unpredictable; it depends on the precisions of $x$ and $y$, on
their sizes (i.e. their exponents), and also on the size of $x+y$. PARI
works out automatically the right precision for the result, even when it
is working in calculator mode GP where there is a \ref{default precision}.
See the technical reference manual for the precise formulas giving the
precision of the result.

The second part of the PARI philosophy is that PARI operations are in
general quite permissive. For instance taking the exponential of a vector
should not make sense. However, it is frequent that a computation comes
out with a result which is a vector with many components, and one wants
to get the exponential of each one. This could easily be done
either under GP or in library mode, but in fact PARI assumes
that this is exactly what you want to do when you take the exponential of a
vector, so no work is necessary. Most transcendental functions work in the
same way (see chapter 3 for details).

An ambiguity would arise with square matrices. PARI always considers
that you want to do componentwise function evaluation, hence to get
for example the exponential of a square matrix you would need to use
a function with a different name, {\tt matexp} for instance. In the present
version \vers, this is not yet implemented. See however the program in
Appendix C, which is a first attempt for this particular function.

The available operations and functions in PARI are described in detail
in chapter 3. Here is a brief summary:

\subsec{Standard operations}.

The four standard operators $+$, $-$, $*$, $/$ of course exist. It should
be once more emphasized that division is, as far as it can, an exact
operation ($4$ divided by $3$ gives $(4/3)$). In addition to this, operations
on integers or polynomials, like $\backslash $ (Euclidean division),
$\%$ (Euclidean remainder) exist. There is also the exponentiation
operator $\hat{\ }$, when the exponent is of type integer
(otherwise it is considered as a transcendental function).
Finally, the logical operators $\&\&$ ({\tt and} operator), $|\,|$ ({\tt or}
operator) exist, giving as results 1 (true) or 0 (false). Note that the
C-syntax $\&$ and $|$ is also accepted as a synonym. However, there is
no bitwise {\tt and} or {\tt or}.

\subsec{Conversions and similar functions}.

Many conversion functions are available to convert between different
types. For example floor, ceiling, rounding, truncation, etc\dots.
Other simple functions are included like real and imaginary part,
conjugation,
norm, absolute value, changing precision or creating an integermod or a
polymod.

\subsec{Transcendental functions}.

They usually operate on any object in $\Bbb C$, and some also on $p$-adics.
The list is everexpanding and of course contains all the elementary
functions, plus already a number of others. Recall that by extension,
PARI usually allows a transcendental function to operate componentwise
on vectors or matrices.

\subsec{Arithmetic functions}.

Apart from a few like the factorial function or the Fibonacci
numbers, these are functions which explicitly use the prime factor
decomposition of integers. The standard functions are included.
In the present version \vers, a primitive, but useful version of Lenstra's
Elliptic Curve Method (ECM) has been implemented.
More sophisticated functions are implemented, like finding integral bases
and discriminants of number fields, computing class numbers and regulators
(for quadratic fields only), and also many functions dealing with
elliptic curves over $\Bbb Q$ or over local fields.

\subsec{Other functions}.

Quite a number of other functions dealing with polynomials (e.g. finding
complex or $p$-adic roots, factoring,\dots), power series
(e.g. substitution, reversion),
linear algebra (e.g. determinant, characteristic polynomial, linear
systems), and different kinds of recursions are also included. In addition,
standard numerical analysis routines like Romberg integration (open or closed,
on a finite or infinite interval), real root finding when the root is bracketed,
polynomial interpolation, series acceleration, and plotting are included.
See the last sections of chapter 3 for details.

\vfill\eject