Small operands gcd improvements

Niels Möller nisse at
Tue Aug 6 13:26:36 UTC 2019

tg at (Torbjörn Granlund) writes:

> We cannot enforce both to be zero.  Just imagine that our great divisor
> is greater than GMP_NUMB_MAX.  :-)

For that case, we'll get u1 = v1 > 0, u0 = v0, and will trigger the
unlikely u0 == 0 check between subtraction and count_trailing_zeros. So
proper exit can be handled as part of the unlikely code path.
> The primary exit condition needs to be simple for performance (but one
> might perhaps reenter the loop if a secondary exit condition is unmet).


  while (u1 || v1) 

will do precisely that ;-) If we just put the || operands in the right
order (u1 should be the high limb of the number just shifted).


Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.

More information about the gmp-devel mailing list