Small operands gcd improvements

[Niels Möller]

tg at gmplib.org (Torbjörn Granlund) 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. If both u1 > 0 and v1 > 0 on entry (if gcd_22
require that is unclear), then u1 == 0 impliex v1 > 0.

> We could do a large rightshift outside the loop and then jump back into
> and (ab)use gcd_22 with u1 = 0 xor v1 = 0.  I suspect random operands
> will not see any timing difference.  Don't you agree that u1 / v1 will
> not be too far from 1.0 on average?

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.

To do the same for the unlikely u0 = 0 exit case, we'd need a large
right shift.

I think an explicit gcd_21 loop may be clearer, but unlikely to matter
for performance.

Regards,
/Niels

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