bdiv vs redc

Torbjorn Granlund tg at gmplib.org
Fri Jun 29 11:55:49 CEST 2012

```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
```