bdiv vs redc

[Torbjorn Granlund]

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

  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.
  
Ah.  This makes some sense.

  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.
  
Yes, I am aware of these similarities (or at least, I *was* aware of it
when we worked on the perfpow code).

An mpn_remove_1 makes sense.

We should also extract the Hensel nth root and nth square root from
mpn/generic/perfpow.c, and put them in their own files.  (Some typing
cleanup might be asked for.)

-- 
Torbjörn