bdiv vs redc
Niels Möller
nisse at lysator.liu.se
Fri Jun 29 11:02:02 CEST 2012
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.
More information about the gmp-devel
mailing list