t...@gmplib.org (Torbjörn Granlund) writes: > ni...@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 hgcd2 call. > 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. 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
