usersch1.tex

% Copyright (c) 2000  The PARI Group
%
% This file is part of the PARI/GP documentation
%
% Permission is granted to copy, distribute and/or modify this document
% under the terms of the GNU General Public License
\chapter{Overview of the PARI system}

\section{Introduction}

\noindent
PARI/GP is a specialized computer algebra system, primarily aimed at number
theorists, but has been put to good use in many other different fields, from
topology or numerical analysis to physics.

Although quite an amount of symbolic manipulation is possible, PARI does
badly compared to systems like Axiom, Magma, Maple, Mathematica, Maxima, or
Reduce on such tasks, e.g.~multivariate polynomials, formal integration,
etc. On the other hand, the three main advantages of the system are its
speed, the possibility of using directly data types which are familiar to
mathematicians, and its extensive algebraic number theory module (from
the above-mentioned systems, only Magma provides similar features).

Non-mathematical strong points include the possibility to program either
in high-level scripting languages or with the PARI library, a mature system
(development started in the mid eighties) that was used to conduct and
disseminate original mathematical research, while building a large user
community, linked by helpful mailing lists and a tradition of great user
support from the developers. And, of course, PARI/GP is Free Software,
covered by the GNU General Public License, either version 2 of the License or
(at your option) any later version.

PARI is used in three different ways:

\quad 1) as a library \tet{libpari}, which can be called from an upper-level
language application, for instance written in ANSI C or C$++$;

\quad 2) as a sophisticated programmable calculator, named \tet{gp}, whose
language \tet{GP} contains most of the control instructions of a standard
language like C;

\quad 3) the compiler \tet{gp2c} translates GP code to C, and loads it into
the \kbd{gp} interpreter. A typical script compiled by \kbd{gp2c} runs 3 to 10
times faster. The generated C code can be edited and optimized by hand. It
may also be used as a tutorial to \kbd{libpari} programming.

