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

[Niels Möller]

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.