Use on small mulmod_bnm1 [was: New mulmod_bknp1]

[Marco Bodrato]

Ciao,

> Il 2022-02-15 11:48 Marco Bodrato ha scritto:
>> I pushed some new functions to compute the product (and square) modulo
>> B^nn+1, for small values of the exponent nn.

Currently that code is used by two functions.
One is mulmod_bnm1, because of the patch named 
"mpn/generic/mulmod_bnm1.c: Use mulmod_bknp1, on the bnp1 side." 
available at
https://gmplib.org/repo/gmp/rev/6ff25532f2a4

What's the actual effect of that change?
I attach an image (fakte_18319.png), giving the relative speed of the 
code after/before the patch. There are two measure-runs, but they are 
almost the same. For some size there is a 5-10% (even 20%) speed-up, for 
the next size there is nothing. A very "noisy" (not random) effect.

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

I attach another image (eble_18319.png) with an estimate of the shape of 
the expected gain if "the best size" is chosen for every multiplication.
Of course everything would get much smooter.

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...

A third image (ambaux_18319.png), simply shows both the current, and the 
estimated values.

Ĝis,
m
-------------- next part --------------
A non-text attachment was scrubbed...
Name: fakte_18319.png
Type: image/png
Size: 93833 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20220415/1d68da8e/attachment-0003.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: eble_18319.png
Type: image/png
Size: 53269 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20220415/1d68da8e/attachment-0004.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ambaux_18319.png
Type: image/png
Size: 118854 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20220415/1d68da8e/attachment-0005.png>