Cancellation with hgcd / unbalanced mulmod_bnm1

[bodrato at mail.dm.unipi.it]

Ciao Niels!

Il Sab, 12 Novembre 2011 5:50 pm, Niels ha scritto:
> bodrato at mail.dm.unipi.it 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
three).

Regards,
m

-- 
http://bodrato.it/software/