hgcd1/2

[Niels Möller]

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

> What are the specs for div2?
>
> Surely n1 > 0 and d1 > 0.

All variants need d1 > 0, method 2 also needs n1 > 0 (for
count_leading_zeros).

> Also N >= D?

Method 2 needs clz(n1) <= clz(d1). Besides that, I think they can handle
N < D, i.e., q == 0.

> Does the new div2 always compute the "accurate" quotient,
> i.e., with the remainder R < D?

Yes. If the adjustment step in methos 1 were skipped, it would still
give R < D, but occasionally underflow with R < 0.

> I'm asking as I believe strongly in unit testing of these types of
> non-trivial idioms.  :-)

Unit tests would be nice. I think the tests/mpz/t-gcd.c does exercises
the large quotient cases.

BTW, I wonder if it makes sense with HGCD2_DIV2_METHOD == 3 similar to
HGCD2_DIV1_METHOD == 3, with special handling of q <= 7 but no looping?

Regards,
/Niels

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