Use on small mulmod_bnm1 [was: New mulmod_bknp1]

[Niels Möller]

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

>> 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.
>
> Yes, with a larger expected gain for 3, and a smaller one for 13, or 17.

And in your table, almost all use 3, and none use 7, 13 or 17.

> It should be possible to not increase too much.

Sounds good!

>  size -> measured time
>  1008 -> 6.156e-05	(+  72, +8.3%) 2^4*3^2*7
>  1080 -> 6.906e-05	(+  72, +12%) 2^3*3^3*5
>  1104 -> 7.294e-05	(+  24, +5.6%) 2^4*3*23

So 1104 wins over the power of 2, 1024 = 2^10.

>  1128 -> 7.686e-05	(+  24, +5.4%) 2^3*3*47
>  1200 -> 7.986e-05	(+  72, +3.9%) 2^4*3*5^2
>  1224 -> 8.28e-05	(+  24, +3.7%) 2^3*3^2*17
>  1296 -> 8.602e-05	(+  72, +3.9%) 2^4*3^4
>  1320 -> 9.437e-05	(+  24, +9.7%) 2^3*3*5*11
>  1368 -> 9.824e-05	(+  48, +4.1%) 2^3*3^2*19
>  1392 -> 0.0001022	(+  24, + 4%) 2^4*3*29
>  1416 -> 0.0001087	(+  24, +6.4%) 2^3*3*59
>  1512 -> 0.0001112	(+  96, +2.3%) 2^3*3^3*7
>  1584 -> 0.0001159	(+  72, +4.2%) 2^4*3^2*11
>  1600 -> 0.0001217	(+  16, +5.1%) 2^6*5^2

The only example in the list using 5 as a factor.

>  1680 -> 0.0001273	(+  80, +4.6%) 2^4*3*5*7
>  1704 -> 0.0001396	(+  24, +9.7%) 2^3*3*71
>  1728 -> 0.00014	(+  24, +0.23%) 2^6*3^3
>  1776 -> 0.0001434	(+  48, +2.4%) 2^4*3*37
>  1800 -> 0.0001439	(+  24, +0.35%) 2^3*3^2*5^2
>  1872 -> 0.0001463	(+  72, +1.7%) 2^4*3^2*13
>  1920 -> 0.000158	(+  48, + 8%) 2^7*3*5
>  1944 -> 0.0001598	(+  24, +1.2%) 2^3*3^5
>  1984 -> 0.0001648	(+  40, +3.1%) 2^6*31

First example not using any of the odd numbers in the list, so not using
mulmod_bknp1 at all.

>  2048 -> 0.0001676	(+  64, +1.7%) 2^11

I wonder if this would be beaten by 2064 = 2^4*3*43, or if this power
of two really is a winner.

It's also interesting that all these winners use 2^k with k >= 3, so
third split in mulmod_bnm1 seems to pay off measurably. 

So just rounding up to a multiple of 24 = 2^3 * 3 might be a reasonable
initial strategy (above some threshold of a likely few hundred limbs). 

Regards,
/Niels

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