Faster integer remainder

[Nelson H. F. Beebe]

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

with a blog at 

	https://lemire.me/blog/2019/02/08/faster-remainders-when-the-divisor-is-a-constant-beating-compilers-and-libdivide/

and C and Go code at

	https://github.com/lemire/fastmod

Their algorithms are applicable to remainder computation, as well as
to exact divisibility tests, to repeated integer divisions by a
constant denominator, and to compile-time integer division by
constants.

They include studies on ARM, POWER8, and x86-64 CPUs, with correctness
proofs, and software implementations in C.  The latter require support
for 128-bit integer arithmetic (that is, twice the precision of that
of the longest commonly used integer type), so they may not be
applicable to other CPU designs.

On all tested systems, their new algorithms are up to 50% faster than
current state-of-the-art ones used by gcc and clang, and faster than
hardware remainder instructions on some systems.

-------------------------------------------------------------------------------
- Nelson H. F. Beebe                    Tel: +1 801 581 5254                  -
- University of Utah                    FAX: +1 801 581 4148                  -
- Department of Mathematics, 110 LCB    Internet e-mail: beebe at math.utah.edu  -
- 155 S 1400 E RM 233                       beebe at acm.org  beebe at computer.org -
- Salt Lake City, UT 84112-0090, USA    URL: http://www.math.utah.edu/~beebe/ -
-------------------------------------------------------------------------------