General mpn_gcd_basecase

[Niels Möller]

tg at gmplib.org (Torbjörn Granlund) writes:

>   If your willing to have both count_leading_zeros and
>   count_trailing_zeros in the loop, maybe it's simpler and more efficient
>   with a table-based binary euclid?
>
>     CND_SWAP
>     count_leading_zeros(cnt, up[n-1] | vp[n-1])
>     q = tab[...high bits...]
>
>     if (q odd)
>       u <-- u - q v
>     else
>       u <-- (q+1) u - v

Sorry for the confusion, this should have been

        u <-- (q+1) v - u

>     count_trailing_zeros(cnt, up[0]);  /* At least one */
>     u >>= cnt;
>
> I don't follow the u assignment in the else clause.  And even*odd-odd
> would seem to become odd.

Let's assume u, v odd, and q = floor(u/v), even though the table-based
code would involve some approximation. Let r = u - qv, then 0 <= r < v.

If q is odd, then r is even (odd - odd x odd), and we set u <-- r. If q
is even, then r is odd, and we use v - r which is even and positive. And

  v - r = (q+1) v - u.

Since q+1 is odd, this is odd x odd - odd.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.