Marco Bodrato <bodr...@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. _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel