Ciao, Il Dom, 1 Settembre 2019 11:54 pm, Torbjörn Granlund ha scritto: > "Marco Bodrato" <bodr...@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/ _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
