lemire/fastmod

A C/C++ header file for fast 32-bit division remainders (and divisibility tests) on 64-bit hardware.

fastmod

A header file for fast 32-bit division remainders on 64-bit hardware.

How fast? Faster than your compiler can do it!

Compilers cleverly replace divisions by multiplications and shifts, if the divisor is known at compile time. In a hashing benchmark, our simple C code can beat state-of-the-art compilers (e.g., LLVM clang, GNU GCC) on a recent Intel processor (Skylake).

Further reading:

• Faster Remainder by Direct Computation: Applications to Compilers and Software Libraries, Software: Practice and Experience 49 (6), 2019.

Usage

We support all major compilers (LLVM's clang, GNU GCC, Visual Studio). This library only makes sense when compiling 64-bit binaries.

It is a header-only library but we have unit tests. Assuming a Linux/macOS setting:

make
./unit

The tests are exhaustive and take some time.

You can also build the tests using cmake which will work nearly everywhere (including under Windows).

cmake -B build 

To enable the exhaustive tests, do...

cmake -B build -D FASTMOD_EXHAUSTIVE_TESTS=ON

Under Windows, you can run tests as follows:

cmake --build build --config Release
cd build
ctest . --config Release

Users of Visual Studio need to compile to a 64-bit binary, typically by selecting x64 or ARM64 in the build settings. Visual Studio should default on 64-bit builds on 64-bit systems.

Code samples

In C, you can use the header as follows.

#include "fastmod.h"

// unsigned...

uint32_t d = ... ; // divisor, should be non-zero
uint64_t M = computeM_u32(d); // do once

fastmod_u32(a,M,d);// is a % d for all 32-bit unsigned values a.

fastdiv_u32(a,M);// is a / d for all 32-bit unsigned values a, d>1.


is_divisible(a,M);// tells you if a is divisible by d

// signed...

int32_t d = ... ; // should be non-zero and between [-2147483647,2147483647]
int32_t positive_d = d < 0 ? -d : d; // absolute value
uint64_t M = computeM_s32(d); // do once

fastmod_s32(a,M,positive_d);// is a % d for all 32-bit a

fastdiv_s32(a,M,d);// is a / d for all 32-bit a,  d must not be one of -1, 1, or -2147483648

In C++, it is much the same except that every function is in the fastmod namespace so you need to prefix the calls with fastmod:: (e.g., fastmod::is_divisible).

Go version

• There is a Go version of this library: https://github.com/bmkessler/fastdiv

(Speculative work) 64-bit benchmark

It is an open problem to derive 64-bit divisions that are faster than what the compiler can produce for constant divisors. For comparisons to native % and / operations, as well as bitmasks, we have provided a benchmark with 64-bit div/mod. You can compile these benchmarks with make benchmark. These require C++11. It is not currently supported under Visual Studio.

fastmod's Issues

Error for MSVC (__umulh is not a constexpr function)

See here: https://godbolt.org/z/bjYn1s

It does not compile because __umulh is not a constexpr function...

Allow signed 32 bit division on MSVC

If I am not wrong, __mulh is available on MSVC, would it be possible to use this for MSVC to allow 32 bit signed division?

I am not in the possession of MSVC so I cannot test this, but the change would be trivial

Typo in fastmod.h

In #3 I introduced a typo at line 9 in fastmod.h, <cstding> should be <cstdint>, I'm not sure how that escaped me. (I didn't open a pull request for this as I felt it was rather overkill for this thing.)

Why use 128-bit integers for 32 bit operations?

The code seems to be using 128 bit operations for the 32 bit code:

fastmod/include/fastmod.h

Lines 45 to 47 in bb334d0

	FASTMOD_API uint64_t mul128_u32(uint64_t lowbits, uint32_t d) {
	return ((__uint128_t)lowbits * d) >> 64;
	}

fastmod/include/fastmod.h

Lines 86 to 89 in bb334d0

	// fastdiv computes (a / d) given precomputed M for d>1
	FASTMOD_API uint32_t fastdiv_u32(uint32_t a, uint64_t M) {
	return (uint32_t)(mul128_u32(M, a));
	}

However, unless I am mistaken, this can all be done with only 64 bit integer operations:

1. Break M into 32 bit chunks h and l
2. The high-64 bit chunk of the 128 bit multiplication u128(M) * a should be exactly the same as (u64(h) * u64(a)) >> 32

Label	128-97	96-64	64-33	32-1
M			h	l
a			0	a
out1			[la	la]
out2		[ha	ha]
out3		[0	0]
out4	[0	0]
result	0	high32(h*a)	high32(la) + low32(ha)	low32(l*a)
		^ What we want

Edited as I originally had the 0s from the multiplication in the wrong columns.

`fastdiv_s64()` and `fastmod_s64()` appear to be missing?

I can see there is an implementation for computeM_s64() here, but it appears this function is not being used anywhere in the repo.

What's more, I cannot seem to be able to find any references to either fastdiv_s64() or fastmod_s64().

Division by 1 returns 0

When d is 1, the computation in computeM_u32 overflows to 0:

fastmod/include/fastmod.h

Line 77 in 82f9506

return UINT64_C(0xFFFFFFFFFFFFFFFF) / d + 1;

Then M is 0, and fastdiv_u32(a,M) returns 0 for any a (fastmod_u32(a,M) works correctly, as a % 1 == 0).

Unnamed namespace causes ODR violations in C++

Putting everything in an unnamed namespace means that your header can't safely be used by templates or other code in headers. If a function template or inline function that uses fastmod is used in two different translation units the two copies of the function will call different versions of fastmod in different unnamed namespaces, which breaks the One-Definition Rule and so has undefined behaviour. With C++20 Modules this is likely to be diagnosed and fail to compile.

not portable to MSVC

__uint128_t is not available on msvc.

Perhaps replace the __uint128_t stuff with custom implementation?

Looks like all it needs to implement is mul(128,32)

Can skip the right shift, just grab upper 64 bits

comment fix

at line 86 of fastmod.h

// fastmod computes (a / d) given precomputed M for d>1

should read

// fastdiv computes (a / d) given precomputed M for d>1

Best,
Jeffrey Sarnoff