NAME

libPARI - Overview of the PARI system


DESCRIPTION


Introduction

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).

Important note

. 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.

How to get the latest version?

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.

How to report bugs?

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 types

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/nZ (in (Z/nZ)[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/nZ 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.

Integers and reals

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.

Intmods, rational numbers, p-adic numbers, polmods, and rational functions

these 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^kZ (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.

Complex numbers and quadratic numbers

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.

Polynomials, power series, vectors, matrices and lists

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.

Strings

These contain objects just as they would be printed by the gp calculator.

Notes

Exact and imprecise objects
we have already said that integers and reals are called the 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 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 an important notion since no numerical analysis is involved when dealing with exact objects.

Scalar types
the first nine basic types, from 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.

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. For p-adics the answer is as follows
every p-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.


Multiprecision kernels / Portability

(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 PARI philosophy

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.


Operations and functions

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

Standard arithmetic operations.

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).

Conversions and similar functions.

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.

Transcendental functions.

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.

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. 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.

Other functions.

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.