fft interface

[Emmanuel Thomé]

Hi,

On Wed, Oct 17, 2012 at 10:22 AM, Niels Möller <nisse at lysator.liu.se> wrote:
> And we totally lack interfaces for invariance (and such interfaces don't
> have to be fft-specific).

Just a follow-up on this. I recall Torbjörn expressing the desire to
add such functionality. That was a few years back, and indeed this
would be a worthy addition IMHO.

Note that supporting operand invariance (as in powering, for instance)
is one step, but there is possibly more to be done in this area. Think
matrix multiplication for instance. One also wants to be able to *add*
the transformed data. I see there's a FIXME item in
mpn_hgcd_matrix_mul precisely regarding this. This use case should not
be overlooked. Conceivably, interest could appear regarding other
Z-linear operations.

I agree on the principle that interfaces for invariance do not have to
be fft-specific. However, the ratio between pointwise ops and
evaulation is quite different in the kara-toom and fft areas. I'm not
exactly convinced that such an interface for non-fft range would be
really useful (I am talking only multiplication. Division is
different).
 - either the interface is completely phony. Then why bother ?
 - or the ``transformed'' version of an integer has length M(n), which
is cumbersome.
 - or only a few steps of evaluation are ``unrolled'' in the
``transform''. E.g. for kara, an integer A=(A0+A1*B)+(A2+A3*B)*B^2 can
be transformed into [(A0+A1*B), (A2+A3*B), (A0+A1*B)+(A2+A3*B)] (one
step), or even [A0, A1, A0+A1, A2, A3, A2+A3, A0+A2, A1+A3,
A0+A1+A2+A3] (two steps). There we control expansion from the original
data to the transform (here 4->9), but the little that we save is not
much tempting.

What are you thinking about regarding operator invariance support for
multiplication in the non-fft range ? (sorry if I am missing something
obvious).


In the FFT range, we have Paul's patch for the current
Schonhage-Strassen implementation which is already useful.
Unfortunately it lives outside gmp:

http://www.loria.fr/~zimmerma/bignum/fft_patch.gmp-5.0.1


Best,

E.