GMP 6 the incomatible GMP?

Fredrik Johansson fredrik.johansson at gmail.com
Tue Jan 8 02:04:42 CET 2013


On Tue, Jan 8, 2013 at 12:28 AM, Torbjorn Granlund <tg at gmplib.org> wrote:
> nisse at lysator.liu.se (Niels Möller) writes:
>
>   Hmm. I guess one could go down to only 8 bits or so for the alloc field,
>   and for larger allocations, store the number of allocated limbs at the
>   head of the limb array (in the case limb size is not artificially small,
>   it could be just _mp_d[-1]).
>
> That's another idea.
>
>   Do you think 48 bits (or 47 bits absolute value) for _mp_size will be
>   large enough for the foreseeable future (say, 10 years)?
>
> I think that will be sufficient for some hundred years, since any
> super-linear algorithm applied to an operand of 2^53 bits (2^47 64-bit
> limbs) would hardly ever terminate even with a multi-THz CPU.

Well, pi has been computed to 10 trillion digits, which is 2^45 bits.
Extrapolating the records from the last 60 years, a 2^53-bit
multiplication can be expected to occur within 30 years, though
certainly with highly parallel hardware, not a single CPU. Actually,
NTTs of that size ought to be feasible on the current generation of
top supercomputers, in theory at least.

Of course 10+ years from now you could just release GMP 7 and break
backwards compatibility again ;-)

Fredrik


More information about the gmp-devel mailing list