Reflections on mulmod_bnm1

[Niels Möller]

bodrato at mail.dm.unipi.it writes:

> Input of basecases are semi-normalised. The top limb equal to one does not
> imply that all other limbs are zero.

Are you sure? To me, it looks like the code produces values mod B^n + 1
by code equivalent to

  cy = mpn_sub_n (rp, xp, xp + n);
  rp[n] = mpn_add_1 (rp, rp, n, cy);

Then rp[n] = 1 only if cy = 1 and the resulting {rp, n} are all zero.

>> I'm not so bothered by MNP_COPY in unlikely cases, but I don't like the
>> zero-padding of inputs (MPN_ZERO). And I think it is unfortunate if for
>> some small inputs mulmod_bmn1 is significantly slower than unbalanced
>> mpn_mul + mpn_add. Say, an = rn = 20, bn = 12, or rn = 20, an = bn = 15
>> (and threshold > 20).
>
> In both cases you mention bn > rn/2, this means: no copy, no padding.

Both cases have rn below the MULMOD_BNM1_THRESHOLD. Then mpn_mulmod_bnm1
zero-pads both operands to size rn, and calls mpn_bc_mulmod_bnm1. With
even smaller bn/rn, you can get padding also for rn >
MULMOD_BNM1_THRESHOLD.

Regards,
/Niels

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