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