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

[Niels Möller]

tg at gmplib.org (Torbjörn Granlund) writes:

> nisse at lysator.liu.se (Niels Möller) writes:
>
>   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?

No, I imagine one would need two cases.

> Don't forget the sign bit needed for the size.

I did forget about that...

>   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.

Recall

  x = m for e == 0
  x = (2^{mantissa bits} + m) 2^{e - 1} for e > 0

For illustration, reduce mantissa to only 2 bits

e   m   x
00  00  0000
00  01  0001
00  10  0010
00  11  0011
01  00  0100  (2^2 + 0) 2^{1-1} 
01  01  0101
01  10  0110
01  11  0111
10  00  1000  (2^2 + 0) 2^{2-1}
10  01  1010  (2^2 + 1) 2^{2-1}
10  10  1100

So if we compare the concatenation of e and m to x, we have identical
bit patterns for both e = 0 and e = 1, with the first difference for e =
2, m = 1.

The thing is, for e = 1, the low one bit of the exponent is at precisely
the right place to stand in for the implicit one bit of the mantissa.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.