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

[Torbjörn Granlund]

Emmanuel Thomé <Emmanuel.Thome at inria.fr> writes:

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

I like "gmp enterprise".  Would have made a good April Fools joke, in
fact.

  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.

You're right. I used the wrong expression computation tool which
computes log2(n) as floor(log2(n)) :-(

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

I understand the limitations, and if DRAM prices and density would still
be following (Moore's exponential) law, we couldn't add enough bits to
the size field.

  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.

GMP n for some finite value of n will run awesomely with operands on disk
or some other remote place.

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