Cancellation with hgcd / unbalanced mulmod_bnm1

[Niels Möller]

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
> three).

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.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.