How large are arbitrarily large integers? (Was Re: Bitfield subtlety)
Torbjörn Granlund
tg at gmplib.org
Thu Mar 29 20:01:40 UTC 2018
nisse at lysator.liu.se (Niels Möller) writes:
Ah, so large mantissa is beneficial both for reducing this overhead, and
to reduce the amount of rounding up for the allocation for huge numbers.
Yep.
I was thinking of something like
x = m for e == 0
x = (2^{mantissa bits} + m) 2^{e - 1} for e > 0
where the first case, e = 0, are some kind of denormalized numbers, and
the second case has an implicit one bit.
Ah, I had not considered using an implicit bit. That should add some
overhead when writing new alloc fields. Do you have some clever code
for that?
A different little tweak is to do
x = (m+1) 2^e
which means that we would reach an exact power-of-two as limit (not some
2^r-2^s). Not a fantastic range extension, but a limit which is easier
to communicate.
With the above model, largest representable value for the alloc field
would be
2^30 (2^14 + 2^14-1) = 2^45 - 2^30,
and we have 45 bits left for the size field. If we really want, we could
extend the range all the way to 2^45-1 by a special interpretation of
the case of both e and m being all ones.
Don't forget the sign bit needed for the size.
And we actually get an identity mapping for both e = 1 and e = 0, so
no hairy code for sizes < 2^15 = 32768.
I don't follow you here.
Does this make sense? It's kind-of neat to not have to extend the
exponent to 6 bits.
Let's avoid that. Just because many mistakes have been made relatated
to underestimation of memory use, we don't need to overestimate it.
If we go with some 44 bit proposal, then current CPUs with current GMP
code assuming an infinite cache would take about a year for a single
2^50-bit multiplication.
--
Torbjörn
Please encrypt, key id 0xC8601622
More information about the gmp-devel
mailing list