New mulmod_bknp1

[Marco Bodrato]

Ciao,

Il 2022-02-23 12:35 Marco Bodrato ha scritto:
> ... then maybe I was wrong when I wrote that we should not trade a
> factor 3 with a factor 2...

Yes, I think I was wrong. I pushed to the repository the use of the 
_bknp1 (mod B^kn+1) code on the +1 side of the _bnm1 multiplication code 
(mod B^2n-1).

And here are the measures by tune/speed on our development machine 
"shell".
The _rounded measures use a larger size, rounded to some multiple of 
some power of two. Actually, they are not faster than the non-rounded 
size. Moreover, before the patch the _rounded cost was monotonous, now 
it's not.
The rounding strategy needs a revision.

[bodrato at shell ~/gmp-repo]$ /var/tmp/bodrato/gmp/hg/build/tune/speed 
-p100000000 -s 72-900 -rc -t36 mpn_mulmod_bnm1_rounded mpn_mulmod_bnm1
overhead 5.84 cycles, precision 100000000 units of 2.86e-10 secs, CPU 
freq 3500.09 MHz
     mpn_mulmod_bnm1_rounded mpn_mulmod_bnm1
72            4939.99       #0.9984
108          10049.80       #0.9249
144          12718.57       #0.9997
180          22397.62       #0.8529
216          23185.73       #0.9993
252          36533.91       #0.8669
288          34125.65       #0.9981
324          56029.22       #0.8225
360          48846.70       #0.9999
396          63004.78       #0.9731
432          61179.69       #0.9996
468          95840.50       #0.8255
504         #80506.97        1.0001
540         113637.14       #0.8538
576         #92016.26        1.0002
612         127849.99       #0.9169
648        #115918.53        1.0000
684         161355.14       #0.8673
720         130868.85       #0.9980
756         166164.06       #0.9613
792         197147.66       #0.7897
828         196738.21       #0.9304
864         212050.34       #0.9630
900         217971.55       #0.9548

Ĝis,
m

-- 
http://bodrato.it/papers/