[BACK]Return to usersch1.tex CVS log [TXT][DIR] Up to [local] / OpenXM_contrib / pari / doc

Annotation of OpenXM_contrib/pari/doc/usersch1.tex, Revision 1.1

1.1     ! maekawa     1: \chapter{Overview of the PARI system}
        !             2:
        !             3: \section{Introduction}
        !             4:
        !             5: \noindent
        !             6: The PARI system is a package which is capable of doing formal computations
        !             7: on recursive types at high speed; it is primarily aimed at number
        !             8: theorists, but can be used by anybody whose primary need is speed.
        !             9:
        !            10: Although quite an amount of symbolic manipulation is possible in PARI, this
        !            11: system does very badly compared to much more sophisticated systems like
        !            12: Axiom, Macsyma, Maple, Mathematica or Reduce on such manipulations
        !            13: (e.g.~multivariate polynomials, formal integration, etc\dots). On the other
        !            14: hand, the three main advantages of the system are its speed (which can be
        !            15: between 5 and 100 times better on many computations), the possibility of
        !            16: using directly data types which are familiar to mathematicians, and its
        !            17: extensive algebraic number theory module which has no equivalent in the
        !            18: above-mentioned systems.
        !            19:
        !            20: It is possible to use PARI in two different ways:
        !            21:
        !            22: \quad 1) as a library, which can be called from an upper-level language
        !            23: application (for instance written in C, C$++$, Pascal or Fortran);
        !            24:
        !            25: \quad 2) as a sophisticated programmable calculator, named {\bf GP}, which
        !            26: contains most of the control instructions of a standard language like C.
        !            27:
        !            28: The use of GP is explained in chapters 2 and 3, and the programming in library
        !            29: mode is explained in chapters 3, 4 and 5. In the present Chapter 1, we give
        !            30: an overview of the system.
        !            31:
        !            32: \subsectitle{Important note:} A tutorial for GP is provided in the standard
        !            33: distribution (\kbd{tutorial.dvi}) and you should read this first (at
        !            34: least the beginning of it, you can skip the specialized topics you're not
        !            35: interested in). You can then start over and read the more boring stuff which
        !            36: lies ahead. But you should do that eventually, at the very least the various
        !            37: Chapter headings. You can have a quick idea of what is available by looking
        !            38: at the GP reference card (\kbd{refcard.dvi} or \kbd{refcard.ps}). In case
        !            39: of need, you can then refer to the complete function description in Chapter 3.
        !            40:
        !            41: \subsectitle{How to get the latest version?}
        !            42:
        !            43: \noindent
        !            44: This package can be obtained by anonymous ftp from quite a number of sites
        !            45: (ask \kbd{archie} or your favourite Web search engine for the site nearest to
        !            46: you). But, if you want the very latest version (including development
        !            47: versions), you should use the anonymous ftp address
        !            48:
        !            49: \kbd{ftp://megrez.math.u-bordeaux.fr/pub/pari}
        !            50:
        !            51: \noindent
        !            52: where you will find all the different ports and possibly some
        !            53: binaries. A lot of version information, mailing list archives, and various
        !            54: tips can be found on PARI's (fledgling) home page:
        !            55:
        !            56: \kbd{\wwwsite}
        !            57:
        !            58: \subsectitle{Implementation notes:} (You can skip this section and switch to
        !            59: \secref{se:start} if you're not interested in hardware technicalities. You
        !            60: won't miss anything that would be mentioned here.)
        !            61:
        !            62: Version \vers{} of the PARI package contains essentially three versions. The
        !            63: first one is a specific implementation for 680x0 based computers which
        !            64: contains a kernel (for the elementary arithmetic operations on multiprecise
        !            65: integers and real numbers, and binary/decimal conversion routines) entirely
        !            66: written in MC68020 assembly language (around 6000 lines), the rest being at
        !            67: present entirely written in ANSI C with a C++-compatible syntax. The system
        !            68: runs on SUN-3/xx, Sony News, NeXT cubes and on 680x0 based Macs with
        !            69: x$\ge$2. It should be very easy to port on any other 680x0 based machine
        !            70: like for instance the Apollo Domain workstations.
        !            71:
        !            72: Note that the assembly language source code uses the SUN syntax, which for
        !            73: some strange reason differs from the Motorola standard used by most other
        !            74: 680x0 machines in the world. In the Mac distribution, we have included a
        !            75: program which automatically converts from the SUN syntax into the standard
        !            76: one, at least for the needed PARI assembly file. On the Unix distribution,
        !            77: we have included other versions of the assembly file, using different
        !            78: syntaxes. {\bf This version is not really maintained anymore since we lack
        !            79: the hardware to update/test it.}
        !            80:
        !            81: The second version is a version where most of the kernel routines are written
        !            82: in C, but the time-critical parts are written in a few hundred lines
        !            83: of assembler at most. At present there exist three versions for the Sparc
        !            84: architecture: one for Sparc version 7 (e.g.~Sparcstation 1, 1+, IPC, IPX or 2),
        !            85: one for Sparc version 8 with supersparc processors (e.g.~Sparcstation 10
        !            86: and 20) and one for Sparc version 8 with microsparc I or II processors
        !            87: (e.g.~Sparcclassic or Sparcstation 4 and 5). No specific version is written
        !            88: for the Ultrasparc since it can use the microsparc II version. In addition,
        !            89: versions exist for the HP-PA architecture, for the PowerPC architecture
        !            90: (only for the 601), for the Intel family starting at the 386 (under Linux,
        !            91: OS/2, MSDOS, or Windows), and finally for the DEC Alpha 64-bit processors.
        !            92:
        !            93: Finally, a third version is written entirely in C, and should be portable
        !            94: without much trouble to any 32 or 64-bit computer having no real memory
        !            95: constraints. It is about 2 times slower than versions with a small assembly
        !            96: kernel. This version has been tested for example on MIPS based DECstations
        !            97: 3100 and 5000 and SGI computers.
        !            98:
        !            99: In addition to Unix workstations and Macs, PARI has been ported to a
        !           100: considerable number of smaller and larger machines, for example the VAX,
        !           101: 68000-based machines like the Atari, Mac Classic or Amiga 500, 68020 machines
        !           102: such as the Amiga 2500 or 3000, and even to MS-DOS 386 or better machines,
        !           103: using the \tet{EMX} port of the GNU C compiler and DOS-extender.
        !           104:
        !           105: \section{The PARI types}
        !           106: \label{se:start}\sidx{types}
        !           107:
        !           108: \noindent
        !           109: The crucial word in PARI is \idx{recursiveness}: most of the types it knows
        !           110: about are recursive. For example, the basic type {\bf Complex} exists (actually
        !           111: called \typ{COMPLEX}). However, the components (i.e.~the real and imaginary
        !           112: part) of such a ``complex number'' can be of any type. The only sensible ones
        !           113: are integers (we are then in $\Z[i]$), rational numbers ($\Q[i]$), real
        !           114: numbers ($\R[i]=\C$), or even elements of $\Z/n\Z$ ($(\Z/n\Z)[i]$ when this
        !           115: makes sense), or $p$-adic numbers when $p\equiv 3 \mod 4$ ($\Q_{p}[i]$).
        !           116:
        !           117: This feature must of course not be used too rashly: for example you are in
        !           118: principle allowed to create objects which are ``complex numbers of complex
        !           119: numbers'', but don't expect PARI to make sensible use of such objects: you
        !           120: will mainly get nonsense.
        !           121:
        !           122: On the other hand, one thing which {\it is\/} allowed is to have components
        !           123: of different, but compatible, types. For example, taking again complex
        !           124: numbers, the real part could be of type integer, and the imaginary part of
        !           125: type rational.
        !           126:
        !           127: By compatible, we mean types which can be freely mixed in operations like $+$
        !           128: or $\times$. For example if the real part is of type real, the imaginary part
        !           129: cannot be of type integermod (integers modulo a given number $n$).
        !           130:
        !           131: Let us now describe the types. As explained above, they are built recursively
        !           132: from basic types which are as follows. We use the letter $T$ to designate any
        !           133: type; the symbolic names correspond to the internal representations of the
        !           134: types.\medskip
        !           135: \settabs\+xxx&typexxxxxxxxxxxx&xxxxxxxxxxxxxxxx&xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx\cr
        !           136: %
        !           137: \+&type \typ{INT} \idxtyp{INT}:& $\Z$& Integers (with
        !           138: arbitrary precision)\sidx{integer}\cr
        !           139: %
        !           140: \+&type \typ{REAL}\idxtyp{REAL}:& $\R$& Real numbers
        !           141: (with arbitrary precision)\sidx{real number}\cr
        !           142: %
        !           143: \+&type \typ{INTMOD}\idxtyp{INTMOD}:& $\Z/n\Z$&
        !           144: Integermods (integers modulo $n$)\sidx{integermod}\cr
        !           145: %
        !           146: \+&type \typ{FRAC}\idxtyp{FRAC}:& $\Q$& Rational numbers
        !           147: (in irreducible form)\sidx{rational number}\cr
        !           148: %
        !           149: \+&type \typ{FRACN}\idxtyp{FRACN}:& $\Q$& Rational numbers
        !           150: (not necessarily in irreducible form)\cr
        !           151: %
        !           152: \+&type \typ{COMPLEX}\idxtyp{COMPLEX}:& $T[i]$& Complex
        !           153: numbers\sidx{complex number}\cr
        !           154: %
        !           155: \+&type \typ{PADIC}\idxtyp{PADIC}:& $\Q_p$&
        !           156: $p$-adic\sidx{p-adic number} numbers\cr
        !           157: %
        !           158: \+&type \typ{QUAD}\idxtyp{QUAD}:& $\Q[w]$& Quadratic Numbers
        !           159: (where $[\Z[w]:\Z]=2$)\sidx{quadratic number}\cr
        !           160: %
        !           161: \+&type \typ{POLMOD}\idxtyp{POLMOD}:& $T[X]/P(X)T[X]$&
        !           162: Polmods (polynomials modulo $P$)\sidx{polmod}\cr
        !           163: %
        !           164: \+&type \typ{POL}\idxtyp{POL}:& $T[X]$& Polynomials
        !           165: \sidx{polynomial}\cr
        !           166: %
        !           167: \+&type \typ{SER}\idxtyp{SER}:& $T((X))$& Power series
        !           168: (finite Laurent series)\sidx{power series}\cr
        !           169: %
        !           170: \+&type \typ{RFRAC}\idxtyp{RFRAC}:& $T(X)$& Rational
        !           171: functions (in irreducible form) \sidx{rational function}\cr
        !           172: %
        !           173: \+&type \typ{RFRACN}\idxtyp{RFRACN}:& $T(X)$& Rational functions
        !           174: (not necessarily in irreducible form)\cr
        !           175: %
        !           176: \+&type \typ{VEC}\idxtyp{VEC}:& $T^n$& Row (i.e.~horizontal)
        !           177: vectors\sidx{row vector}\cr
        !           178: %
        !           179: \+&type \typ{COL}\idxtyp{COL}:& $T^n$& Column (i.e.~vertical)
        !           180: vectors\sidx{column vector}\cr
        !           181: %
        !           182: \+&type \typ{MAT}\idxtyp{MAT}:& ${\cal M}_{m,n}(T)$&
        !           183: Matrices\sidx{matrix}\cr
        !           184: %
        !           185: \+&type \typ{LIST}\idxtyp{LIST}:& $T^n$&
        !           186: Lists\sidx{list}\cr
        !           187: %
        !           188: \+&type \typ{STR}\idxtyp{STR}:&     &
        !           189: Character strings\sidx{string}\cr
        !           190: \noindent
        !           191: and where the types $T$ in recursive types can be different in each component.
        !           192:
        !           193: In addition, there exist types \typ{QFR}\idxtyp{QFR} and \typ{QFI}
        !           194: \idxtyp{QFI} for binary quadratic forms of respectively positive and
        !           195: negative discriminants,\sidx{binary quadratic form} which can be used in
        !           196: specific operations, but which may disappear in future versions.
        !           197:
        !           198: \sidx{GEN} Every PARI object (called \kbd{GEN} in the sequel) belongs
        !           199: to one of these basic types. Let us have a closer look.
        !           200:
        !           201: \subsec{Integers and reals}:\sidx{integer}\sidx{real number}
        !           202: they are of arbitrary and varying length (each number carrying in its
        !           203: internal representation its own length or precision)
        !           204: with the following mild restrictions (given for
        !           205: 32-bit machines, the restrictions for 64-bit machines being so weak as to be
        !           206: considered inexistent): integers must be in absolute value less than
        !           207: $2^{268435456}$ (i.e.~roughly 80807124 digits).  The precision of real
        !           208: numbers is also at most 80807124 significant decimal digits, and the binary
        !           209: exponent must be in absolute value less than $2^{23}=8388608$.
        !           210:
        !           211: Note that PARI has been optimized so that it works as fast as possible on
        !           212: numbers with at most a few thousand decimal digits. In particular, not too
        !           213: much effort has been put into fancy multiplication techniques (only the
        !           214: Karatsuba algorithm is implemented). Hence, although it is possible to use
        !           215: PARI to do computations with 80000000 decimal digits, much better programs
        !           216: can be written for such huge numbers.
        !           217:
        !           218: Integers and real numbers are completely non-recursive types and are
        !           219: sometimes called the {\it\idx{leaves}}.
        !           220:
        !           221: \subsec{Integermods, rational numbers (irreducible or not),
        !           222: $p$-adic numbers, polmods, and
        !           223: rational functions}:\sidx{integermod}\sidx{rational number}\sidx{p-adic number}
        !           224: \sidx{polmod} these are recursive, but in a restricted way.
        !           225:
        !           226: For integermods or polmods, there are two components: the modulus, which
        !           227: must be of type integer (resp.\ polynomial), and the representative number
        !           228: (resp.\ polynomial).
        !           229:
        !           230: For rational numbers or rational functions, there are also only two
        !           231: components: the numerator and the denominator, which must both be of type
        !           232: integer (resp.\ polynomial).
        !           233:
        !           234: \def\limproj{{\displaystyle\lim_{\textstyle\longleftarrow}}}
        !           235:
        !           236: Finally, $p$-adic numbers have three components: the prime $p$, the
        !           237: ``modulus'' $p^k$, and an approximation to the $p$-adic number. Here $\Z_p$
        !           238: is considered as $\limproj \Z/p^k\Z$, and $\Q_p$ as its field of
        !           239: fractions.  Like real numbers, the codewords contain an exponent (giving
        !           240: essentially the $p$-adic valuation of the number) and also the information on
        !           241: the precision of the number (which is in fact redundant with $p^k$, but is
        !           242: included for the sake of efficiency).
        !           243:
        !           244: \subsec{Complex numbers and quadratic numbers}:
        !           245: \sidx{complex number}\sidx{quadratic number}
        !           246: quadratic numbers are numbers of the form $a+bw$, where $w$ is such that
        !           247: $[\Z[w]:\Z]=2$, and more precisely $w=\sqrt d/2$ when $d\equiv 0 \mod 4$,
        !           248: and $w=(1+\sqrt d)/2$ when $d\equiv 1 \mod 4$, where $d$ is the discriminant
        !           249: of a quadratic order. Complex numbers correspond to the very important
        !           250: special case $w=\sqrt{-1}$.\label{se:compquad}
        !           251:
        !           252: Complex and quadratic numbers are partially recursive: the two components
        !           253: $a$ and $b$ can be of type integer, real, rational, integermod or $p$-adic,
        !           254: and can be mixed, subject to the limitations mentioned above. For example,
        !           255: $a+bi$ with $a$ and $b$ $p$-adic is in $\Q_p[i]$, but this is equal to
        !           256: $\Q_p$ when $p\equiv 1 \mod 4$, hence we must exclude these $p$ when one
        !           257: explicitly uses a complex $p$-adic type.
        !           258:
        !           259: \subsec{Polynomials, power series, vectors, matrices and lists}:
        !           260: \sidx{polynomial}\sidx{power series}\sidx{vector}\sidx{matrix}
        !           261: they are completely recursive: their components can be of any type, and types
        !           262: can be mixed (however beware when doing operations). Note in particular that
        !           263: a polynomial in two variables is simply a polynomial with polynomial
        !           264: coefficients.
        !           265:
        !           266: Note that in the present version \vers{} of PARI, there is a bug in the
        !           267: handling of power series of power series (i.e.~power series in several
        !           268: variables).  However power series of polynomials (which are power series in
        !           269: several variables of a special type) are OK. The reason for this bug is
        !           270: known, but it is difficult to correct because the mathematical problem itself
        !           271: contains some amount of imprecision.
        !           272:
        !           273: \subsec{Strings}: These contain objects just as they would be printed by the
        !           274: GP calculator.
        !           275:
        !           276: \subsec{Notes}:
        !           277:
        !           278: \subsubsec{Exact and imprecise objects}: \sidx{imprecise object}we have
        !           279: already said that integers and reals are called the \idx{leaves} because they
        !           280: are ultimately at the end of every branch of a tree representing a PARI
        !           281: object. Another important notion is that of an {\bf \idx{exact object}}: by
        !           282: definition, numbers of basic type real, $p$-adic or power series are
        !           283: imprecise, and we will say that a PARI object having one of these imprecise
        !           284: types anywhere in its tree is not exact. All other PARI objects will be
        !           285: called exact. This is a very important notion since no numerical analysis is
        !           286: involved when dealing with exact objects.
        !           287:
        !           288: \subsubsec{Scalar types}:\sidx{scalar type} the first nine basic types, from
        !           289: \typ{INT} to \typ{POLMOD}, will be called scalar types because they
        !           290: essentially occur as coefficients of other more complicated objects. Note
        !           291: that type \typ{POLMOD} is used to define algebraic extensions of a base ring,
        !           292: and as such is a scalar type.
        !           293:
        !           294: \subsubsec{What is zero?} This is a crucial question in all computer
        !           295: systems. The answer we give in PARI is the following. For exact types, all
        !           296: zeros are equivalent and are exact, and thus are usually represented as an
        !           297: integer \idx{zero}. The problem becomes non-trivial for imprecise types. For
        !           298: $p$-adics the answer is as follows: every $p$-adic number (including 0) has
        !           299: an exponent $e$ and a ``mantissa'' (a purist would say a ``significand'') $u$
        !           300: which is a $p$-adic unit, except when the number is zero (in which case $u$
        !           301: is zero), the significand having a certain ``precision'' $k$ (i.e.~being
        !           302: defined modulo $p^k$). Then this $p$-adic zero is understood to be equal to
        !           303: $O(p^e)$, i.e.~there are infinitely many distinct $p$-adic zeros. The number
        !           304: $k$ is thus irrelevant.
        !           305:
        !           306: For power series the situation is similar, with $p$ replaced by $X$, i.e.~a
        !           307: power series zero will be $O(X^e)$, the number $k$ (here the length of the
        !           308: power series) being also irrelevant.\label{se:whatzero}
        !           309:
        !           310: For real numbers, the precision $k$ is also irrelevant, and a real zero will
        !           311: in fact be $O(2^e)$ where $e$ is now usually a negative binary exponent. This
        !           312: of course will be printed as usual for a real number ($0.0000\cdots$ in
        !           313: \kbd{f} format or $0.Exx$ in \kbd{e} format) and not with a $O()$ symbol as
        !           314: with $p$-adics or power series.
        !           315:
        !           316: \section{Operations and functions}
        !           317:
        !           318: \subsec{The PARI philosophy}.
        !           319: The basic philosophy which governs PARI is that operations and functions
        !           320: should, firstly, give as exact a result as possible, and secondly, be
        !           321: permitted if they make any kind of sense.
        !           322:
        !           323: More specifically, if you do an operation (not a transcendental one) between
        !           324: exact objects, you will get an exact object. For example, dividing 1 by 3
        !           325: does not give $0.33333\cdots$ as you might expect, but simply the rational
        !           326: number $(1/3)$. If you really want the result in type real, evaluate $1./3$
        !           327: or add $0.$ to $(1/3)$.
        !           328:
        !           329: The result of operations between imprecise objects will be as precise as
        !           330: possible. Consider for example one of the most difficult cases, that is the
        !           331: addition of two real numbers $x$ and $y$. The \idx{accuracy} of the result is
        !           332: {\it a priori\/} unpredictable; it depends on the precisions of $x$ and $y$,
        !           333: on their sizes (i.e.~their exponents), and also on the size of $x+y$. PARI
        !           334: works out automatically the right precision for the result, even when it is
        !           335: working in calculator mode GP where there is a \idx{default precision}.
        !           336:
        !           337: In particular, this means that if an operation involves objects of
        !           338: different accuracies, some digits will be disregarded by PARI. It is a
        !           339: common source of errors to forget, for instance, that a real number is
        !           340: given as $r + 2^e \varepsilon$ where $r$ is a rational approximation, $e$ a
        !           341: binary exponent and $\varepsilon$ is a nondescript real number less than 1 in
        !           342: absolute value\footnote{*}{this is actually not quite true: internally, the
        !           343: format is $2^b (a + \varepsilon)$, where $a$ and $b$ are integers}. Hence,
        !           344: any number less than $2^e$ may be treated as an exact zero:
        !           345:
        !           346: \bprog%
        !           347: ? 0.E-28 + 1.E-100
        !           348: \%1 = 0.E-28
        !           349: \eprog
        !           350: \noindent As an exercise, if \kbd{a = 2\pow -100}, why do \kbd{a + 0.} and
        !           351: \kbd{a * 1.} differ ?
        !           352:
        !           353: The second part of the PARI philosophy is that PARI operations are in general
        !           354: quite permissive. For instance taking the exponential of a vector should not
        !           355: make sense. However, it frequently happens that a computation comes out with a
        !           356: result which is a vector with many components, and one wants to get the
        !           357: exponential of each one. This could easily be done either under GP or in
        !           358: library mode, but in fact PARI assumes that this is exactly what you want to
        !           359: do when you take the exponential of a vector, so no work is necessary. Most
        !           360: transcendental functions work in the same way (see Chapter 3 for details).
        !           361:
        !           362: An ambiguity would arise with square matrices. PARI always considers that you
        !           363: want to do componentwise function evaluation, hence to get for example the
        !           364: exponential of a square matrix you would need to use a function with a
        !           365: different name, \kbd{matexp} for instance. In the present version \vers, this
        !           366: is not yet implemented. See however the program in Appendix C, which is a
        !           367: first attempt for this particular function.
        !           368:
        !           369: The available operations and functions in PARI are described in detail in
        !           370: Chapter 3. Here is a brief summary:
        !           371:
        !           372: \subsec{Standard operations}.
        !           373:
        !           374: \noindent
        !           375: Of course, the four standard operators \kbd{+}, \kbd{-}, \kbd{*}, \kbd{/}
        !           376: exist. It should once more be emphasized that division is, as far as possible,
        !           377: an exact operation: $4$ divided by $3$ gives \kbd{(4/3)}. In addition to
        !           378: this, operations on integers or polynomials, like \b{} (Euclidean
        !           379: division), \kbd{\%} (Euclidean remainder) exist (and for integers, {\b{/}}
        !           380: computes the quotient such that the remainder has smallest possible absolute
        !           381: value). There is also the exponentiation operator \kbd{\pow }, when the
        !           382: exponent is of type integer. Otherwise, it is considered as a transcendental
        !           383: function. Finally, the logical operators \kbd{!} (\kbd{not} prefix operator),
        !           384: \kbd{\&\&} (\kbd{and} operator), \kbd{||} (\kbd{or} operator) exist, giving
        !           385: as results \kbd{1} (true) or \kbd{0} (false). Note that \kbd{\&} and \kbd{|}
        !           386: are also accepted as synonyms respectively for \kbd{\&\&} and \kbd{||}.
        !           387: However, there is no bitwise \kbd{and} or \kbd{or}.
        !           388:
        !           389: \subsec{Conversions and similar functions}.
        !           390:
        !           391: \noindent
        !           392: Many conversion functions are available to convert between different types.
        !           393: For example floor, ceiling, rounding, truncation, etc\dots.  Other simple
        !           394: functions are included like real and imaginary part, conjugation, norm,
        !           395: absolute value, changing precision or creating an integermod or a polmod.
        !           396:
        !           397: \subsec{Transcendental functions}.
        !           398:
        !           399: \noindent
        !           400: They usually operate on any object in $\C$, and some also on $p$-adics.
        !           401: The list is everexpanding and of course contains all the elementary
        !           402: functions, plus already a number of others. Recall that by extension, PARI
        !           403: usually allows a transcendental function to operate componentwise on vectors
        !           404: or matrices.
        !           405:
        !           406: \subsec{Arithmetic functions}.
        !           407:
        !           408: \noindent
        !           409: Apart from a few like the factorial function or the Fibonacci numbers, these
        !           410: are functions which explicitly use the prime factor decomposition of
        !           411: integers. The standard functions are included.  In the present version \vers,
        !           412: a primitive, but useful version of Lenstra's Elliptic Curve Method (ECM) has
        !           413: been implemented.
        !           414:
        !           415: There is now a very large package which enables the number theorist to work
        !           416: with ease in algebraic number fields. All the usual operations on elements,
        !           417: ideals, prime ideals, etc\dots are available.
        !           418:
        !           419: More sophisticated functions are also implemented, like solving Thue
        !           420: equations, finding integral bases and discriminants of number fields,
        !           421: computing class groups and fundamental units, computing in relative number
        !           422: field extensions (including explicit class field theory), and also many
        !           423: functions dealing with elliptic curves over $\Q$ or over local fields.
        !           424:
        !           425: \subsec{Other functions}.
        !           426:
        !           427: \noindent
        !           428: Quite a number of other functions dealing with polynomials (e.g.~finding
        !           429: complex or $p$-adic roots, factoring, etc), power series (e.g.~substitution,
        !           430: reversion), linear algebra (e.g.~determinant, characteristic polynomial,
        !           431: linear systems), and different kinds of recursions are also included. In
        !           432: addition, standard numerical analysis routines like Romberg integration (open
        !           433: or closed, on a finite or infinite interval), real root finding (when the
        !           434: root is bracketed), polynomial interpolation, infinite series evaluation, and
        !           435: plotting are included.  See the last sections of Chapter~3 for details.
        !           436: \vfill\eject

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>