fast gcd

[Torbjorn Granlund]

Paul Zimmermann <Paul.Zimmermann at loria.fr> writes:

  since you answered on gmp-devel, let me continue the discussion there.

Yes, please let's gmp-devel be the main arena for GMP technical
discussions.

  >   * Use FFT invariance for the matrix-vector multiplication
  >     mpn_hgcd_matrix_adjust. This function is used for varying
  >     balancedness of the inputs, depending also on the choice of p in
  >     the gcd and gcdext outer loops.
  
  you report a 15% speedup in your slides. Since most of the time is spent in the
  matrix-vector and matrix-matrix products asymptotically, and each operand is
  reused twice, we can expect a theoretical speedup of up to 50% if the pointwise
  products are negligible (i.e., with an FFT of large order).
  
This should largely depend on the FSF coefficient ring size too.  The
present GMP FFT code's ring is a function of the product size.  The
dyadic products then of course will take time non-linear in the product
size.

Other FFT variants use a fixed ring size (or a few fixed ring sizes to
choose among).  The dyadic products will then take linear time.

This is an interesting resulting property: some FFT variants give
different invariance behaviour.

(This is not a novel observation, of course.)

-- 
Torbjörn