Use on small mulmod_bnm1 [was: New mulmod_bknp1]

[Niels Möller]

Marco Bodrato <bodrato at mail.dm.unipi.it> writes:

> In the 128-2048 range (at least on that machine: shell.gmplib.org) the
> sizes multiple of 12, 24, 48... should be preferred...

I don't fully understand this, but if I got it right, we want the size n
to be divisible by 2^k, for mulmod_bnm1 to be able to split a few times.
But we don't need a very large k, since we have diminishing returns for
each split.

And for the new mulmod_bknp1 to fit, we also need n to be divisible by
one of certain small odd numbers, currently 3, 5, 7, 13, 17.

> But I'm not sure if we should really tune a table (so as we do for
> FFT), or some simpler criterias would give reasonable results...

I think it would make sense to first select k (maybe a constant, or
growing very slowly with n, which might ask for a tuned table), say 2 <=
k <= 5 for the size range of interest. And then round n upwards to the
closest multiple of one of 2^k * {3, 5, 7, 13, 17}. Hmm, or maybe to
make it more complex, one of 2^{k,k-1} * {3, 5, 7, 13, 17}, it that
let's us avoid growth. It would be nice if we could find a set of
candidates that guarantess that we don't have to increase size more
than, say, 10%, but not sure if that's possible.

Regards,
/Niels


-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.