nisse at lysator.liu.se
Sat Sep 7 11:57:19 UTC 2019
tg at gmplib.org (Torbjörn Granlund) writes:
> nisse at lysator.liu.se (Niels Möller) writes:
> The current _METHOD 3 code starts with
> if (UNLIKELY ((d0 >> (GMP_LIMB_BITS - 3)) != 0)
> || UNLIKELY (n0 >= (d0 << 3)))
> The first condition isn't that unlikely, though, and will get less
> unlikely when we change hgcd2 to use div1 in some way also for the
> double limb loop. Since the first few iterations of hgcd2 work with
> numbers close to filling two limbs.
> I thought 2-3 of about 40 iterations would suffer from that condition.
> Don't you agree?
Something like that (not sure what the typical iteration coount is), so
one or two mispredicted branches and unnecessary div instructions per
> Coulds do the shifting in the other direction instead:
> t = n0 >> 2;
> mask = -(mp_limb_t) (t >= d0);
> The quotient might be underestimated, cannot it?
I don't think so, n0 >= 4*d0 if and only if floor(n0/4) >= d0. So this
quotient bit isn't affected by low n0 bits. But they have to be taken
into account for the other two quotient bits.
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel