Toom k-way in GMP 5?
bodrato at mail.dm.unipi.it
bodrato at mail.dm.unipi.it
Thu Jan 14 12:49:52 CET 2010
Dear Paul,
> thank you very much for your answer.
Thank you very much for your questions, analysis, suggestions ... ;-)
> thus GMP does not use Schönhage-Strassen any more? Nor does it use
> FFT mod B^n-1 and B^n+1 and CRT reconstruction?
Sorry for my misleading answer. My focus was on Toom (as usual).
The old mul_fft_full has been disabled, but this does not means that also
the next version will not use (some renewed version of) it!
Currently GMP5 computes the large products modulo some B^m-1. This is done
by CRT reconstruction of two halves B^{m/2}-1 and B^{m/2}+1. Respectively
computed recursively and using the usual FFT code.
> How can mpn_toom6h_mul work with 7x6, which requires 12 evaluation points?
The "h" means "half"; toom6h actually implements Toom-6_and_half (Toom-6.5
as I called it in the paper with Alberto), i.e. it uses 12 points.
The advantage of an even number of points is that one can use a trick that
I call "early recomposition", i.e. one can mix the usual evaluation,
pointwise-product, and recomposition phases to obtain some speed-up and a
lower memory foot-print.
The idea was announced here some months ago:
http://gmplib.org/list-archives/gmp-devel/2009-June/000906.html
So I reread your question "how can you do 6x6 if you use 12 points?".
I now you can guess the answer: it's like 7x6, but evaluation in infinity
gives zero. This "intuitive" answer describe the current implementation.
There is also a "counter-intuitive" answer, i.e. we can skip the
evaluation in ZERO. I think it should give slightly better results, but
this is not implemented yet.
By the way, to write a Toom function that accepts a wide range of operands
and internally decides the splitting, one necessarily needs to use a Toom
and a Toom-and-half, or there will be some "shapes" one can not handle.
I mean, if with a fixed number of points one can do (n)x(m) and
(n+1)x(m-1), there will be no way to handle the border case (n)X(m-1).
With two adjacent Toom, one fills the gaps of the other one.
Best regards,
Marco
--
http://bodrato.it/papers/
More information about the gmp-devel
mailing list