bdiv vs redc

[Torbjorn Granlund]

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

  also with Q' of size qn. The common case is to have
  
    Q' = B^{qn} - Q, R' = R - D
  
Missing a B^{qn} there at the end, I suppose.

  so you only need a subtraction. But it breaks for the special case N = 0
  (mod B^{qn}), because then R' = R and Q = Q' = 0. And making the
  subtraction conditional defeats the design with a common redc/bdiv_r
  useful for both powm and powm__sec.
  
  Some alternatives:
  
  1. Change the bdiv convention.
  
Seems like a good idea with our goals today, but it might have bad
effects in other parts of the library.

The quotient might need one more bit using this alternative convention.
Right?  We have no great place to return it.

  2. Switch to using submul_1 in the loop (making it more analogous to
     euclidean loop). But that's a slowdown on some platforms, right?
  
Bad idea, for the reason you mention, and since we cannot make
redc_2/sbpi2_bdiv_* using submul_2 (which we don't have, and should not
introduce IMO).

  3. Do the subtraction unconditionally, and live with the strange results
     in corner cases:
  
       If N = 0 (mod B^{qn}), we get R = B^{-qn} N - D, rather than B^{-qn}
       N as one would expect.
  
       And if N = 0, we get R = -D, which is just outside of the expected
       range -D < R < B^{dn}.
  
     Users which care can process trailing zero limbs before calling
     bdiv_r, and not call it at all if N = 0 (mod B^{qn}).
     
  If (2) is ruled out for performance reasons, I think I'd prefer (1) even
  if that's an interface change (but only for internal functions, I
  hope?). redc is the most important application, and switching the sign
  of Q will simplify also the other sb_bdiv loops. Ah, and doing the R' =
  R - D subtraction at all is a slowdown for redc, which is another
  argument for (1).
  
I agree.

  Are there any bdiv users for which the interface change (1) causes
  serious trouble?

We haven't documented these functions, AFAIK.

-- 
Torbjörn