General mpn_gcd_basecase

[Torbjörn Granlund]

"Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:

  Before you wake up, I send you another version. I added two more bits to
  the table entries, and started using one with some bit trickery
  (exploiting symmetries). It should be able to gain a bit of "speed", but
  in the unlikely  case of operands of very different sizes only.

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:

Algorithm                         Iterations  Iter/Bit  Bit/Iter  Max iter
plain binary                   :    834306161   0.697    1.435       59
binary+-                       :    726936855   0.607    1.647       58
binary+- alternating           :    925657708   0.773    1.293       70
binary tab4                    :    731982593   0.611    1.635       58
binary tab16                   :    528194771   0.441    2.266       42
binary tab64                   :    479879082   0.401    2.495       40
binary tab256                  :    456126047   0.381    2.625       40
binary tab1024                 :    434483855   0.363    2.755       36
binary tab4096                 :    427124147   0.357    2.803       36
plain euclides                 :    690890073   0.577    1.733       63
euclides binary                :    435552015   0.364    2.748       40
euclides 2-choice binary       :    412937954   0.345    2.899       37

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

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


-- 
Torbjörn
Please encrypt, key id 0xC8601622