bdiv vs redc
nisse at lysator.liu.se
Mon Jul 16 16:52:30 CEST 2012
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.
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel