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 can be used by anybody whose primary need is speed.
Although quite an amount of symbolic manipulation is possible, PARI does badly compared to systems like Axiom, Macsyma, Maple, Mathematica 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 which has no equivalent in the above-mentioned systems.
PARI is used in three different ways:
1) as a library, 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 library 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 informations, 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 GP language is not typed in the traditional sense (it is
dynamically typed); in particular, variables have no type. In library mode,
the type of all PARI objects is GEN
, a generic type. On the other hand,
each object has a specific internal type, depending on the mathematical
object it represents.
The crucial word is recursiveness: most of the types PARI knows
about 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, one thing which 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 x
. For example if the real part is of type
real, the imaginary part cannot be of type intmod (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 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_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(X)T[X]
Polmods (polynomials modulo
P
)\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
{\cal M}_{m,n}(T)
Matrices
type t_LIST
T^n
Lists
type t_STR
Character strings
and where the types T
in recursive types can be different in each
component.
The internal type t_VECSMALL
, 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.
In addition, there exist types t_QFR
and t_QFI
for binary
quadratic forms of respectively positive and negative
discriminants, which can be used in specific
operations, but which may disappear in future versions.
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 inexistent): integers must be in absolute
value less than 2^{268435454}
(i.e. roughly 80807123 digits). The
precision of real numbers is also at most 80807123 significant decimal
digits, and the binary exponent must be in absolute value less than
2^{29}
.
Note that PARI has been optimized so that it works as fast as possible on
numbers with at most a few thousand decimal digits. In particular, the
native PARI kernel does not contain asymptotically fast DFT-based techniques
Hence, although it is possible to use PARI to do computations with 10^7
decimal digits, better programs can be written for such huge numbers. At the
very least the GMP kernel should be used at this point. (For reasons of
backward compatibility, we cannot enable GMP by default, but you probably
should enable it.)
Integers and real numbers are non-recursive types and are sometimes called
leaves
.
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.
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.3.5 of PARI, there are bugs 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. This bug is difficult to correct because 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.
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 an important notion since no numerical analysis is
involved when dealing with exact objects.
t_INT
to t_POLMOD
, will be called scalar types because they
essentially occur as coefficients of other more complicated objects. Note
that type t_POLMOD
is used to define algebraic extensions of a base ring,
and as such is a scalar type.
p
-adics the answer is as followsp
-adic number, including 0, has
an exponent e
and a ``mantissa'' (a purist would say a significand) u
which is a p
-adic unit, except when the number is zero (in which case u
is zero), the significand having a certain precision of k
``significant
words'' (i.e. being defined modulo p^k
). Then this p
-adic zero is
understood to be equal to O(p^e)
, i.e. there are infinitely many distinct
p
-adic 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 floating point number
(0.0000...
in f
format or 0.Exx
in e
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.
(You can skip this section if you are not interested in hardware technicalities.)
The PARI multiprecision kernel comes in three non exclusive flavours. See
Appendix A for how to set up these on your system; various compilers are
supported, but the GNU gcc
compiler is the definite favourite.
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
* the whole ix86 family (Intel, AMD, Cyrix) starting at the 386, up to the Xbox gaming console, including the Opteron 64 bit processor.
* 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;
* the DEC Alpha 64-bit processor;
* the Intel Itanium 64-bit processor;
* the PowerPC equipping modern macintoshs (G3, G4, etc.);
* 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.
An 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, one should now use the GMP kernel.
The basic principle which governs 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.
Specifically, an exact operation between exact objects will yield an exact
object. For example, dividing 1 by 3 does not give 0.33333...
, but
simply the rational number (1/3)
. To get the result as a floating point
real number, evaluate 1./3
or add 0.
to (1/3)
.
Conversely, the result of operations between imprecise objects 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, which is only used to
convert exact types to inexact ones.
In particular, this means that 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 valueFOOTNOTE<<< this is actually not quite true: internally, the
format is 2^b (a +
varepsilon)
, where a
and b
are integers >>>. 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
As 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 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, matexp
for instance. In the present version 2.3.5, this
is not implemented.
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. It should once more be emphasized 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 (and 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 everexpanding and of course contains all the
elementary functions, plus many others. 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, 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. See the last sections of Chapter 3 for details.
And now, you should really have a look at the tutorial before proceeding.