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

[Torbjörn Granlund]

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