largest number
Torbjorn Granlund
tg at gmplib.org
Mon Mar 5 15:48:57 CET 2012
Zimmermann Paul <Paul.Zimmermann at loria.fr> writes:
> The upper limit on representable integers in GMP is a function of the
> memory available to your machine. There are no practical intrinsic
> limits with present-day machines. Two hundred million (decimal) digit
> numbers are under a billion bits, which is readily feasible.
this is not completely true. For mpz_t the _mp_size field is an "int", which
has 32 bits on most platforms, and the sign bit is used to represent the sign
of the number. Thus the hard limit is 2^31-1 limbs, which is 2^37-64 bits on a
64-bit platform. In practice it seems the actual limit is a bit smaller, i.e.,
2^37-128 bits. This will take about 16GB memory, which is not uncommon now.
This is also not completely true. :-)
The hard limit for mpz is 2^32-1 *bits*, on a 32-bit machine,
and (as Paul says) about 2^37-64 bits on a 64-bit machine.
We are not aware of any practical limits in mpn on a 64-bit machine, but
using precisions over 2^32 limbs means wandering into an untested
territory. (The limit is 2^32-1 bits for 32-bit machines, which is
close to the entire address space.)
We might lift the mpz limit for 64-bit machines, with some trickery.
The idea is to borrow bits from the _mp_alloc field to be used by the
_mp_size field, using a 20-bit custom float for alloc (14 bit mantissa,
6 bit exponent), and a 44-bit integer for the size field. This will add
some slight overhead, but keep the struct at the same size, for source
compatibility. The overhead comes primarily from false reallocation
conditions for sizes above 16383 limbs, since that code for checking for
reallocation should initially assume the float in an integer...
--
Torbjörn
More information about the gmp-discuss
mailing list