How large are arbitrarily large integers? (Was Re: Bitfield subtlety)
Richard Biener
rguenther at suse.de
Thu Mar 29 07:32:52 UTC 2018
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)
More information about the gmp-devel
mailing list