gcd_22

[Niels Möller]

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

> Some messages ago, Niels suggested that discarding the smallest number
> keeping the largest one in some unlikely case could be a good idea.

I think that is ok provided the numbers are close...

> I did not completely understand what he meant... But here I can see his
> suggestion was quite clever.
> I'd suggest
>   if (UNLIKELY (cy)) { mpn_neg(up,up, N-1); up[N-1] = 0; }
> without jumping back... :-)

Including in this case, since if I understand it correctly, it can
happen only when the high limbs are equal, up[N-1] == vp[N-1], and
that's "close enough", progress should be almost the same.

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

     while (N > 2)
       {
         if (up[N-1] < vp[N-1])
	   swap up,vp
	 cy = mpn_sub_n (up, up, vp, N);
	 if (UNLIKELY (cy)) { mpn_neg(up,up, N-1); up[N-1] = 0; }
	 if (UNLIKELY (up[0] == 0)) {
	   // handle any number zeros including that U = 0
	 }
	 count_trailing_zeros (cnt, up[0]);
	 mpn_rshift (up, up, N, cnt);
	 N -= ((up[n-1] | vp[N-1]) > 0);
       }
     mpn_gcd_22(...);

Would absolutely be interesting to benchmark that against the current
Lehmer code based on hgcd2, to see where the cross-over is. And
preferably benchmarked with respect to size in bits, not size in limbs
(for Lehmer, I suspect three full limbs may need two hgcd2 iterations,
and hence be significantly slower than 3 limbs minus a few bits).

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.

Regards,
/Niels

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