Cancellation with hgcd / unbalanced mulmod_bnm1
nisse at lysator.liu.se
Sat Nov 12 20:40:33 CET 2011
bodrato at mail.dm.unipi.it writes:
> Remember that toom42 simply is "unbalanced Toom-3" (i.e. same cost as
> toom33), toom63 is "unbalanced Toom-4'n'half" and mpn_mulmod_bnm1 can be
> used for "unbalanced FFT". With this point of view, it should be easier to
> understand that, in the FFT range, mulmod is the best strategy (among the
Ah. So then the only unbalanced algorithms which can beat fft at large
sizes are *interated* multiplication doing one block of the larger
operand at a time. Which are linear in the size of the larger operand.
Not sure how relevant that is for sizes like 3n x n and 2n x n, though
That's also related to Torbjörn's suggestion of reusing the transform of
the smaller operand.
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel