p
-adic numbers, polmods, and rational
libPARI - Overview of the PARI system
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:
1) as a library libpari
, which can be called from an upper-level
language application, for instance written in ANSI C or C++
;
2) as a sophisticated programmable calculator, named gp
, whose
language GP
contains most of the control instructions of a standard
language like C;
3) the compiler gp2c
translates GP code to C, and loads it into
the gp
interpreter. A typical script compiled by 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 libpari
programming.
The present Chapter 1 gives an overview of the PARI/GP system; gp2c
is
distributed separately and comes with its own manual. Chapter 2 describes the
GP
programming language and the 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: User's
Guide to the PARI library (libpari.dvi
.
A tutorial for gp
is provided in the standard distribution: A
tutorial for PARI/GP (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 gp
reference card (refcard.dvi
or refcard.ps
). In case of need, you
can refer to the complete function description in Chapter 3.
Everything can be found on PARI's home page:
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.
Bugs are submitted online to our Bug Tracking System, available from PARI's home page, or directly from the URL
http://pari.math.u-bordeaux.fr/Bugs/
.
Further instructions can be found on that page.
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 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
@3* the whole ix86 family (Intel, AMD, Cyrix) starting at the 386, up to the Xbox gaming console, including the Opteron 64 bit processor.
@3* 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;
@3* the DEC Alpha 64-bit processor;
@3* the Intel Itanium 64-bit processor;
@3* the PowerPC equipping old macintoshs (G3, G4, etc.);
@3* 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 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!
@3The 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 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 t_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 = 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
gp
.) But do not expect PARI to make sensible use of such objects: you
will mainly get nonsense.
On the other hand, it is allowed to have components of different, but
compatible, types, which can be freely mixed in basic ring operations +
or
x
. 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 t_xxx
correspond to the internal representations
of the types.
type t_INT
Z Integers (with arbitrary
precision)
type t_REAL
R Real numbers (with arbitrary precision)
type t_INTMOD
Z/n
Z Intmods (integers modulo
n
)\varsidx{intmod}
type t_FRAC
Q Rational numbers (in irreducible
form)
type t_FFELT
F_q
Finite field element
type t_COMPLEX
T[i]
Complex numbers
type t_PADIC
Q_p
p
-adic numbers
type t_QUAD
Q[w]
Quadratic Numbers (where
[
Z[w]:
Z] = 2
)
type t_POLMOD
T[X]/(P)
Polmods (polynomials modulo
P\in T[X]
)\varsidx{polmod}
type t_POL
T[X]
Polynomials
type t_SER
T((X))
Power series (finite Laurent
series)
type t_RFRAC
T(X)
Rational functions (in irreducible
form)
type t_VEC
T^n
Row (i.e. horizontal) vectors
type t_COL
T^n
Column (i.e. vertical) vectors
type t_MAT
M_{m,n}(T)
Matrices
type t_LIST
T^n
Lists
type t_STR
Character strings
type t_CLOSURE
Functions
type t_ERROR
Error messages
type t_INFINITY
- oo
and + oo
@3and where the types T
in recursive types can be different in each
component. The first nine basic types, from t_INT
to
t_POLMOD
, are called scalar types because they essentially occur as
coefficients of other more complicated objects. Type t_POLMOD
is used to
define algebraic extensions of a base ring, and as such is a scalar type.
In addition, there exist types t_QFR
and t_QFI
for integral
binary quadratic forms, and the internal type t_VECSMALL
. The latter
holds vectors of small integers, 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 GEN
in the sequel) belongs to one of these
basic types. Let us have a closer look.
They are of
arbitrary and varying length (each number carrying in its internal
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 non-recursive types.
p
-adic numbers, polmods, and rational
functionsThese are recursive, but in a restricted way.
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).
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.
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
.
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 = 0 mod 4
, and w = (1+
sqrt d)/2
when d = 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 t_INT
, t_REAL
, t_INTMOD
, t_FRAC
, or
t_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 = 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 t_REAL
is not
allowed.
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.
In the present version 2.9.3 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.
These contain objects just as they would be printed by the
gp
calculator.
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 zero. The problem becomes non-trivial 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.
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...
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.
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 t_REAL
, t_PADIC
or t_SER
are
imprecise. A PARI object having one of these imprecise types anywhere in
its tree is inexact, and 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...
, but the rational number
(1/3)
. To get the result as a floating point real number, evaluate
1./3
or 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 accuracy of the result is
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
gp
, where there is a notion of 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:
? 0.E-28 + 1.E-100 %1 = 0.E-28 ? 0.E100 + 1 %2 = 0.E100
@3As an exercise, if a = 2^(-100)
, why do a + 0.
and
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 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 wayFOOTNOTE<<< 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:
? 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)
The first example is straightforward: since 3
is invertible mod 5
, (1/3)
is easily mapped to Z/5
Z. In the second example, 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.
The available operations and functions in PARI are described in detail in Chapter 3. Here is a brief summary:
Of course, the four standard operators +
, -
, *
, /
exist. We emphasize once more that division is, as far as possible,
an exact operation: 4
divided by 3
gives (4/3)
. In addition to
this, operations on integers or polynomials, like \
(Euclidean
division), %
(Euclidean remainder) exist; for integers, {\/
}
computes the quotient such that the remainder has smallest possible absolute
value. There is also the exponentiation operator ^
, when the
exponent is of type integer; otherwise, it is considered as a transcendental
function. Finally, the logical operators !
(not
prefix operator),
&&
(and
operator), ||
(or
operator) exist, giving
as results 1
(true) or 0
(false).
Many conversion functions are available to convert between different types. For example floor, ceiling, rounding, truncation, etc.... Other simple functions are included like real and imaginary part, conjugation, norm, absolute value, changing precision or creating an intmod or a polmod.
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...). Recall that by
extension, PARI usually allows a transcendental function to operate
componentwise on vectors or matrices.
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.
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.
And now, you should really have a look at the tutorial before proceeding. \newpage