fast gcd
Torbjorn Granlund
tg at gmplib.org
Wed Oct 14 10:44:31 CEST 2009
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
More information about the gmp-devel
mailing list