div_qr_1 interface

Torbjorn Granlund tg at gmplib.org
Sat Oct 26 18:51:31 CEST 2013

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

  A long time ago, we choose an interface for sbpi1_div_qr which does
  *not* store the most significant limb; instead it returns it. I think it
  was the intention that a new top-level mpn_div_qr should follow that
  convention, and not store the top limb. I don't remember if that was
  purely for esthetic reasons, or if it also simplified the divide&conquer
  division code.
  Having some of the special division case functions, like mpn_div_qr_1,
  storing the top quotient limb leads to unnecessary complications when
  writing the general mpn_div_qr; it forces mpn_div_qr for n/1 to do the
  top limb itself and call mpn_div_qr_1 with (n-1)/1, which seems like a
  case of bad impedance mismatch.
  But then, requirements for div_qr_1 don't necessarily translate to
  requirements for the primitive division loops we're discussing now.
  For the recent mpn_div_qr_1 and mpn_div_qr_1n_pi1, it turned out to work
  fine to have mpn_div_qr_1 for n/1 do the top quotient limb up front, and
  let mpn_div_qr_1n_pi1 generate n-1 quotient limbs (but n-1 *full* limbs,
  since we pass in a high u limb, reduced to uh < d).
  It's unclear to me if the best design for the unnormalized case is to
  follow mpn_div_qr_1n_pi1 or not. It get be clearer after writing a
  decent mpn_div_qr_1u_pi1.
Thanks, this all make sense to me now.  :-)

I think it will not be too hard to adapt the new pi2 code; moving the
current after-loop code to before the loop will probably make the
structure best.  At least the 1n variant.

The 1u case is a bit trickier.  Here, we will always have a final
quotient limb which depends on a remainder limb and a partial dividend


More information about the gmp-devel mailing list