General mpn_gcd_basecase

[Marco Bodrato]

Ciao,

Il Dom, 1 Settembre 2019 6:35 pm, Torbjörn Granlund ha scritto:
> "Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:

> My code:   1.85 bits/iteration
> Your code: 2.60 bits/iteration

> It is worth remembering the table from my experiments with single-limb
> numbers:

> binary tab64                   :    479879082   0.401    2.495       40
> binary tab256                  :    456126047   0.381    2.625       40
> binary tab1024                 :    434483855   0.363    2.755       36

> The now observed 2.60 bits/iteration is very close to the 2.625
> bits/iteration from the table.

My code uses a 256 table... but extends it to a 1024 one...

What does the "binary tab###" single-limb implementation exactly do?

> (I looked briefly at your code, and don't understand it.  I haven't had
> time for a proper look yet.)

Yes, storing some unused bits in the table was not a good idea for clarity.

I send it again, I changed some variable names, added some comments and
some #ifdef to experiment the different flavours.

I get:
 -DNO_TG_TRICK -DTAB256 -DNLIMBS=10 -DSTAT=1
bits/iteration avg: 2.45

 -DTAB256 -DNLIMBS=10 -DSTAT=1
bits/iteration avg: 2.57

 -DNO_TG_TRICK -DNLIMBS=10 -DSTAT=1
bits/iteration avg: 2.53

 -DNLIMBS=10 -DSTAT=1
bits/iteration avg: 2.60


I added also an "#if 0"-ed bad idea :-)

Ĝis,
m

-- 
http://bodrato.it/papers/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: gcd-tgmb.c
Type: text/x-csrc
Size: 4904 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20190901/7b3244cd/attachment.bin>