The present Chapter 1 gives an overview of the PARI/GP system; \kbd{gp2c} is
distributed separately and comes with its own manual. Chapter 2 describes the
\kbd{GP} programming language and the \kbd{gp} calculator. Chapter 3
describes all routines available in the calculator. Programming in library
mode is explained in Chapters 4 and 5 in a separate booklet: \emph{User's
Guide to the PARI library} (\kbd{libpari.dvi}.

A tutorial for \kbd{gp} is provided in the standard distribution: \emph{A
tutorial for PARI/GP} (\kbd{tutorial.dvi}) and you should read this first.
You can then start over and read the more boring stuff which lies ahead. You
can have a quick idea of what is available by looking at the \kbd{gp}
reference card (\kbd{refcard.dvi} or \kbd{refcard.ps}). In case of need, you
can refer to the complete function description in Chapter 3.

\subsectitle{How to get the latest version} Everything can be found on
PARI's home page:
$$\url{http://pari.math.u-bordeaux.fr/}.$$
%
From that point you may access all sources, some binaries,
version information, the complete mailing list archives, frequently asked
questions and various tips. All threaded and fully searchable.

\subsectitle{How to report bugs} Bugs are submitted online to our Bug
Tracking System, available from PARI's home page, or directly from the URL
$$\url{http://pari.math.u-bordeaux.fr/Bugs/}.$$
%
Further instructions can be found on that page.

\section{Multiprecision kernels / Portability}

The PARI multiprecision kernel comes in three non exclusive flavors. See
Appendix~A for how to set up these on your system; various compilers are
supported, but the GNU \kbd{gcc} compiler is the definite favorite.

A first version is written entirely in ANSI C, with a C++-compatible syntax,
and should be portable without trouble to any 32 or 64-bit computer having no
drastic memory constraints. We do not know any example of a computer where a
port was attempted and failed.

In a second version, time-critical parts of the kernel are written in
inlined assembler. At present this includes

\item the whole ix86 family (Intel, AMD, Cyrix) starting at the 386, up to
the Xbox gaming console, including the Opteron 64 bit processor.

\item three versions for the Sparc architecture: version 7, version 8 with
SuperSparc processors, and version 8 with MicroSparc I or II processors.
UltraSparcs use the MicroSparc II version;

\item the DEC Alpha 64-bit processor;

\item the Intel Itanium 64-bit processor;

\item the PowerPC equipping old macintoshs (G3, G4, etc.);

\item the HPPA processors (both 32 and 64 bit);

A third version uses the GNU MP library to implement most of its
multiprecision kernel. It improves significantly on the native one for large
operands, say 100 decimal digits of accuracy or more. You \emph{should}
enable it if GMP is present on your system. Parts of the first version are
still in use within the GMP kernel, but are scheduled to disappear.

A historical version of the PARI/GP kernel, written in 1985, was specific to
680x0 based computers, and was entirely written in MC68020 assembly language.
It ran on SUN-3/xx, Sony News, NeXT cubes and on 680x0 based Macs. It is no
longer part of the PARI distribution; to run PARI with a 68k assembler
micro-kernel, use the GMP kernel!

\section{The PARI types} \label{se:start}

\noindent The GP language is not typed in the traditional sense; in
particular, variables have no type. In library mode, the type of all PARI
objects is \kbd{GEN}, a generic type. On the other hand, it is dynamically
typed: each object has a specific internal type, depending on the
mathematical object it represents.

The crucial word is recursiveness: most of the PARI types are recursive. For
example, the basic internal type \typ{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
$\Z[i]$), rational numbers ($\Q[i]$), real numbers ($\R[i]=\C$), or even
elements of $\Z/n\Z$ (in $(\Z/n\Z)[t]/(t^2+1)$), or $p$-adic numbers when
$p\equiv 3 \mod 4$ ($\Q_{p}[i]$). This feature must not be used too rashly in
library mode: for example you are in principle allowed to create objects
which are ``complex numbers of complex numbers''. (This is not possible under
\kbd{gp}.) But do not expect PARI to make sensible use of such objects: you
will mainly get nonsense.

On the other hand, it \emph{is} allowed to have components of different, but
compatible, types, which can be freely mixed in basic ring operations $+$ or
$\times$. For example, taking again complex numbers, the real part could be
an integer, and the imaginary part a rational number. On the other hand, if
the real part is a real number, the imaginary part cannot be an integer
modulo $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 symbolic names \typ{xxx} correspond to the internal representations
of the types.\medskip
\settabs\+xxxxxx&typexxxxxxxxxxxxx&xxxxxxxxxxxxx&xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx\cr
%
\+&type \tet{t_INT}& $\Z$& Integers (with arbitrary
precision)\sidx{integer}\cr
%
\+&type \tet{t_REAL}& $\R$& Real numbers (with arbitrary precision)\sidx{real
number}\cr
%
\+&type \tet{t_INTMOD}& $\Z/n\Z$& Intmods (integers modulo
$n$)\varsidx{intmod}\cr
%
\+&type \tet{t_FRAC}& $\Q$& Rational numbers (in irreducible
form)\sidx{rational number}\cr
%
\+&type \tet{t_FFELT}& $\F_q$& Finite field element\sidx{finite field
element}\cr
%
%
\+&type \tet{t_COMPLEX}& $T[i]$& Complex numbers\sidx{complex number}\cr
%
\+&type \tet{t_PADIC}& $\Q_p$& $p$-adic\sidx{p-adic number} numbers\cr
%
\+&type \tet{t_QUAD}& $\Q[w]$& Quadratic Numbers (where
$[\Z[w]:\Z]=2$)\sidx{quadratic number}\cr
%
\+&type \tet{t_POLMOD}& $T[X]/(P)$& Polmods (polynomials modulo
$P\in T[X]$)\varsidx{polmod}\cr
%
\+&type \tet{t_POL}& $T[X]$& Polynomials \sidx{polynomial}\cr
%
\+&type \tet{t_SER}& $T((X))$& Power series (finite Laurent
series)\sidx{power series}\cr
%
\+&type \tet{t_RFRAC}& $T(X)$& Rational functions (in irreducible
form)\sidx{rational function}\cr
%
\+&type \tet{t_VEC}& $T^n$& Row (i.e.~horizontal) vectors\sidx{row vector}\cr
%
\+&type \tet{t_COL}& $T^n$& Column (i.e.~vertical) vectors\sidx{column
vector}\cr
%
\+&type \tet{t_MAT}& ${\cal M}_{m,n}(T)$& Matrices\sidx{matrix}\cr
%
\+&type \tet{t_LIST}& $T^n$& Lists\sidx{list}\cr
%
\+&type \tet{t_STR}&    & Character strings\sidx{string}\cr
%
\+&type \tet{t_CLOSURE}&    & Functions\cr
%
\+&type \tet{t_ERROR}&    & Error messages\cr
%
\+&type \tet{t_INFINITY}&    & $-\infty$ and $+\infty$\cr

\noindent and where the types $T$ in recursive types can be different in each
component. \sidx{scalar type} The first nine basic types, from \typ{INT} to
\typ{POLMOD}, are called scalar types because they essentially occur as
coefficients of other more complicated objects. Type \typ{POLMOD} is used to
define algebraic extensions of a base ring, and as such is a scalar type.

In addition, there exist the type \tet{t_QFB} for integral
binary quadratic forms, and the internal type \tet{t_VECSMALL}. The latter
holds vectors of small integers\sidx{vecsmall}, whose absolute value is
bounded by $2^{31}$ (resp.~$2^{63}$) on 32-bit, resp.~64-bit, machines. They
are used internally to represent permutations, polynomials or matrices over a
small finite field, etc.

Every PARI object (called \tet{GEN} in the sequel) belongs to one of these
basic types. Let us have a closer look.

\subsec{Integers and reals} They are of
arbitrary and varying length (each number carrying in its internal
\sidx{integer}\sidx{real number}
representation its own length or precision) with the following mild
restrictions (given for 32-bit machines, the restrictions for 64-bit machines
being so weak as to be considered nonexistent): integers must be in absolute
value less than $2^{536870815}$ (i.e.~roughly 161614219 decimal digits). The
precision of real numbers is also at most 161614219 significant decimal
digits, and the binary exponent must be in absolute value less than
$2^{29}$, resp. $2^{61}$, on 32-bit, resp.~64-bit machines.

Integers and real numbers are nonrecursive types.

\subsec{Intmods, rational numbers, $p$-adic numbers, polmods, and rational
functions} These are recursive, but in a restricted way.
\sidx{intmod}\sidx{rational number}\sidx{p-adic number}\sidx{polmod}

For intmods or polmods, there are two components: the modulus, which must
be of type integer (resp.\ polynomial), and the representative 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).

\def\limproj{{\displaystyle\lim_{\textstyle\longleftarrow}}}

Finally, $p$-adic numbers have three components: the prime $p$, the
``modulus'' $p^k$, and an approximation to the $p$-adic number. Here $\Z_p$
is considered as the projective limit $\limproj \Z/p^k\Z$ via its finite
quotients, and $\Q_p$ as its field of fractions. Like real numbers, the
codewords contain an exponent, giving the $p$-adic valuation of the number,
and also the information on the precision of the number, which is
redundant with $p^k$, but is included for the sake of efficiency.

\subsec{Finite field elements}\sidx{finite field element}
The exact internal format depends of the finite field size, but it includes
the field characteristic $p$, an irreducible polynomial $T\in\F_p[X]$
defining the finite field $\F_p[X]/(T)$ and the element expressed as
a polynomial in (the class of) $X$.

\subsec{Complex numbers and quadratic numbers}\sidx{complex
number}\sidx{quadratic number} Quadratic numbers are numbers of the form
$a+bw$, where $w$ is such that $[\Z[w]:\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 numbers
correspond to the important special case $w=\sqrt{-1}$.

Complex numbers are partially recursive: the two components $a$
and $b$ can be of type \typ{INT}, \typ{REAL}, \typ{INTMOD}, \typ{FRAC}, or
\typ{PADIC}, and can be mixed, subject to the limitations mentioned above.
For example, $a+bi$ with $a$ and $b$ $p$-adic is in $\Q_p[i]$, but this is
equal to $\Q_p$ when $p\equiv 1 \mod 4$, hence we must exclude these $p$ when
one explicitly uses a complex $p$-adic type. Quadratic numbers are more
restricted: their components may be as above, except that \typ{REAL} is not
allowed.

\subsec{Polynomials, power series, vectors, matrices}
\sidx{polynomial}\sidx{power series}\sidx{vector}\sidx{matrix}
They are completely recursive, over a commutative base ring: 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. Polynomials or matrices over
noncommutative rings are not supported.

In the present version \vers{} of PARI, it is not possible to handle
conveniently 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. This is a difficult design
problem: the mathematical problem itself contains some amount of imprecision,
and it is not easy to design an intuitive generic interface for such beasts.

\subsec{Strings} These contain objects just as they would be printed by the
\kbd{gp} calculator.

\subsec{Zero} What is 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, and thus are usually represented as an
integer \idx{zero}. The problem becomes nontrivial for imprecise types:
there are infinitely many distinct zeros of each of these types! For
$p$-adics and power series the answer is as follows: every such object,
including 0, has an exponent $e$. This $p$-adic or $X$-adic zero is
understood to be equal to $O(p^e)$ or $O(X^e)$ respectively.
\label{se:whatzero}

Real numbers also have exponents and a real zero is in fact $O(2^e)$ where
$e$ is now usually a negative binary exponent. This of course is printed as
usual for a floating point number ($0.00\cdots$ or $0.Exx$ depending on the
output format) and not with a $O$ symbol as with $p$-adics or power series.
With respect to the natural ordering on the reals we make the following
convention: whatever its exponent a real zero is smaller than any positive
number, and any two real zeroes are equal.

\section{The PARI philosophy}
The basic principles which govern PARI is that operations and functions
should, firstly, give as exact a result as possible, and secondly, be
permitted if they make any kind of sense.

In this respect, we make an important distinction between exact and inexact
objects: by definition, types \typ{REAL}, \typ{PADIC} or \typ{SER} are
imprecise. A PARI object having one of these imprecise types anywhere in
its tree is \emph{inexact}, and \emph{exact} otherwise. No loss of accuracy
(rounding error) is involved when dealing with exact objects. Specifically,
an exact operation between exact objects will yield an exact object. For
example, dividing 1 by 3 does not give $0.333\cdots$, but the rational number
$(1/3)$. To get the result as a floating point real number, evaluate
\kbd{1./3} or \kbd{0.+1/3}.

Conversely, the result of operations between imprecise objects, although
inexact by nature, will be as precise as possible. Consider for example the
addition of two real numbers $x$ and $y$. The \idx{accuracy} of the result is
\emph{a priori} unpredictable; it depends on the precisions of $x$ and $y$,
on their sizes, and also on the size of $x+y$. From this data, PARI works out
the right precision for the result. Even if it is working in calculator mode
\kbd{gp}, where there is a notion of \idx{default precision}, its value is
only used to convert exact types to inexact ones.

In particular, if an operation involves objects of different accuracies, some
digits will be disregarded by PARI. It is a common source of errors to
forget, for instance, that a real number is given as $r + 2^e \varepsilon$
where $r$ is a rational approximation, $e$ a binary exponent and
$\varepsilon$ is a nondescript real number less than 1 in absolute value.
Hence, any number less than $2^e$ may be treated as an exact zero:
\bprog
? 0.E-28 + 1.E-100
%1 = 0.E-28
? 0.E100 + 1
%2 = 0.E100
@eprog
\noindent As an exercise, if \kbd{a = 2\pow (-100)}, why do \kbd{a + 0.} and
\kbd{a * 1.} differ?

The second principle is that PARI operations are in general quite permissive.
For instance taking the exponential of a vector should not make sense.
However, it frequently happens that one wants to apply a given function
to all elements in a vector. This is easily done using a loop,
or using the \tet{apply} built-in function, but in fact PARI assumes that
this is exactly what you want to do when you apply a scalar function to a
vector. Taking the exponential of a vector will do just that, so no work is
necessary. Most transcendental functions work in the same way\footnote{*}{An
ambiguity arises with square matrices. PARI always considers that you want to
do componentwise function evaluation in this context, hence to get for
example the standard exponential of a square matrix you would need to
implement a different function.}.

In the same spirit, when objects of different types are combined they
are first automatically mapped to a suitable ring, where the computation
becomes meaningful:
\bprog
    ? 1/3 + Mod(1,5)
    %1 = Mod(3, 5)
    ? I + O(5^9)
    %2 = 2 + 5 + 2*5^2 + 5^3 + 3*5^4 + 4*5^5 + 2*5^6 + 3*5^7 + O(5^9)
    ? Mod(1,15) + Mod(1,10)
    %3 = Mod(2, 5)
@eprog
The first example is straightforward: since $3$ is invertible mod $5$, $(1/3)$
is easily mapped to $\Z/5\Z$. In the second example, \kbd{I} stands for the
customary square root of $-1$; we obtain a $5$-adic number, $5$-adically
close to a square root of $-1$. The final example is more problematic, but
there are natural maps from $\Z/15\Z$ and $\Z/10\Z$ to $\Z/5\Z$, and the
computation takes place there.

\section{Operations and functions}

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

\subsec{Standard arithmetic operations}

\noindent
Of course, the four standard operators \kbd{+}, \kbd{-}, \kbd{*}, \kbd{/}
exist. We emphasize once more that division is, as far as possible,
an exact operation: $4$ divided by $3$ gives \kbd{(4/3)}. In addition to
this, operations on integers or polynomials, like \b{} (Euclidean
division), \kbd{\%} (Euclidean remainder) exist; for integers, {\b{/}}
computes the quotient such that the remainder has smallest possible absolute
value. There is also the exponentiation operator \kbd{\pow }, when the
exponent is of type integer; otherwise, it is considered as a transcendental
function. Finally, the logical operators \kbd{!} (\kbd{not} prefix operator),
\kbd{\&\&} (\kbd{and} operator), \kbd{||} (\kbd{or} operator) exist, giving
as results \kbd{1} (true) or \kbd{0} (false).

\subsec{Conversions and similar functions}

\noindent
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 intmod or a polmod.

\subsec{Transcendental functions}

\noindent
They usually operate on any complex number, power series, and some also on
$p$-adics. The list is ever-expanding and of course contains all the
elementary functions (exp/log, trigonometric functions), plus many others
(modular functions, Bessel functions, polylogarithms\dots). Recall that by
extension, PARI usually allows a transcendental function to operate
componentwise on vectors or matrices.

\subsec{Arithmetic functions}

\noindent
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. A number of factoring methods
are used by a rather sophisticated factoring engine (to name a few, Shanks's
SQUFOF, Pollard's rho, Lenstra's ECM, the MPQS quadratic sieve). These
routines output strong pseudoprimes, which may be certified by the APRCL
test.

There is also a large package to work with algebraic number fields. All the
usual operations on elements, ideals, prime ideals, etc.~are available.
More sophisticated functions are also implemented, like solving Thue
equations, finding integral bases and discriminants of number fields,
computing class groups and fundamental units, computing in relative number
field extensions, Galois and class field theory, and also many functions
dealing with elliptic curves over $\Q$ or over local fields.

\subsec{Other functions}

\noindent
Quite a number of other functions dealing with polynomials (e.g.~finding
complex or $p$-adic roots, factoring, etc), 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 univariate integration
(using the double exponential method), real root finding (when the root is
bracketed), polynomial interpolation, infinite series evaluation, and
plotting are included.
\medskip

And now, you should really have a look at the tutorial before proceeding.
\newpage