Torbjorn Granlund <t...@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. _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel