Division interfaces

Torbjorn Granlund tg at gmplib.org
Mon Feb 28 23:07:31 CET 2011

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

  What are the current plans for retiring the divrem_1 interface? IIRC, we
  agreed there should be an interface more or less like
    div_qr_1 (mp_ptr qp, mp_limb_t *qh, mp_srcptr up, mp_size_t un,
  	    mp_limb_t d);
  and then preinv versions and separate functions for generating fraction
  It would be easier to commit my new div_qr_1 code after this interface
  change (if it's going to happen, that is).
I suppose it got stuck in the great complexity emerging from all our
ideas in the area.

I have lots of code, including assembly code, implementing the new
preliminary division interface.  But your new 'pi1-b' precomputation
will need to be put between the pi1 and pi2 routines.

  And then we have the issue of unnormalized divisors (it looks like
  mpn_sbpi1_div_qr still requires that dp[dn-1] has the high bit set. I'm
  afraid that's going to be a bit of work. I think the strategy should be
  to normalize high limbs (the inputs to the 3/2 division) on the fly, 

We surely need to compute the needed inverse from normalised operands.
Perhaps one could actually apply 3/2 division w/o normalising the 3 + 2
limbs, at the expense of more quotient limb overesimates?

  then do the book-keping needed when doing the mpn_submul_1 calls with
  unnormalized arguments.
I don't get this part.


More information about the gmp-devel mailing list