"Marco Bodrato" <bodr...@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.
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
