# Division by constant unsigned integers

The code accompanying this article can be found in a github repository.

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 of the form . Now, if we expect that . The expression can be evaluated with just a multiplication and a bit shift, and is more efficient to evaluate than a division by .

The idea might be a little less mysterious after seeing an example in the decimal system. Take . Instead of taking a large constant of the form , we take . Now we have . Now we have . We certainly expect that since .

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 denote for the set of natural numbers including zero, for the set of positive natural numbers, and for the set of integers. Further, 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 , . 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 we should have whenever . So, it is natural to take with as our starting point, since we expect 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 method produces the correct result. Note that from this point on we will assume that is larger than . We will assume and use and interchangeably.

First, we would like to know when the round-up method is correct. The following theorem states a condition under which the round-up method is correct, that is, for all .

Lemma 2: Let and . If

then for all .

Proof: Multiplying the inequality by we get

For all we have , so that . It follows that we have

for all . By lemma 1, it follows that for all .

Lemma 2 essentially says that if there is a multiple of in the interval , there exists some constant such that for all .

The following theorem provides us with a practical choice for , by simply rounding up .

Theorem 3 (round-up method): Let and , and let . If then for all .

Proof: Considering that is the smallest multiple of that is larger than , we have . So if we have . So by lemma 2 we have for all .

For the efficient evaluation of the product it is necessary that and fit in a single -bit register. So it is natural to wonder whether we can always find such that for all and is an -bit unsigned constant.

First, let’s do some examples.

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 theorem 3 is satisfied and for any 8-bit unsigned integer we have .

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 theorem 3 is satisfied and for any 8-bit unsigned integer we can have .

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

Theorem 4: Let , with 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. So satisfies the condition of lemma 2, and it follows that for all . By using lemma 8 with instead of , we see that , so .

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

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


This trick is used by some compilers to handle divisors for which does not fit in bits.

Now, let’s focus on the round-down method. If, instead of using we round down and use , we run into some problems. When we take any that is not a power of two, we see that so that while when . So, we find that the value of is too low. Instead of rounding up to get , we can round down but increase . This gives us the round-down method, which approximates by with .

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

Lemma 5: Let and . If

then for all .

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 .

This lemma is obviously an analogue of lemma 2 for the round-down method. It is also possible to prove an analogue of theorem 3 for the round-down method. We will not use this result in the rest of the article and proving it is left as an exercise for the reader.

Exercise: Prove the following theorem.

Theorem 6: Let with , and let . If then 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 7: We call a positive divisor efficient for the -bit round-up method if there exists a tuple such that for all . Likewise, we call a positive divisor efficient for the -bit round-down method if there exists a tuple 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 8: Let , with and define . Now with

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 9: Any positive divisor is either efficient for the -bit round-up method, or efficient for the -bit round-down method.

Proof: Set and define . From lemma 8, 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.

This theorem also implies that we never need to check if a divisor is efficient for the -bit round-down method. We can simply test if a divisor is efficient for the -bit round-up method, and use the round-down method if it is not. Indeed, when both methods can be used we prefer to use the round-up method, since it is slightly more efficient.

The following result gives us a more intuitive understanding of the conditions of lemma 2 and 5.

Theorem 10: Let with . Define , , , and . Now:

• If , then is efficient for the round-up method
• If , then is efficient for the round-down method

Proof: Suppose . This implies and , so we have

Substituting , multiplying by , and using gives

So the condition of lemma 2 is satisfied and we have for all . Using lemma 8, we see that can be represented with bits. We see that is efficient for the round-up method by definition 7.

Similarly, suppose . Then we have and . Combining this gives

Substituting , multiplying by , and using gives

So the condition of lemma 5 is satisfied and we have for all . Using lemma 8, we see that can be represented with bits. We see that is efficient for the round-down method by definition 7.

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

Lemma 11: Let , , and define 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 . So if , we have . So the condition of lemma 2 is satisfied and we have for all . By lemma 8 it follows that , so by definition 7 is efficient for the round-up method.

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 9, 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. So and we can use theorem 4 with instead of .

Lemma 12: Let , with and . Let , , , and . Then

for all .

Note: It can be useful to express in terms of , and in terms of . In this case, we get and .

Example: Take , . Setting we get . We see that . So is not efficient for the roundup method. However, it is even, so using lemma 12 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 that satisfies the condition

Luckily, if we have found a single that satisfies the condition of the round-up or the round-down method, it is simple to find out if there is a smaller that satisfies the same condition.

Lemma 13: Let , with , and let be such that . Suppose that the tuple satisfies either the condition of lemma 2:

or the condition of lemma 5:

If is even, then the tuple satisfies the same condition. If is odd, then there exists no smaller that satisfies the condition.

Proof: Suppose that satisfies the condition of lemma 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 the condition of lemma 5 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 , so there can only be one multiple of in this set, which is . So we have , so must be even.

Basically, we can set , and see if TODO

once we have found an that satisfies the condition of lemma 2 or lemma 5, we can keep dividing it by two (and decreasing by one) as long as it is even. Once the result is odd, we have find the smallest that satisfies the condition.

The following examples illustrate this.

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 use lemma 13 and 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 9, we see that 11 is efficient for the -bit round-down method. We have . Since is even, we can use lemma 13. We divide by two to get and have .

Example: Take , . We set so that . Now , so is efficient for the round-up method. Now write . Using lemma 12 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 12 gives us that with for all . We can now apply lemma 13 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  and , 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 compilation, there is a lot of room for optimizations. Typically, programmers are OK with waiting a fraction of a second longer for their programs to compile if this means that their code executes faster. So for division by compile-time constants, there is time for extensive optimizations and it pays of to distinguish many special cases in which small improvements are possible. At runtime, time is more precious, so we want to keep the precomputation reasonably efficient. We’d like the fast_divide function to have a single codepath for all divisors, to keep it efficient.

### 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 {
} 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 continue 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 can 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. For now, it 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 11:

// 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 the computation of for when is a power of two for rounding.

Setting the mul, add, and shift fields of divdata is straightforward. For the round-up method we evaluate the expression , so we need to multiply by and don’t need to add anything. For the round-down method we evaluate the expression as , so need to multiply by and add .

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

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

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
ret


Admittedly, I picked the instructions and calling conventions to be convenient for my use case. In practice, the assembly emitted by the compiler is 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 godbolt.org. 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 4. Benchmarks from  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.

For divisors that do not fall in one of these special cases, we use fixed-point arithmetic to efficiently implement the division.

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);
}


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 11:

// 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 13.

// 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 12. 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 12. 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 , 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.

An alternative is to use a combination of the following two instructions, which are supported by most processors:

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


In , 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 14: Let with . Then

• If , then with for all .
• If , then with for all .

Proof: The expression is just rounded up to the nearest multiple of , so we have . Now, we write . Substituting this in gives

So the condition of lemma 2 is satisfied if and only if .

Likewise, we have and by substituting this in the condition of lemma 5 we see that the condition if satisfied if and only if .

Exercise: Follow the more direct approach taken in  and  to prove lemma 14. Use , , and lemma 1.

Lemma 15: 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 of lemma 14 is satisfied. It follows that that when we have for all .

Since is a divisor of , it can not be a power of two. So is not an integer, which implies . From lemma 8, it follows that . So we have for all for some . It follows by definition 7 that is efficient for the -bit roundup 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));


### 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 == UINT_MAX) break;
}
if (d == UINT_MAX) break;
}


For , this code will run more or less instantly, for it will take a couple of minutes. For this program will take far too long to run. 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;
}


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 containing at least 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 test set triggers the bug before you fix it.