Reflections on mulmod_bnm1

[bodrato at mail.dm.unipi.it]

Ciao,

> I'm not 100% sure it's a good design idea to use a single size parameter
> for the basecase functions. I guess the idea here is that mulmod_bnm1 is
> useful only when there's at least one split and recursive calls to bnm1
> and bnp1. And if one assumes that an >= rn / 2, then the recursive calls
> all will have an = bn = rn. (This is of course related to the
> ALLOW_MISUSE that Marco described earlier today).

If one assumes an >= rn/2, then recursive calls will have rn = an >= bn.

Obviously bc_mulmod_bnp1 can be used also by FFT or elsewhere, but let us
focus on internal use only.

At first I wrote basecases with all the three parameters: an, bn, rn. This
avoids any MPN_COPY, but forces the use of mpn_mul and some logic in the
_bc, to be repeated all the times, even in the very likely case an=bn=rn.
Moreover, there was a subtile bug: it could happen that bc_mulmod_bnp1 was
called with (anp < bnp), even if originally we had (an >= bn)... because
wrapping can give a carry or not... and mpn_mul does not support an<bn.

The single-sized basecases are simpler and faster, their usage forces us
to add some logic on the caller side, where we can decide if we want to
support all the possible uses, or we prefer to reduce them simplifying the
code.

Finally, logic is moved where we have more control on it (maybe reducing
it, maybe not), we added some COPY but only in unlikely conditions, we can
use mul_n instead of mul. In my opinion, the balance is positive.

Regards,
Marco

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