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: be...@math.utah.edu -
- 155 S 1400 E RM 233 be...@acm.org be...@computer.org -
- Salt Lake City, UT 84112-0090, USA URL: http://www.math.utah.edu/~beebe/ -
-------------------------------------------------------------------------------
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
