Cancellation with hgcd / unbalanced mulmod_bnm1

[Niels Möller]

bodrato at mail.dm.unipi.it writes:

> The cost of current mpn_mulmod_bnm1 implementation does not really depend
> on how much balanced the operands are.
> It computes two products: mod m'=B^{k/2}+1, and mod m"=B^{k/2}-1. In your
> scenario, it will further reduce a, resulting in two 3/2 n x n mulmods; it
> will detect that b is short and will not reduce it, this is the only
> saving related to unbalancement.

This makes me think that maybe using mulmod_bnm1 is not optimal for such
unbalanced operands, say kn x n (mod B^{kn} - 1).

> 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
http://gmplib.org/devel/ correctly, mpn_mul_bnm1 wins for large sizes.

There's still room for other strategies for sizes below 5000 limbs or
so, which may affect the HGCD_REDUCE threshold.

Regards,
/Niels

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