bdiv vs redc

[Niels Möller]

nisse at lysator.liu.se (Niels Möller) writes:

> Some other test cases fail, though: t-root, t-perfpow, t-divis, and
> t-cong. I'm not familiar with this code, I had a quick look at the root
> code but didn't see any obvious dependency on bdiv.

Found it, it's the divisibility check in perfpow.

With the old bdiv convention, we had that D divides U iff R == 0.
With the new convention, the divisibility test is the more complicated

  cy == 0 && (R == D || R == 0)

where the R == 0 case can happen only if U == 0. So if it is known a
priori that U != 0, then the test can be simplified to just

  R == D.

I also noted that there's some similarity between perfpow and remove,
maybe we should have an mpn_remove_1, and use that from perfpow? And
differences, remove.c uses mpn_bdiv_qr for divisibility tests (and keeps
the quotient in case the division is exact), while perfpow calls
mpn_divisible_p which in turn calls mpn_*_bdiv_qr.

Regards,
/Niels

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