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