How large are arbitrarily large integers? (Was Re: Bitfield subtlety)

Torbjörn Granlund tg at gmplib.org
Wed Mar 28 21:18:49 UTC 2018


On 64-bit machines GMP's mpz functions allows operands of 2^37 bits That
corresponds to 45,812,984,490 decimal digits, quite a few.  A similar
limit exists for GMP's floats' precision.

Now, this is not always enough.  Some applications would like GMP to
support much larger operands.  We can do that without breaking the ABI
and without making the mpz type larger.  The trick is, as I mentioned
before, to steal some bits of the _mp_alloc field for use as additional
operand size bits.  We then use a custom float for the allocation.  The
price for this change is:

* minuscule extra overhead
* coarser allocation, but this will be just a fraction of a percent
* incompatibility with user code which accesses GMP's internal fields

So, now to the question1:

(1)

What should the new limit be?  GMP is now 27 years old, and it seems
reasonable to assume it will live at least another 27 years.  In that
time, computer hardware will evolve, I presume.

Would 8 more size bits do?  That would allow 11,728,124,029,610 decimal
digits.  Do we need 16 more bits?  That would up the limit to
3,002,399,751,580,330 decimal digits, at the expense of 0.05% more
allocation for large operands on average.  Stealing more alloc bits than
that quickly makes allocation very coarse.

The 1 million GiB of RAM needed for storing a single number with
3,002,399,751,580,330 decimals costs at least 14 million USD.  I am not
sure any computer exists which has enough RAM sockets, though.

(2) Does anybody have a 2 TiB computer to lend to the GMP project for
our testing?  :-)

-- 
Torbjörn
Please encrypt, key id 0xC8601622


More information about the gmp-devel mailing list