bdiv vs redc

[Torbjorn Granlund]

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

  Torbjorn Granlund <tg at gmplib.org> writes:
  
  > The quotient might need one more bit using this alternative convention.
  > Right?  We have no great place to return it.
  
  I'd suggest the convention that
  
    Q = -N D^{-1} (mod B^{nn - dn})
    R B^{qn} = N + Q D
  
  Then Q is qn = nn - dn limbs, no extra bit, and
  
    0 <= R < B^dn + D
  
  This is the same as for the current redc functions. But I'm leaning
  towards putting the returned R at the high end rather than the low, and
  with the loop organization you suggest it should then work fine to put Q
  at the low end.
  
Could you perhaps write a new proposed sbpi1_bdiv_qr with the result
normalisation you suggest, using my proposed sbpi1_bdiv_r style?  That
would allow for a single outer loop, unlike the current sbpi1_bdiv_qr.

  Maybe we don't even need bdiv_r then, if
  
    bdiv_qr (up, up, un, dp, dn)
  
  is cheap enough (storing the q limbs at the low end of U).
  
That would be nice.  But cutting even a few constant cycles off redc is
worth it, so "cheap enough" should be taken in a very strict sense...

  Ah, and notation. I suggest we write U for the numerator, rather than N,
  like we have been doing in some other division work. To avoid confusion
  with n used as a limb count (worse when talking than when writing).
  
OK, I started with the header of sbpi1_bdiv_qr and got these variable
names.  (There is a disadvantage with up since up can be confused with
the english word up in comments; up can thereby mess thing up.  :-)

-- 
Torbjörn