Arithmetic without limitations?

Paul Zimmermann Paul.Zimmermann at loria.fr
Wed Feb 10 17:09:53 CET 2010


       Hi,

yesterday Fabrice Bellard, who holds the current record for computing digits of
Pi, gave a talk in our lab. His slides (in french) are available at
http://misn.loria.fr/fichiers/bellard-20100209.pdf. Slide 34 compares his
implementation (TPI) with gmp-chudnovsky.c and GMP 5.0.1. You can try TPI
from http://bellard.org/pi/pi2700e9/tpi.html.

The most amazing thing is not that he set a new record, but that he did it on
a personal computer with only 6GB of RAM, where the largest multiplication he
had to perform was between two numbers of 2700 billion decimal digits, i.e.,
about 1.1TB each!

This is really what we are missing in GMP. The current GMP algorithms are so
fast (almost linear in the input size) that time is no more a problem, but more
and more memory is a real limitation.

To set his record, Fabrice designed a multiprecision library (yes, from
scratch) with the same API as GMP, but with an intermediate level "mpt"
between "mpn" and "mpz". The idea is that a "mpt" can either contain an
array of limbs (mpn) in memory, or points to a file on disk. The mpn level
(now mpt) has to be redesigned to be able to handle inputs or outputs on disk,
but then every program using mpt (including mpz) will work without any change.

I believe in the future GMP should give facilities for "out-of-core" computing.

Paul





More information about the gmp-devel mailing list