Faster integer remainder

Nelson H. F. Beebe beebe at
Mon Oct 14 13:02:52 UTC 2019

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

A preprint PDF file is available at

with a blog at

and C and Go code at

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

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  -
- 155 S 1400 E RM 233                       beebe at  beebe at -
- Salt Lake City, UT 84112-0090, USA    URL: -

More information about the gmp-devel mailing list