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

[Niels Möller]

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

> Would 8 more size bits do?  That would allow 11,728,124,029,610 decimal
> digits.  Do we need 16 more bits?  That would up the limit to
> 3,002,399,751,580,330 decimal digits, at the expense of 0.05% more
> allocation for large operands on average.  Stealing more alloc bits than
> that quickly makes allocation very coarse.

I think one relevant question is on how large numbers we expect to be
able to complete any computation with worse complexity than O(n) in
reasonable time. But when we integrate fft multiplication with decent
locality, the limit will be cpu power, not available RAM, I'd hope.

To me, 0.05% allocation overhead sounds reasonable. Is there any
other good reason to steal less than 16 bits?

(I also think it would in some ways be easier to allocate the alloc and
size fields together with the limb array for huge numbers, but last time
we discussed these extensions, I think we found the custom-float hack
more attractive after all).

Regards,
/Niels

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