# Division by constant unsigned integers

Most modern processors have an integer divide instruction which, for technical reasons, is very slow compared to other integer arithmetic operations. When the divisor is constant, it is possible to evaluate the result of the division without using the slow division instruction. Most optimizing compilers perform this optimization, as can be seen on Matt Godbolt’s compiler explorer. This article tries to be a self-contained reference for optimizing division by constant unsigned divisors.

There are tricks to make division by some special divisors fast: A division by one can be ignored, a division by a power of two can be replaced by a bit shift. A more general trick exists: By using fixed-point arithmetic, we can speed up division by all constant divisors. However, this is not simple to explain, and for this reason I will focus only on positive (or 'unsigned') divisors in this article. For a number (also called the dividend) and a divisor , I assume that we are interested in the quotient .

When it is necessary to repeatedly divide floating-point numbers by the same constant , it is often preferred to precompute the floating-point number and multiply by this instead. This is usually a lot more efficient. We can do something similar for integers by using fixed point arithmetic. The basic idea is to pick a large constant that is easy to divide by. In decimal you can take some power of ten, in binary you would take a power of two so that we can divide by using bit shifts. If we would have we would have . However, is usually not an integer, and we need to round. Still, if we still expect that .

In the following section, I'll discuss the mathematical background. In the sections after that, I'll discuss optimization of division by unsigned integers.

## Mathematical background

### Preliminaries

I will assume that we are working on an -bit machine which can efficiently compute the full -bit product of two -bit unsigned integers. I will use the notation for the set of unsigned integers that can be represented with bits:

I will use the notation to denote the integer in the range that is equivalent to modulo . That is, is the unique integer such that

for some .

### Unsigned division

For a given divisor , we now want to have an expression that evaluates to for all . We have two demands for this expression:

1. It should be correct, that is, the expression is equal to
2. It should be efficient to evaluate. For our purposes, this means that we want to multiply numbers of at most bits, so that they fit in a single register on our -bit machine, and that we implement the division by with a bit shift.

Guided by these demands, we can start our analysis. The following lemma will be useful:

Lemma 1: Suppose that with . If then .

Proof: We have for some nonnegative integer . So . It follows that , so that .

At this point, we have decided that we want an expression that evaluates to . In the introduction, we have established that when

then

So, it is natural to take with as our starting point, since we know that . We now need to decide how exactly to pick and . The obvious choice for are the integers that minimize the error to , which are and . Note that when is not a power of two and put , we have , so this is not a viable method. So, let's round up instead.

This gives us the round-up method, which approximates by with .

First, we determine the conditions under which the round-up and round-down method produce the correct result. Note that from this point on we will assume that is larger than . We will assume and use and interchangeably.

Now, we establish under which conditions the round-up method is correct. The following theorem can be used to derive a condition under which the round-up method is correct, that is, for all .

Theorem 2: Let be nonnegative integers with . If there exists an with

then

Proof: Multiplying the inequality by we get

For all we have , so that . It follows that

By lemma 1, it follows that for all .

Corollary (correctness of the round-up method): Let with and . If we have for all . If then there exists no such that .

Proof: Note that is simply the first multiple of that is greater than or equal to . So the bound is always satisfied. If we have , then satisfies the condition of theorem 2 and we have for all . If we have , the first multiple that is greater than or equal to is larger than . This means that there is no multiple of in the range , and that there exists no such that .

Let's do some examples to see how we can use the round-up method in practice.

Example: Let's take , . First, we try and compute . We have . So we increase to one and try again. This time we get . We have . So the condition of the corollary is satisfied and for any 8-bit unsigned integer we have . Note that fits in bits.

Example: Let's take , . First, we try and compute . We see that . So we increase to one and try again. This time we get . We see that . Again, we increase to two and check the bound again: , and . Increasing to four, we get , and . So the condition of the corollary is satisfied and for any 8-bit unsigned integer we can have . Note that does not fit in bits, which makes the multiplication inefficient on -bit processors.

This last example shows that does not always fit in bits. The following theorem shows that always fits in bits.

Theorem 3: Let and define . Then and for all .

Proof: The range consists of consecutive numbers. We have , so and there must be a multiple of in this range. Since is simply the first multiple greater than or equal to , this is a multiple of in this range. By theorem 2, it follows that for all . In the proof of lemma 6 we saw that . By multiplying both sides by two and rounding up, we see that we have , so .

