bdiv vs redc

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> As currently writtem this is a pure generalisation of redc_1; the
> dividend and divisor have separate sizes.  The remainder is of redc_1
> type, with carry returned, not borrow.

This may be a little subtle. The redc code (and this loop) computes

  R B^{qn} = N + Q D

with Q of size qn. The bdiv convention is to return

  R' B^{qn} = N - Q' D

also with Q' of size qn. The common case is to have

  Q' = B^{qn} - Q, R' = R - D

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.

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?

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).

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

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.