Use on large mul_fft [was: New mulmod_bknp1]

[Marco Bodrato]

Il 2022-04-15 19:56 Marco Bodrato ha scritto:
> 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,

The second one is mul_fft, thanks to the patch named 
"mpn/generic/mul_fft.c: Use _bknp1," [...], available at
https://gmplib.org/repo/gmp/rev/f9cbcda05f7e

I attach an image (fakte+eble_18327.png), showing the relative speed of 
the
code after/before the patch.

The green line represents the gain with the current code. The orange one 
is estimated, using not the actual time of the function for a given 
size, but the best timings among the usable sizes.

Even if also for this range we see the effect "interesting improvement 
for some sizes, no news for some other sizes", the graph is not so 
"noisy".

The two lines (green, and orange) show more or less the same shape. 
Working on a better criteria to choose the mulmod size for large sizes 
is probably not worth doing.
Maybe something can be done on the FFT side? I didn't try.

Ĝis,
m
-------------- next part --------------
A non-text attachment was scrubbed...
Name: fakte+eble_18327.png
Type: image/png
Size: 71690 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20220416/21b26286/attachment-0001.png>