Ciao Niels, for some reason I did not receive your answer. I took the text from the archive.
Il gio, 21 aprile 2022 08:15 am, Niels Möller ha scritto: > Marco Bodrato <bodrato at mail.dm.unipi.it> writes: >> 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. >> size -> measured time >> 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. Yes, it does. Both on shell and on my laptop, even if in both cases MUL_FFT_MODF_THRESHOLD is smaller than 512. >> 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. There are some more in the full list... >> 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. Yes, starting from here, the power of 2 seems dominant. >> 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 is a winner, I measured a much larger range. > 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. On that machine, in that range. > 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). The reasonable gaps between the sizes probably are: +2, +4, +8, +12, +24, +48, then powers of two. On shell, something like: +2 up to 36 +4 up to 108 +12 up to 264 +24 up to 936 and up to 1944... +24 again? Even if we have many +72 (preserving a factor 3^2)... Then, powers of 2. Ĝis, m _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
