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

[Emmanuel Thomé]

On Wed, Mar 28, 2018 at 11:18:49PM +0200, 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.

Quite a few digits, yes, but I remember that it's been a while since I've
hit that limit for the first time. And lately, I do so every now and
then, without even realizing I'm about to compute something extreme.

My personal favorite moniker for the ABI-breaking bastardization of GMP
that consists in redefining the alloc and size types to long is
"gmp enterprise" ;-). I've used that to bench the product of two 2^40-bit
integers (it takes 8 hours and 1.3 TB of RAM).

> [...]
>
> 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.
 
I'd much rather go for the 16-more bits option (but I don't get the same
numbers as you do -- I get 2^53 bits, a.k.a. 2.7*10^15 decimals). The
2^45-bits option seems short-sighted to me.

> 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.

I'm not sure this data is very relevant. FWIW, the 16GiB of RAM it takes
to store a single number of 2^37 bits cost 1.7 million USD in 1990
(source: a random pick from the web, https://jcmit.net/memoryprice.htm ).
So we're more or less in the same ballpark.

With a bit of a stretch, we could actually envision (in the not so
distant future, at least) a huge RDMA-based cluster offering an
addressable memory space nearing 1PiB. (after all, all it takes is 4096
nodes with 256GiB RAM each). That's not what I call "RAM", but not
everybody thinks the same.

Cheers,

E.