Do we have all needed gcd_11 so we can switch to using it, without
performance regressions?
Attached patch updates the small-number cases at the end of mpn_gcd.
This code would get simpler if we allowed one even input to gcd_11 and
gcd_22.
Regards,
/Niels
*** /tmp/extdiff.5QAq5X/gmp-gcd_11.731706bff51e/mpn/generic/gcd.c 2019-08-17 00:59:04.000000000 +0200
--- /home/nisse/hack/gmp-gcd_11/mpn/generic/gcd.c 2019-08-17 17:31:06.382864651 +0200
*************** mpn_gcd (mp_ptr gp, mp_ptr up, mp_size_t
*** 218,231 ****
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);
--- 218,223 ----
*************** mpn_gcd (mp_ptr gp, mp_ptr up, mp_size_t
*** 233,256 ****
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;
- ctx.gn = 1 + (g.d1 > 0);
- }
done:
TMP_FREE;
--- 225,266 ----
ASSERT (up[0] & 1);
! /* FIXME: Would be simpler if mpn_gcd_11 and mpn_gcd_22 allowed one even input. */
! if (LIKELY (n == 2))
{
! mp_double_limb_t g;
! mp_limb_t v0 = vp[0];
! mp_limb_t v1 = vp[1];
!
! if (UNLIKELY (v0 == 0))
! {
! v0 = v1;
! v1 = 0;
! }
! if ((v0 & 1) == 0)
! {
! int c;
! count_trailing_zeros (c, v0);
! v0 = (v0 >> c) | (v1 << (GMP_LIMB_BITS - c));
! v1 >>= c;
! }
! g = mpn_gcd_22 (up[1], up[0], v1, v0);
!
! gp[0] = g.d0;
! gp[1] = g.d1;
! ctx.gn = 1 + (g.d1 > 0);
}
! else
{
! mp_limb_t vl;
! int c;
!
! ASSERT (n == 1);
! vl = vp[0];
! count_trailing_zeros (c, vl);
!
! *gp = mpn_gcd_11 (up[0], vl >> c);
! ctx.gn = 1;
}
done:
TMP_FREE;
--
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
