How large are arbitrarily large integers? (Was Re: Bitfield subtlety)
Niels Möller
nisse at lysator.liu.se
Thu Mar 29 18:40:53 UTC 2018
tg at gmplib.org (Torbjörn Granlund) writes:
> Yes. The mantissa size determines which is the smallest operand for
> which we need to add some bookkeeping overhead for doing the float
> conversion. These small sizes will just store the exact integral
> allocation.
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.
> I considered several possibilities of the form m*b^e, where m is the
> mantissa and e is the exponent, both stored in an k bit allocation
> field, and b is implicit the base which I limited to either 2, 4, 8, or
> 16. Only m and e sizes and b bases which result in similar allocation
> range and _mp_size range are of course worth considering.
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.
> Perhaps something like (2,14,5) would make most sense. This would give
> allocation range of 2^45 limbs and size range of 2^44 limbs, while
> invoking the hairy code for allocations above 8191 limbs.
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.
And we actually get an identity mapping for both e = 1 and e = 0, so
no hairy code for sizes < 2^15 = 32768.
Does this make sense? It's kind-of neat to not have to extend the
exponent to 6 bits.
Regards,
/Niels
--
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel
mailing list