Small operands gcd improvements

[Niels Möller]

tg at gmplib.org (Torbjörn Granlund) writes:

> nisse at lysator.liu.se (Niels Möller) writes:
>
>   > Checking u1 = 0 and v1 = 0 separately as you suggest is a different
>   > thing, and it might not have zero cost in the gcd_22 loop.
>
>   I think only the shifted number should be checked, and as the main loop
>   exit condition.
>
> OK, so we agree there!

But on second though, maybe 

  while (u1 | v1)

or

  while (u1 || v1)

is even simpler and efficient enough. Then we need not do anything
special when the first operand gets small enough to fit in one limb.

>   That would probably work fine, but maybe not simpler than an explicit
>   gcd_22. So then the normal case would call gcd_22 with u1 > 0, v1 > 0,
>   and exit the loop with u1 > 0, v1 == 0. I don't see why we'd need a
>   right shift here, I think one could just check if u1 > 0 and if so jump
>   back to gcd_22, and next time the loop exits we will have u1 = 0, v1 =
>   0.
>
> What do you mean by an "explicit gcd_22"?

Sorry, I meant "explicit gcd_21".

Regards,
/Niels

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