A C/C++ header file for fast 32-bit division remainders (and divisibility tests) on 64-bit hardware.
Branch: master
Clone or download
Latest commit 1aa0dfc Feb 19, 2019
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
docs Preparing. Feb 8, 2019
include Documenting further the 64-bit functions. Feb 19, 2019
tests Documenting further the 64-bit functions. Feb 19, 2019
.gitmodules Remove uint256_t submodule. Feb 12, 2019
.travis.yml Adding travis file. Feb 9, 2019
LICENSE Preparing. Feb 8, 2019
Makefile Documenting further the 64-bit functions. Feb 19, 2019
README.md Update README.md Feb 20, 2019

README.md

fastmod

Build Status

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:

Usage

We support all major compilers (LLVM's clang, GNU GCC, Visual Studio). Users of Visual Studio need to compile to a 64-bit binary, typically by selecting x64 in the build settings.

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.

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.


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

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

(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.