Toom k-way in GMP 5?

[bodrato at mail.dm.unipi.it]

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/