How large are arbitrarily large integers? (Was Re: Bitfield subtlety)
Torbjörn Granlund
tg at gmplib.org
Thu Mar 29 08:36:29 UTC 2018
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
More information about the gmp-devel
mailing list