hgcd1/2

[Niels Möller]

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
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.