General mpn_gcd_basecase

[Marco Bodrato]

Ciao,

Il Dom, 1 Settembre 2019 11:54 pm, Torbjörn Granlund ha scritto:
> "Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:
>
>   My code uses a 256 table... but extends it to a 1024 one...
>
>   What does the "binary tab###" single-limb implementation exactly do?
>
> Here is the program which generated it all:

Great!

So, tab256 uses a table where almost all of the entries are negative,
except 1 and 3.
And it gets
Algorithm                         Iterations  Iter/Bit  Bit/Iter  Max iter
binary tab256                  :     40429598   0.381    2.625       40

With the MASK_ADJUST trick I just posted, the code I sent, compiled with 
-DTAB256 -DNLIMBS=10 -DSTAT obtains:
bits/iteration avg: 2.67

which is not bad, and with some bit trickery can be obtained with a
64-chars table only (or 32, if we store 4+4 bits in each char).

The subtract-only variant can be emulated with -DTAB_VARIANT=16, that way
your code uses an all negative table, and gives:
Algorithm                         Iterations  Iter/Bit  Bit/Iter  Max iter
binary tab256                  :     42336979   0.399    2.506       45


My other variant should be compared with tab1024, even if it actually
needs a table with only 256 chars... (here each entry has 5 meaningful
bits, further compression is too tricky)

In your program, the subtract-only variant can be emulated with
-DTAB_VARIANT=32, that way your code uses an all negative table, and
gives:
Algorithm                         Iterations  Iter/Bit  Bit/Iter  Max iter
binary tab1024                 :     42714649   0.403    2.484       47

With a more balanced table it gets:
Algorithm                         Iterations  Iter/Bit  Bit/Iter  Max iter
binary tab1024                 :     38517021   0.363    2.755       35

With my latest variant I get
bits/iteration avg: 2.71
with a code that unconditionally uses submul.

> It takes some time to grasp these bit trickery, no critique against your
> code style intended!

I know, but adding some comment when discussing is a good idea anyway. :-)

Ĝis,
m

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