This patch gets rid of the gcd_1 call and instead handles everything
with gcd_11 and gcd_22. It also lifts the operands into registers.
Niels, do you agree with this? Marco?
We discussed a gcd_21 in the past, and here again is a utility for it.
It is behind an UNLIKELY just as it is unlikely within gcd_22, so not
super important. Perhaps gcd_21 is more common as operands directly
from user code.
We surely could make gcd_21 fast now with the table based algorithm; 4
bits per iteration is easy when the operands have different sizes of > 4
bits. Or even binary euclid for machines with fast small quotient
division.
2019-09-09 Torbjörn Granlund <t...@gmplib.org>
* mpn/generic/gcd.c: Rewrite tail of function.
*** /tmp/extdiff.zlppJi/gmp-main.cf5765234af8/mpn/generic/gcd.c Sun Sep 8
21:55:22 2019
--- /home/tege/prec/gmp-main/mpn/generic/gcd.c Mon Sep 9 21:10:41 2019
***************
*** 218,252 ****
ASSERT(up[n-1] | vp[n-1]);
! if (n == 1)
! {
! *gp = mpn_gcd_1(up, 1, vp[0]);
! ctx.gn = 1;
! goto done;
! }
!
! /* Due to the calling convention for mpn_gcd, at most one can be
! even. */
!
if (! (up[0] & 1))
MP_PTR_SWAP (up, vp);
! ASSERT (up[0] & 1);
! if (vp[0] == 0)
! {
! *gp = mpn_gcd_1 (up, 2, vp[1]);
! ctx.gn = 1;
! goto done;
! }
! else if (! (vp[0] & 1))
! {
! int r;
! count_trailing_zeros (r, vp[0]);
! vp[0] = ((vp[1] << (GMP_NUMB_BITS - r)) & GMP_NUMB_MASK) | (vp[0] >> r);
! vp[1] >>= r;
! }
! {
! mp_double_limb_t g = mpn_gcd_22 (up[1], up[0], vp[1], vp[0]);
gp[0] = g.d0;
gp[1] = g.d1;
--- 218,261 ----
ASSERT(up[n-1] | vp[n-1]);
! /* Due to the calling convention for mpn_gcd, at most one can be even. */
if (! (up[0] & 1))
MP_PTR_SWAP (up, vp);
! {
! mp_limb_t u0, u1, v0, v1;
! mp_double_limb_t g;
! u0 = up[0];
! v0 = vp[0];
! if (n == 1)
! {
! int cnt;
! count_trailing_zeros (cnt, v0);
! *gp = mpn_gcd_11 (u0, v0 >> cnt);
! ctx.gn = 1;
! goto done;
! }
!
! ASSERT ((u0 & 1) != 0);
!
! v1 = vp[1];
! if (UNLIKELY (v0 == 0))
! {
! v0 = v1;
! v1 = 0;
! /* FIXME: We could invoke a mpn_gcd_21 here, just like mpn_gcd_22 could
! when this situation occurs internally.
! }
! if ((v0 & 1) == 0)
! {
! int cnt;
! count_trailing_zeros (cnt, v0);
! v0 = ((v1 << (GMP_NUMB_BITS - cnt)) & GMP_NUMB_MASK) | (v0 >> cnt);
! v1 >>= cnt;
! }
!
! u1 = up[1];
! g = mpn_gcd_22 (u1, u0, v1, v0);
gp[0] = g.d0;
gp[1] = g.d1;
--
Torbjörn
Please encrypt, key id 0xC8601622
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
