Faster integer remainder

[Niels Möller]

"Nelson H. F. Beebe" <beebe at 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.