General mpn_gcd_basecase
Marco Bodrato
bodrato at mail.dm.unipi.it
Sun Sep 1 23:01:28 UTC 2019
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/
More information about the gmp-devel
mailing list