gcd_22

Torbjörn Granlund tg at gmplib.org
Tue Aug 27 08:40:42 UTC 2019


nisse at lysator.liu.se (Niels Möller) writes:

  And to make the loop work, it needs some condition to decrement N and
  maintain non-zero high limbs (if both up[N-1] and vp[N-1] are zero,
  comparison is no good). So that would be something like

Since N is my proposal is a constant, it is considered bad practice to
decrement it.

Instead i expect deflection to a loop handling N-1.

Besides, I am not sure you got the decrementation criteria exactly
right. ;-)

  Back when the current gcd code was written, I think it won against the
  accelerated binary gcd also for small sizes, and that's why we didn't
  introduce any lehmer-vs-binary threshold.

I believe we will be able to beat the old "accelerated binary" code and
the present code with a branch-reduced approach.

Reducing the branches should be done next, but it will take some work to
reduce it enough for a significant speedup.  At least that's my
understanding.

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


More information about the gmp-devel mailing list