| Welcome to the GNU MP web pages! Here you can find information about the GMP library, some important patches, and an outline of planned future developments. You can also find the manual and some useful diagrams here.

What is GMP?
GMP function classes
GMP documentation
Download the latest release of GMP
Improving GMP
Frequently asked questions
Status of the current release
Projects using GMP
Try GMP!
Future releases

#### What is GMP?

GMP is a free library for arbitrary precision arithmetic, operating on signed integers, rational numbers, and floating point numbers. There is no limit to the precision except the ones implied by the available memory in the machine GMP runs on. GMP has a rich set of functions, and the functions have a regular interface.

GMP is designed to be as fast as possible, both for small operands and for huge operands. The speed is achieved by using fullwords as the basic arithmetic type, by using fast algorithms, with carefully optimized assembly code for the most common inner loops for a lot of CPUs, and by a general emphasis on speed (instead of simplicity or elegance).

GMP is believed to be faster than any other similar library. The advantage for GMP increases with the operand sizes for certain operations, since GMP in many cases has asymptotically faster algorithms.

GMP is distributed under the GNU Library General Public License. For more information about the GNU project, please see the official GNU web site.

#### GMP function classes

There are five classes of functions in GMP.

- High-level signed integer arithmetic functions (mpz). There are about 100 arithmetic and logic functions in this class.

- High-level rational arithmetic functions (mpq). This class consists of just about 20 functions, but all signed integer arithmetic functions can be used too, by applying them to the numerator and denominator separately.

- High-level floating-point arithmetic functions (mpf). This is the GMP function class to use if the C type `double' doesn't give enough precision for an application. There are about 50 functions in this class.

- Low-level positive-integer, hard-to-use, very low overhead functions are found in the mpn class. No memory management is performed; the caller must ensure enough space is available for the results. The set of functions is not regular, nor is the calling interface. These functions accept input arguments in the form of pairs consisting of a pointer to the least significant word, and an integral size telling how many limbs (= words) there are in that argument.

  The three first classes of functions call these low-level function for almost all their calculations.

- Berkeley MP compatible functions.

#### GMP documentation (online and offline)

Complete documentation for GMP is available in the GMP Manual. It is also available for download in DVI format (42KB gzip'ed) and in PostScript format (114KB gzip'ed).

The speed of GMP varies a lot on different CPUs. See the GMP speed chart for details.

#### Download the latest release of GMP

Here you can download the complete sources for GMP:

  ftp://ftp.sunet.se/pub/gnu/gmp-2.0.2.tar.gz (Sweden)
  ftp://ftp.funet.fi/pub/gnu/prep/gmp-2.0.2.tar.gz (Finland)
  ftp://ftp.informatik.rwth-aachen.de/pub/gnu/gmp-2.0.2.tar.gz (Germany)
  ftp://utsun.s.u-tokyo.ac.jp/ftpsync/prep/gmp-2.0.2.tar.gz (Japan)
  ftp://labrea.stanford.edu/pub/gnu/gmp-2.0.2.tar.gz (USA, Pacific)
  ftp://ftp.gnu.org/pub/gnu/gmp-2.0.2.tar.gz (USA, East)

#### Improving GMP

Since GMP is free software, anybody can improve it and pass on the result, as permitted by the GNU Library General Public License. If you need an enhancement, but don't want to do the work yourself, you can pay somebody to do it for you. Try asking bug-gmp@gnu.org!

If you have written an improvement, please send it to bug-gmp@gnu.org so that it may be included in the next public release. If you plan on making an improvement, please first write to the same address, to make sure your effort is not duplicated.

#### Frequently asked questions

Q: Is there a C++ wrapper for GMP?

A: No, none as far as I know. Many people have started writing one, but nobody has ever sent me any useful code. "Useful" here means complete, efficient, and well-tested. (I intend to write a spec later and put it here.)

Q: When will the next release happen?

A: Hard to tell. I'd like to make it in mid 1999.

Q: I get a Segfault/Bus error in a program that uses GMP to calculate numbers with several hundred thousand digits. Why?

A: GMP allocates most temporaries on the stack, and some machines give user programs very little stack space by default. See setrlimit(2) for information on how to increase the stack allocation. You can also change it from the shell (using ulimit or limit depending on the shell). If you're not using Unix, then recompile the library using `make CFLAGS="-g -DUSE_STACK_ALLOC"'. (Yes, that is backwards..!)

Q: Are there known bugs in GMP?

A: See under "Status ..." a few lines below.

Q: I am working on Y2K certification here at Gull Enterprises. Can you tell me if GMP is year 2000 compliant?

A: GMP was designed for the sole purpose of solving this sort of problems. Just make sure to use the GMP supplied type mpz_t for all year data, and then sleep tight.

Q: What kind of answer is that?

A: Just kidding. But the Y2K question has been posed to the gmp mailing list several times!

#### Status of the current release

The current release is 2.0.2, released June 6, 1996. It was a good release, with no serious bugs in the integer functions, and with only a few serious bugs in the functions for rational numbers and floating-point numbers:

