Cancellation with hgcd / unbalanced mulmod_bnm1

bodrato at bodrato at
Sat Nov 12 20:05:28 CET 2011

Ciao Niels!

Il Sab, 12 Novembre 2011 5:50 pm, Niels ha scritto:
> bodrato at writes:
>> Exactly, in the FFT range the cost of the mpn_mul 2n x n and the cost of
>> the mpn_mulmod_bnm1 3n x n are the same.
> It's not entirely obvious the best way to do a 2n x n multiply is using
> mpn_mul_bnm1, rather than tomm42 or toom63 (recursing to fft, i.e.,
> mpn_mulmod_bnm1, for large sizes). But if I read the diagrams

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



More information about the gmp-devel mailing list