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