t...@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.
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
