Arithmetic without limitations?

[Joerg Arndt]

* Torbjorn Granlund <tg at gmplib.org> [Feb 11. 2010 10:19]:
> [...]

>   
> Incidentally, I have long planned to do exactly what he did, once we had
> the Cooley-Tukey small primes code in place.  My goal was to make a
> spalsh for GMP 5, but in the end we decided to postpone the new FFT
> code.  Yes, I am little envious not to have done this first.  :-)

If "this" means mass-storage FFT multiplication then my computation of
9^(9^9) in 1999 (on a 32-machine) is prior, see p.450 of the fxtbook.
The code is in the fxt lib, used by the hfloat lib.

But yes, considerations about radix/precision (p.561ff) rule out
float-FFTs (with 64bit doubles) for extremely large numbers (with
decimals and radix 1,000 one can get as far as about 3G decimal
digits).  So really NTTs (and CRT) would be needed.  (It appears float
FFTs are frowned upon with GMP anyway).

One may argue that working with numbers which do not fit into RAM
really is something to be left to specialized libs.  For example, one
would definitely use raw devices for the scratch "files" to avoid
_all_ file-system overhead.  Also multi-threading is very advantageous
for speed, even for single core CPUs.  Not sure all or even any of
this has to be in GMP (nonwithstanding the coolness factor).


> 
> [...]

I wish Fabrice would open sorce his code!  (I am aware of 2 more
extremely powerful artihmetic libraries that rot away on the disks of
their authors).