Faster integer remainder

[paul zimmermann]

> "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

after having a closer look, the main idea of that paper (Theorem 1) already
appears in Bernstein's "scaled remainder tree" paper [1].

Indeed, the assumption of Theorem 1 says that c' = c/2^{N+L} is a good
approximation of 1/d. Then if n = qd + r, the fractional part of c'n is
close to r/d, and multiplying by d reveals r.

More precisely, here is a 4-line proof of Theorem 1, assuming n = qd + r:

(1) we have 1/d <= c' := c/2^{N+L} <= 1/d + 1/(d 2^N)
(2) it follows  q+r/d <= c'n <= q + r/d + n/(d 2^N)
(3) thus r/d <= frac(c'n) <= r/d + n/(d 2^N) < (r+1)/d
(4) then r <= frac(c'n)*d < r+1

Paul Zimmermann

[1] cr.yp.to/arith/scaledmod-20040820.pdf