"Nelson H. F. Beebe" <be...@math.utah.edu> writes: > During a routine, and rather delayed, bibliography update, I found and > read a recent paper that might stimulate rethinking multiple-precision > integer remainder computations in gmp: > > Daniel Lemire and Owen Kaser and Nathan Kurz > Faster remainder by direct computation: Applications to > compilers and software libraries > Software: Practice & Experience 49(6) 953--970 June 2019 > https://doi.org/10.1002/spe.2689 > > A preprint PDF file is available at > > https://arxiv.org/pdf/1902.01961
I've had a look. It seems it's for 1/1 division (signed and unsigned), and the idea is to use an approximate reciprocal (rounded upwards), multiply, and get the remainder from the fraction, while the integer part gives the quotient. GMP's udiv_qrnnd uses the fraction, but doesn't compute it accurately enough to use it to get the remainder directly. And for GMP 2/1 (and 3/2) division is more important than 1/1. I wonder if one could do something along those lines for udiv_rnnd_preinv, i.e., 2/1 division with remainder only. We use the reciprocal v = floor [(B^2 - 1) / d] - B, and compute {q_1, q_0} = u_1 * v + {u_1, u_0} Then q_1 is an approximative quotient, and q_0 is a very crude fraction, This is followed by multiplication q_1 * d and some adjustment steps using q_0. See https://gmplib.org/~tege/division-paper.pdf for details. One could attempt to omit q_1 and instead compute a more accurate q_0 as q_0 = LO(u_1 * v) + u_0 + HI(u_0 * v) and remainder would then hopefully be r = HI(f * d) That's one more multiplication, if I'm not missing something, but possibly less adjustment steps, if it can be made to work. I'd expect it can be made to work if inputs are restricted to a few bits smaller than full limbs, less clear if we get accuracy enough to deal with full limbs. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677. Internet email is subject to wholesale government surveillance. _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel