Exact division

[Torbjorn Granlund]

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

  With bdiv_q now working, I wrote a simple divexact function, and I use
  it in mpn/gcdext.c where it needs to compute the second cofactor. As a
  result, the GCDEXT_DC_THRESHOLD on shell was reduced from 496 to around
  415. I guess it would be reduced a little more more with a more clever
  bidirectional divexact.
  
I added summary date at the threshold tables, see
<http://gmplib.org/devel/GCDEXT_DC_THRESHOLD.html>.

"cfg/meas avg: 0.80180" means that the average configured threshold
divided by the average measured threshold is 0.80180.  A significant
move of a threshold!

Another threshold that has moved recently is MULMOD_BNM1_THRESHOLD; it
gets cfg/meas avg: 0.92857.  (This is a result of the latest variant of
its "next" function.)

  (There are two problems with mpn/divexact.c: (1) Torbjörn doesn't trust
  the current implementation, and (2) it requires that the divisor is
  odd. Feel free to move the code in mpn/gcdext.c:divexact).

I suggest that we do something like this in generic/divexact.c:

#if 1
Code from generic/gcdext.c:divexact
#else
Existing generic/dvexact.c code
#endif

Then we could make mpz_divexact call mpn_divexact for a nice performance
boost.

-- 
Torbjörn