Home   Index

AU-KBC RESEARCH CENTRE

AMPL

Another Multiple Precision Library

Introduction

        Numbers that are small enough to be represented in a single computer word are called "single-precision" numbers. For example, on the so-called 32-bit machines, the internal CPU registers are all 32 bits wide and memory accesses are also aligned along 32-bit boundaries. On such machines it is possible to represent any positive integer less than 232 (i.e., any positive integer less than 4, 294, 967, 296) in a single 32-bit word. Therefore, any positive integer upto (but not including) this maximum value, may be represented in single precision . Also, the basic instruction sets of the machines usually operate on data types whose sizes are a single computer word. Most applications seldom deal with values that are large enough to overflow the basic data types.

        However, in some applications such as cryptography and number theory, the sizes of numbers that we have to deal with are so large that they do not fit into a single word -- typically on the order of 10200 or 10300 . But this does not mean that since it is not possible to represent a large integer in a single word, it is not possible to represent it at all. Very large numbers may be represented by an ordered set of integers, each of which is itself small enough to fit into a single computer word. For example, we may regard the ordered set of single precision numbers as the digits of a positional number system with a sufficiently large base. Or we may regard the set as consisting of the residues of the number with respect to a fixed set of moduli, i. e., as a modular representation. Since many machine words are used to represent a single large number, we call such numbers "multiple-precision" (MP) or "arbitrary-precision" numbers, and the algorithms for performing the basic operations of addition, subtraction, multiplication, etc., are generalised to handle these multiple-precision integers. AMPL provides just these kinds of very general algorithms for performing multiple-precision arithmetic.

The AMPL functions

        AMPL (pronounced "ample"), which provides facilities for operating on numbers with arbitrary precision, is implemented as a set of user-callable functions written purely in ISO Standard C. The maximum size of numbers that can be handled by AMPL is limited only by the amount of memory available. The greatest advantage of AMPL is its strict conformance to the ISO Standard. This makes AMPL highly portable across systems.

        There are about fifty user-visible functions in the library and these may be divided into six broad classes:
        Memory management
        Functions in this class allocate, initialise, resize and de-allocate memory for MP objects.
        Input/Output operations
        Routines for reading and converting arbitrarily long numeric strings in different bases into MP numbers and vice-versa.
        Arithmetic operations
        Addition, subtraction, multiplication, division, exponentiation, and their variants are implemented in this class.
        Modular arithmetic operations
        These functions implement addition, multiplication, exponentiation, and their variants, with respect to some modulus.
        Logical operations
        Routines for comparing, shifting and bit-wise operations fall into this class.
        Miscellaneous operations
        General utilities, and other functions such as copying and assignment operations, etc., are implemented in this class.

Special features of AMPL

Anand Sridharan