- A typo in `mpq_equal` makes it fail if the first compared operand is negative. This patch corrects the problem. Joe Keane found the problem and wrote the patch.
- Several errors in `mpf_set_str` and `mpf_get_str` make these functions segfault, and possibly generate incorrect results. This also affects `mpf_out_str`, `mpf_inp_str`, and `mpf_init_set_str`. This gzip'ed patch fixes these errors.
- A bug in a test case makes `make check' fail using the N32 ABI under Irix6. Apply this patch to mpz/tests/t-powm_ui.c to fix the bug. (Note that the N32 ABI isn't really supported in GMP; you need to pass `-n32 -mips3 -D_LONG_LONG_LIMB' manually to make GMP build correctly.)
- The performance on SPARC is poor because of a typo that causes some of the assembly code to be omitted. Apply this patch to mpn/configure.in to fix this.
- A bug in `mpz_invert` makes it sometimes return a negative result, and sometimes not detect when an inverse does not exist. Apply this patch to mpz/invert.c to fix this.
- A bug in `mpq_add` and `mpq_sub` makes them work unreliably due to references outside of allocated memory. Apply this patch to the mpq subdirectory to fix this.
- A change to GCC (I think from version 2.8) makes GMP fail to build on IBM RS/6000 computers running AIX. You'll see complaints of unrecognized assembly instructions. Pass `CFLAGS="-g -O2 -mcpu=power"` or `CFLAGS="-g -O2 -mcpu=powerpc"` to `make' to work around this. (Choose the form that is appropriate for your system; if you're unsure which processor type you have, try running config.guess from the GMP top level directory.)
- A bug in `mpz_probab_prime_p` makes it work unreliably for numbers < 4. Apply this patch to mpz/pprime_p.c to fix the bug.

Some Linux distributions have a buggy `ar` program that omits many of the files from libgmp.a. As a result libgmp.a becomes useless. The best solution is to get a newer GNU release of binutils, version 2.6 or later. As a workaround, you could also apply this patch to the top-level directory of GMP 2.0.2, if you don't want to upgrade your Linux tools. The patch was written by Alexander Zimmermann.

#### Projects using GMP

There are several interesting projects that rely on GMP. Here are some of the ones I am aware of:

- lsh is a project to develop a free (GPLed) implementation of the Secure Shell protocol V2; it is discussed on the psst.. mailing list.
- LiDIA, an object-oriental library which provides datatypes and algorithms for doing computational number theory. The system has a replaceable arithmetic kernel, which can use many different integer packages (at the moment gmp, cln, lip, libI, piologie).
- Paul Zimmermann implemented Lenstra's Elliptic Curve Method (ECM) for integer factorization using GMP. He runs a factorization project known as ECMNET.
- Paul Zimmermann also implemented Uspensky's algorithm for finding real roots of polynomials with integer coefficients. The source code is available here.
- CLN by Bruno Haible, which uses low-level routines from GMP to build a different high-level user interface.
- My own repunit factoring and prime search project...

There are also several projects using GMP to produce non-free software. It's too bad they chose not to share their work with the rest of us, and I won't add pointers to such projects, no matter how interesting! The EU sponsors lots of projects, several of them being based on GMP. But the EU requires that the result of projects they sponsor be non-free, which caused them to quickly be forgotten. (It is a shame for Europe that almost all cool free software is written in USA! Just think of GNU, X Windows, MIT Athena, Coda, Berkely Unix (FreeBSD, NetBSD), etc, etc. We should be grateful the EU never got any money into Linux, because then you would never have heard of it and it would just run on some obscure Transputer-based computer...!)

#### Try GMP!

Enter an integer expression in the field below. The expression may include +, -, *, /, %, ^ (exponentialization), and ! (factorial), the n-ary functions `gcd', `lcm', `and', `ior', `xor', `mul', `plus', the binary functions `minus', `div', `mod', `rem', and the unary function `popc' (population count). Most functions may also be used in infix form. All constants must be integers.

An example of a valid expression is:

1 + gcd(87324,78263148,7896) * (10^1989879887 mod 471!)
This is computed on a 200MHz Amd K6 running FreeBSD.

If you want to know how to do things such as this with GMP, take a look at the source code of the program used to compute these expressions.

#### Future releases

GMP 2.0.3 will be released in as soon as I can find the time to put it together. It will have fixes for all problems reported, and will work properly under Irix 6.

I hope to make a new major GMP release during 1999. I am looking for sponsors willing to support this work. Without sponsors, I do GMP in my spare time, and thus a release can be indefinitely delayed.

Here are the features that are scheduled for GMP 2.1:

- About 10 times faster extended GCD (`mpz_gcdext`) and inversion mod n (`mpz_invert`). The old code was really slow; the new code uses Lehmer's fast algorithm.
- Asymptotically fast division using Newton's algorithm (`mpz_tdiv*`, `mpz_cdiv*`, `mpz_fdiv*`, `mpf_div`, `mpf_ui_div`, etc). The time complexity will be O(n^1.58).
- Radically faster division when the size of the quotient is small compared to the size of the divisor. The time will usually be a function of the size of the quotient, although in case the remainder is much smaller than the divisor, the size of the divisor will come into play too.
- At least 60% faster multiplication and 100% faster squaring, thanks to reimplementation of the Karatsuba multiply code. (Contributed by Rob Harley of Inria, France.)
- Support for using native 64-bit operations with MIPS R4x00 and R5000 under Irix 6.x. The result will be a two-fold speed increase for all operations, in conjunction with the other speed improvements of this list.
- Better support for Cray and Fujitsu vector computers. The most important loops will vectorize.
- Switch to autoconf. This will make it simpler to build the library.
- Much improved conversion between floating-point numbers and ASCII for numbers with large exponents.
- Possibly support for handling of numeric exceptions inside GMP. (Now most functions divide by 0, other functions crash, neither which is terribly useful.)
- Possibly better support for numbers that are less than 2^64 by storing them inside the basic GMP types, avoiding the current dynamic allocation.

Please send comments about this page to tege@swox.com. Copyright (C) 1999 Torbjörn Granlund. |