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

[Richard Biener]

On Wed, 28 Mar 2018, Torbjörn Granlund wrote:

> 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

You can also steal low-order bits from the pointer depending on
alignment...  and depending on the host also some high-order bits.

You can also simply off-load the allocation size to the allocated
area (like to *(size_t)(_mp_d - 8)).  In fact you are already breaking
the ABI in some sort by re-purposing fields given that the internals
of __mpz_struct is exposed.

Not sure if you are already doing small-numbers optimization like
avoiding any allocation for size == 1 by re-purposing _mp_d as
the single allocated limb (where the size of _mp_d makes this possible).

> 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?  :-)

2TiB is not unheard of - but my immediate followup question would be
why the storage needs to be in RAM?  Why can't mpz operate on offline
storage like large SSDs?

Richard.

-- 
Richard Biener <rguenther at suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)