GMP 4.4 remaining tasks
Torbjorn Granlund
tg at gmplib.org
Tue Dec 8 11:09:13 CET 2009
bodrato at mail.dm.unipi.it writes:
>> I suppose we could write a special mulmod_bnm1 for the degenerate case
>> where 2bn < rn.
>
> I don't think you need any interesting special handling for that case.
> What happens is just that the top-level split into b mod (B^n + 1) and b
> mod (B^n - 1) are nops, where the "normal" case needs an add and a sub.
> Current code handles that (even though Marco has marked that handling as
> "ALLOW_MISUSE...).
The additional restrictions given by "#define ALLOW_MISUSE 0", affect size
an only. The product with (an > rn/2) && (an => bn) will work anyway.
My goal, when I modified mulmod_bnm1, was to allow the case (an+bn)<=rn.
So that mulmod_bnm1 can be used for the full product.
It is _not_ slower than current mpn_mul_fft_full...
The "misuse" forbidden by the definition above are _very_ degenerate:
- (an+bn) < rn/2
That might happen if we want to do full multiplication, given the nature
of mpn_mulmod_bnm1_next_size...
Talking about mpn_mulmod_bnm1_next_size. My simple-minded rounding to
the next multiple of 16 for all sizes under MUL_FFT_MODF_THRESHOLD could
perhaps be trimmed to have some size dependency:
1. I suspect we should round 9,10,11 to just 12, and that some values
under 24 should be rounded to 24.
2. If we ever consider writing mpn_bc_mulmod_bn{m,p}1 in assembly, it
would be nice to make sure the sizes are really in a schoolbook
range. We could enforce that by rounding to a larger multiple for
large operands (specifically, that the down-shifted even value is in
the schoolbook range). Silly or clever?
We should realise of course that mpn_bc_mulmod_bnm1 will be called
just once and that mpn_bc_mulmod_bnp1 will be called once for small n
and zero times for large n. Optimised mpn_bc_mulmod_bn{m,p}1
therefore only matter for smallish operations.
--
Torbjörn
More information about the gmp-devel
mailing list