One way to handle the case when does not fit in bits, is to use the following trick from [1] to multiply by an -bit constant: We can evaluate by defining and using the following code:

uint high_word = (((big_uint)m') * n) >> N;
uint result = (high_word + ((n - high_word) >> 1)) >> (l - 1);


The reason for mentioning this method is mainly that it is used by some compilers. We will now focus on a variation of the round-up method that will usually be more efficient. Instead of rounding up , we can round down but increase .

This gives us the round-down method, which approximates by by .

We proceed as we did for the round-up method, by deriving a condition under which the method is correct.

Theorem 4: Let be nonnegative integers with . If there exists an with

then

Proof: Multiply the inequality by to get

Looking at the expression on the left side, we have , so that . It follows that , so

for all . So lemma 1 applies and we have for all .

When using the round-up or round-down method, we want to be an -bit number in order for the multiplication to be efficient. As we have seen, such an does not always exist. Let us call divisors for which such an exists efficient. The following definition makes this rigorous.

Definition: We call a positive divisor efficient for the -bit round-up method (or round down method) if there exists an such that for all . Likewise, we call a positive divisor efficient for the -bit round-down method if there exists an such that for all .

The following result tells us that is the biggest value for that we can pick so that and still fit in bits.

Lemma 5: Let and define . Now

That is, the binary representations of and have exactly bits.

Proof: We have . Since the floor function is a nondecreasing function and we have . It remains to show that .

When , it follows that and the bound holds. When , the ratio is maximized over by , so (this last inequality can be seen by multiplying both sides by ). So we have ; multiplying both sides by gives . After rounding up both sides, it follows that .

The following result states that we can combine the round-up and round-down method to a method that works for any positive divisor. So this finally concludes our quest for an efficient method to calculate the quotient .

Theorem 6: Any positive divisor is either efficient for the -bit round-up method, or efficient for the -bit round-down method.

Proof: Set . By lemma 6, we know that . Now consider the range . This is a range of numbers. Since there must be at least one multiple of in this range. When this multiple satisfies the condition for the round-down method is satisfied. Since , is efficient for the -bit round-down method. Otherwise, we have and the condition for the round-up method is satisfied. Again, since we have that is efficient for the -bit round-up method.

The following result gives a more efficient condition to check if a given divisor is efficient for the round-up method.

Lemma 7: Let be a positive integer, , and . If then is efficient for the round-up method.

Proof: The product is the first multiple of that is equal to or larger than . This product will be of the form for some , so we have . It follows that if and only if .

Armed with these results, let's do the examples from before again:

Example: We set and compute . We have . So is efficient for the 8-bit round-up method and we have for all .

Example: We set and compute . We have . So is not efficient for the 8-bit round-up method. According to theorem 6, it must be efficient for the 8-bit round-down method, so we have for all .

As mentioned before, the round-up method is more efficient. For even divisors that are not efficient for the roundup method, there exists a trick. Say . Then we can put and evaluate as . This has the benefit that has at most bits.

Lemma 8: Let be positive integers, and let for some positive integer . Define and . Now for all with and .

Proof: Define and . Now we have . Using theorem 3, we see that for every . Since whenever , this holds for every .

Example: Take , . Setting we get . We see that . So is not efficient for the roundup method. However, it is even, so using lemma 8 with we get , . We see that with for all .

On some architectures it is faster to shift by fewer bits. So, for the purpose of optimization, we might be interested in finding the smallest such that satisfies the condition of theorem 2 (or the smallest). Surprisingly, there is an easy way to find the smallest or that satisfies the condition of theorem 2 or theorem 4.

Lemma 9: Let be a positive integer that is not a power of two and let , such that satisfy the condition of theorem 2 (or theorem 4, respectively). If is odd, this is the smallest that satisfies this condition. If is even, also satisfy the condition.

Proof: Suppose that satisfies the condition of theorem 2. In this case, we have . It is easy to see that when is even all expressions in the inequality are even, so we can divide by two and see that . The case for an that satisfies the condition of theorem 4 is analogous.

Suppose that there is a smaller pair that satisfies the condition . By multiplying the whole thing by , we see that . The set has elements. We have (this last inequality holds since is not a power of two), so there can only be one multiple of in this set, which is . So we have , so must be even.

Example: Take , . We compute so . We see that . So is efficient for the round-up method and we have for all . However, we see that is even, so we can reduce by dividing it by two and decrementing . We get , . Now is still even, so again we divide by two and decrement . We get and . So we have for all .

Example: Take , . We set so that . Now , so is not efficient for the -bit round-up method. Since 11 is odd, we use the round-down method. Using theorem 6, we see that 11 is efficient for the -bit round down method. We have so we can use lemma 9 to see that we have .

Example: Take , . We set so that . Now , so is efficient for the round-up method. Now write . Using lemma 9 we see that we have with and for all . So we see that for all . The division by can be implemented by taking the upper bits of the product .

Example: Take , . Taking and , we see that . So 28 is not efficient for the 8-bit round-up method. Applying lemma 8 gives us that with for all . We can now apply lemma 9 to see that with for all . This means that we only have to look at the upper 8 bits, and we need just one shift instruction to compute . So this ends up as efficient as the round-up method, which also needs just one shift and a multiplication.

## Implementation

We distinguish between compile-time optimization and runtime optimization of constant unsigned integers. To illustrate, the divisor d in the following code is a compile-time constant:

	const unsigned int d = 61;

for (int i = 0; i < size; i++) {
quotient[i] = dividend[i] / d;
}


The divisor d in the following code is a runtime constant:

	unsigned int d = read_divisor();

for (int i = 0; i < size; i++) {
quotient[i] = dividend[i] / d;
}


In case of a runtime constant divisor, most compilers will not optimize the division. However, we can do it ourselves, by doing something like:

	unsigned int d = read_divisor();
divdata_t divisor_data = precompute(divisor);

for (int i = 0; i < size; i++) {
quotient[i] = fast_divide(dividend[i], divisor_data);
}


In this section, we will discuss both how a compiler can generated optimized code and how to efficiently implement the precompute and fast_divide functions for runtime constant divisors. The libdivide library, which was started by the author of [3] and [4], is a mature implementation that can optimize division by runtime constant integers. The library is conveniently included in a single header file, contains a nice C++ interface, and also implements vector implementations of integer division, which can make division even faster.

During compile-time, there is a lot of room for optimizations. Typically, programmers are OK with waiting a fraction of a second longer if this means that their code executes faster. So for division by compile-time constants, there is time for extensive optimizations. During runtime, time is more precious, so we want to keep the precomputation reasonably efficient. Further, the fast_divide function is used for all divisors; We want to keep it efficient and, if possible, branchless.

For compile-time optimization, we can spend some more effort to produce better optimized code. For runtime optimization, we need to do the precomputation in runtime, which means that we want the precomputation to be efficient as well. Simply put, for compile-time optimization it will pay off to distinguish many special cases for which we can produce more efficient code. For runtime optimization the challenge is the other way around: We want to have a single, fast code path which handles all cases with good efficiency.

### Runtime optimization

Let's take the example from before as a starting point. I will assume that we have a constant N which denotes the number of bits in the unsigned integer datatype uint. I'll also assume the existence of big_uint, an unsigned integer datatype with bits. Using these datatypes, the example from before becomes:

	uint divisor = get_number_from_user();
divdata_t divisor_data = precompute(divisor);

for (int i = 0; i < size; i++) {
quotient[i] = fast_divide(dividend[i], divisor_data);
}


Both the round-up and the round-down method can be implemented using an expression of the form (n * m + add) >> (N + shift) to compute , so it is natural to define the struct divdata_t with these fields:

typedef struct {
uint mul, add, shift;
} divdata_t;


The fast_divide function is now straightforward to write:

uint fast_divide(uint n, divdata_t dd) {
big_uint full_product = ((big_uint)n) * dd.mul + dd.add;
return (full_product >> N) >> dd.shift;
}


Let's start with the implementation of the precompute function. First, we define a variable divdata to hold the result. I'll save you the trouble and note that the case needs to be handled separately. If we work out this case by hand we see that when we set we get and . While this is mathematically correct, we can't use the fast_divide function to evaluate this expression, because it divides by while the fast_divide function implements this as a right shift by , followed by another right shift. This last right shift would have to be a right shift by negative one. Technically, you could say that this is a right shift by one, but most architectures don't work this way and even if it would, we would lose a bit that has been shifted out by the first shift.

Luckily, we use a trick. If we set both divdata.mul and divdata.add to , things will work out since

So let's write a skeleton for the precompute function that only handles the case :

divdata_t precompute(uint d) {
divdata_t divdata;

// d = 1 is a special case
if (d == 1) {
divdata.mul = max;
divdata.shift = 0;
return divdata;
}

// normal path
...

return divdata;
}


For the normal path (that is, all the cases except ) we can use the test from lemma 7:

	// normal path
uint l = ceil_log2(d) - 1;
uint m_down = (((big_uint)1) << (N + l)) / d;
uint m_up = (is_power_of_two(d)) ? m_down : m_down + 1;
uint temp = m_up * d;
bool use_round_up_method= temp <= (1 << l);

// set fields of divdata
...


Note that the temp variable is an -bit unsigned integer. It is just used to compute modulo . Also note that we need a special case for when is a power of two for rounding.

Setting the mul, add, and shift fields of divdata is straightforward:

	// set fields of divdata
if (use_round_up_method) {
divdata.mul = m_up;
}
else {
divdata.mul = m_down;
}

divdata.shift = l;


When you stitch the snippets together and include bits.h from the appendix you should get a working implementation of precompute. However, we can make it a bit more efficient. Note that we have a special case for and also special cases for when is a power of two. The trick we used for actually can be generalized to handle all powers of two.

We can set mul = max and add = max so that the high word contains the dividend. Then we only need need to shift the high word right by bits. Now, we can also compute instead of (which is slightly more efficient), since there is only a difference for powers of two.

divdata_t precompute(uint d) {
divdata_t divdata;
uint l = floor_log2(d);

if (is_power_of_two(d)) {
divdata.mul = max;
}
else {
uint m_down = (((big_uint)1) << (N + l)) / d;
uint m_up = m_down + 1;
uint temp = m_up * d;
bool use_round_up_method = temp <= (1 << l);

if (use_round_up_method) {
divdata.mul = m_up;
}
else {
divdata.mul = m_down;
}
}

divdata.shift = l;

return divdata;
}


There are probably lots of optimizations possible, but this is a reasonably simple and efficient version. It is adapted from [2].

### Compile-time optimization

Here, I will show a sample implementation of the idea. I use a hacked-together framework which is meant to resemble the part of a compiler backend that does code generation. The uint datatype is an -bit unsigned integer, where is 8, 16, or 32. The datatype expression_t is used to denote an expression tree, which can be used for code generation. This is all implemented in compiler.h, which is included in the appendix. For simplicity, I have not implemented register allocation -- every expression is stored from and to r0. This means that only really simple expressions can be used, but this turns out to be enough for our purpose.

We will implement a function div_by_const_uint that takes a constant divisor const uint d and an expression expression_t n that represents the dividend. It will return an expression that represents the instructions that will be executed. As an example, the expression can be written as mul(a, add(b, constant(5)) in this way.

I will use constant(n) where n is an uint to denote a constant, shr(a, b) to denote a right shift of a by b bits, umulhi(a, b) to denote the high bits of a multiplication, add(a, b) to denote the sum of a and b, sbb(a, b) to denote a subtraction with a borrow if the carry bit is set, and gte(a, b) which returns 1 if a is greater than or equal to b and 0 if a is less than b. Here, a and b can be expressions themselves. All nodes in an expression correspond directly to an instruction and the parameters to a function are passed in r0, r1, etc. So a function evaluate that has a single parameter a and returns can be implemented by the expression tree add(mul(a, 3), 5). This will generate the following instructions:

evaluate:
mul r0, r0, 3
add r0, r0, 5
ret


Admittedly, I picked the instructions and calling conventions to be convenient for my use case. The instructions that are emitted by the compiler are typically a bit longer. Still, for most cases the instructions are similar to those that compilers emit. You can see the instructions that clang 11.0 outputs for some divisors on https://godbolt.org/z/bKq7Wa. Note that clang 11.0 still produces suboptimal instructions for the case of an odd divisor that is not efficient for the round-up method, because it uses the method mentioned after theorem 3. Benchmarks from [4] show that using the round-down method is faster.

As mentioned before, for compile-time optimization we can distinguish a lot of cases to squeeze out every last bit of performance. Some special cases that can be implemented particularly efficient are:

• Division by one, which can be handled by setting the quotient equal to the dividend.
• Division by a power of two, which can be implement by a bit shift.
• Division by an integer larger than half of the maximum value of the dividend, which can be implemented by setting the quotient to zero if it is smaller than the divisor, and to one otherwise.
expression_t div_by_const_uint(const uint d, expression_t n) {
if (d == 1) return n;
if (is_power_of_two(d)) return shr(n, constant(floor_log2(d)));
if (d > MAX / 2) return gte(n, constant(d));
return div_fixpoint(d, n);
}


For divisors that do not fall in one of these special cases, we use fixed-point arithmetic to efficiently implement the division. We first test if the divisor is efficient for the -bit round-up method. For divisors that are efficient for the -bit round-up method, we use the round-up method. For even divisors that are not efficient for the round-up method, we use a modified version of the round-up method. Finally, for odd divisors that are not efficient for the round-up method, we use the round-down method, which is slightly less efficient.

expression_t div_fixpoint(uint d, expression_t n) {
// test if d is efficient for round-up method
...

if (use_round_up_method) {
// round-up method
...
}

if ((d & 1) == 0) {
// even divisors which are not efficient for round-up method
// handled by doing a preshift and using round-up method
...
}

// round-down method
...
}


To test if a divisor is efficient for the round-up method we simply implement the condition from lemma 7:

// test if d is efficient for round-up method

uint l = floor_log2(d);
uint m_down = (((big_uint)1) << (N + l)) / d;
uint m_up = m_down + 1;
uint product_mod_2N = m_up * d;
bool use_round_up_method = product_mod_2N <= (1 << l);


The round-up method is pretty straightforward to implement. For efficiency, we reduce and using lemma 9.

// round-up method

// find smallest m
while ((m_up & 1) == 0 && l > 0) {
m_up >>= 1;
l--;
}
return shr(umulhi(n, constant(m_up)), constant(l));


For even divisors which are not efficient for the round-up method, we can use lemma 8. First, we compute from by a right shift. The preshift variable holds the number of bits of this first shift. Then, we multiply by , and shift the result by postshift. You should convince yourself that the following implementation computes preshift and postshift in accordance to lemma 8. In particular, note that this implementation can increment preshift too often, so that postshift becomes negative, and that a separate correction step for this is needed.

// even divisors which are not efficient for round-up method
// handled by doing a preshift and using round-up method

// pre-shift as much as possible; postshift might
// become negative, this is corrected later
d >>= 1;
int preshift = 1, postshift = l - 1;
while ((d & 1) == 0 && postshift > 0) {
d >>= 1;
preshift++;
postshift -= 2;
m_up = (m_up + 1) >> 1;
}

// optimize m
while ((m_up & 1) == 0 && postshift > 0) {
m_up >>= 1;
postshift--;
}

// correct if preshift is too large and
// postshift has become negative
if (postshift < 0) {
m_up = m_up << 1;
postshift++;
}

expression_t n_prime = shr(n, constant(preshift));
return shr(umulhi(n_prime, constant(m_up)), constant(postshift));


There is a subtle point we have to take into consideration when implementing the round-down method. When we naively implement the evaluation of the expression , we would increment . However, when has the maximum value of , the expression will overflow. We can overcome this in a couple of different ways.

The first way is to use that . This latter expression has bits when and have bits. Some architectures have integer fused multiply-add instructions which directly compute . For example, in [2], the XMA.HU instruction on Itanium is used, which computes the high bits of . Other architectures may have support for doing -bit arithmetic. For example, this is the case when doing a division by a 32-bit integer on a 64-bit machine. Otherwise, most instruction sets have:

1. An instruction to add two values and set a carry flag if the sum has overflown
2. An instruction to add with carry, which adds two values and increases the result by one if the carry flag is set

Suppose we have an instruction set with an add instruction which sets the carry flag on overflow, and an adc instruction which adds with carry. Adding a constant, say 12345 to a -bit value contained in registers r0 (low bits) and r1 (high bits) is as easy as:

add r0, r0, 12345
adc r1, r1, 0


In [4], it is suggested to do a saturating increment of instead of naively calculating . This is the same as only incrementing when . So effectively, this calculates the expression

When we do not increment and we are effectively computing instead of . The only way that this difference can matter is when , so that . In this case is a divisor of , and according to the following result a divisor of is efficient for the -bit round-up method. So as long as we only use the round-down method for divisors which are not efficient for the round-up method, we will never get an incorrect result when we use a saturating increment.

Lemma 10: If is a divisor of , then is efficient for the -bit round-up method.

Proof: Take and define and . Using and , we see:

Here, we used that . Since is a divisor of , it can't be a power of two, so we have . It follows that since . We find that

So the condition for corollary 5 is satisfied. Since is not a power of two, we have that . By using lemma 6, we now see that for . So is efficient for the -bit round-up method.

A saturating increment can be implemented as an increment by one, followed by a subtraction with borrow. A subtraction with borrow works similar to an addition with carry: it subtracts a value from another, and decrements the result when the carry flag is set. I have used the sbb instruction to denote a subtraction with borrow. In the following code, n_inc is the result of applying a saturating increment on n:

// round-down method

// find smallest m
while ((m_down & 1) == 0 && l > 0) {
m_down >>= 1;
l--;
}
expression_t n_inc = sbb(add(n, constant(1)), constant(0));
expression_t hiword = umulhi(n_inc, constant(m_down));
return shr(hiword, constant(l));


Piercing all the code together and including the header file bits.h should give you a working implementation of div_by_const_uint and div_fixpoint.

### Testing

When writing code for or , I recommend that you check the result is correct for every pair with . This can be as simple as:

for (uint d = 1; true; d++) {
divdata_t dd = precompute(d);
for (uint n = 0; true; n++) {
assert(fast_divide(n, dd) == n / d);
if (n == max) break;
}
if (d == max) break;
}


For , this code will run more or less instantly, for it will take a couple of minutes. For this program won't terminate anytime soon. However, what you can you is test, for every divisor with , all numbers of the form :

for (uint d = 1; true; d++) {
divdata_t dd = precompute(d);

assert(fast_divide(0, dd) == 0);
assert(fast_divide(1, dd) == 1 / d);
assert(fast_divide(UINT_MAX, dd) == UINT_MAX / d);

uint bound = UINT_MAX / d;
for (uint k = 1, n = d; true; k++) {
assert(fast_divide(n, dd) == k);
assert(fast_divide(n - 1, dd) == k - 1);
if (k == bound) break;
n += d;
}

if (d == UINT_MAX) break;
counter++;
}


This will still take a long time, but it is feasible; The above code took slightly over 40 minutes to run on my machine.

For , exhaustive testing is completely infeasible. I recommend making a set of special values consisting of all numbers from 0 up to 256, all numbers of the form , , , the divisors of these numbers, and the divisors of . Then we can test if the result is correct for each , . On top of that, you can run some randomized testing. I recommend that you pick and uniformly random in and then mask out each byte with some probability. Then, you can run random tests for some time. If you find a bug in the implementations, add and for which the result is not correct to and verify that your testset triggers the bug before you fix the bug.

## References and further reading

The classic reference for optimization of division by both signed and unsigned integers is [1], which states and proves theorem 2 (round-up method). In [2], the approach is extended to the round-down method. The resources [3] and [4] are by far the easiest to read, and cover essentially everything in this article in a more accessible way. They sacrifice some rigor and completeness, though. If you are interested in optimizing division, I recommend reading these articles as your starting point. Finally, in [5] it is shown that we can also use fixed point math to compute the modulo operation.

[1]: Division by Invariant Integers using Multiplication, Torbjörn Granlund and Peter L. Montgomery, 1994.

[2]: N-Bit Unsigned Divison Via N-Bit Multiply-Add, Arch D. Robinson, 2005.

[3]: Labor of Divison (Episode I), fish, 2010.

[4]: Labor of Divison (Episode III): Fast Unsigned Division by Constants, fish, 2011.

[5]: Faster Remainder by Direct Computation: Applications to Compilers and Software Libraries, Daniel Lemire, Owen Kaser, Nathan Kurz, 2019.