The integer division instruction of an computer is typically ten to thirty times slower than the multiplication instruction, due to its complexity. If a divisor is execution-invariant, however, there is a way to replace the integer division operation with an integer multiplication and division by some power of two, the latter of which can be performed by using a bitwise right shift operation. We investigate this approach in this note. Many of the materials discussed in this note are found in (Granlund and Montgomery 1994) and (Henry S. Warren 2013), but some mathematical results and derivations in this note are original.
Introduction
We consider three kinds of divisions in this note: the one that rounds down the fractional part of the result, the one that rounds up the fractional part, and one that rounds the fractional part towards zero. Given a execution-invariant divisor , define , , and by and
Let be the bit width of integers we consider, which is basically the maximum size of dividends with which we perform division by . We assume that . Define . A type of division we consider is division whose dividend and divisor both belong to . We call such division unsigned division. The unsigned division may round down and round up the fractional part of the result.
Another type of division involves integers in . We call this type of division signed division. In signed division of by , the fractional part of the result can be rounded down (Euclidean division), rounded up, or rounded towards zero.
Just for a moment, suppose that we need to divide a real number by another real number , where is execution invariant. Then we can use the fact that to replace the division by multiplication of by , where can be calculated beforehand and written into the code.
In the integer division with a dividend , we can try something similar, but limit our operations to integer multiplications and bitwise right shifts (and some additions and subtractions when needed). The basic idea is that we can choose an integer and a nonnegative integer to let approximate , so that for every in the relevant range of integers. If the approximation is valid in an appropriate sense, the right-hand side can be calculated by multiplication of by and bitwise right shift of the product by positions.
Division by a Power of Two
Bitwise shift operations
This section considers how to perform the division of integers by a power of two through bitwise shift operations. We assume that the CPU provides logical and arithmetic bitwise right shift instructions. Let , …, be functions from to such that for each That is, is the th bit in the binary representation of . Using the binary expansion, we can respectively define the logical and arithmetic bitwise right shift functions, and , by and When is the encoded signed integer in two’s complement, is the sign bit of . The term fills the th through st bit positions with the sign bit. When , it holds that , because is zero.
Unsigned division
Suppose that we want to divide integers in by , where . Pick arbitrarily. Then the binary expansion of is given by where each among , , …, is zero or one. Division of by yields that On the right-hand side of this equality, the first term is an integer, while the second term resides between 0 and , so that
For computation of , we can use the fact that for each , which can be compactly rewritten as It follows that
Signed division
We now consider division of integers in by for some . Define and by and respectively. The function encodes the given integer in two’s complement, and the function decodes the encoded integer, i.e., . Applying of to a given integer and then applying for position shifts yields that When , it holds that so that It follows that
When , it holds that . It follows that Because , it follows that Since , it further follows that Thus, we have verified that for any , The arithmetic bitwise right shift can be used in downward division of signed integers by a power of two.
For computation of , we use the fact that for each , while . It follows that for each , Because , can be conveniently evaluated by The value of then can be computed by using the arithmetic bitwise right shift as we have seen.
The division rounding towards zero can be performed by combining the downward and upward rounding divisions: This formula can be compactly rewritten as
Finally, when we want to divide integers in by for some , we first perform division by and then flip the sign of the result. In the division stage, we need to use the opposite rounding mode unless the desired mode is rounding towards zero.
Unsigned Division by a Number That Is Not a Power of Two
In this section, we mainly consider the downward-rounding version of unsigned division and then also cover the upward-round version at the end. Let be a fixed natural number, and define Our goal is to investigate how to pick and to ensure that if the equality is possible at all. We later apply the obtained results to the case where (i.e., ). The divisor belongs to , and it is treated as a constant throughout this section. .
Valid choice of and
Define by Then () holds if and only if The condition () can be rewritten as We can interpret this condition using an analogy.
In the analogy, represents a date, ranging from zero to . For convenience, we use a modified week system. Monday is any date that is a multiple of . A week is the -day period starting on a Monday. The day following a Monday is a Tuesday. The last day of a week is a Sunday.
Imagine that a household receives one dollar every Monday starting date zero. Then is the total payment received by the household by the week immediately prior to the week of date . Thus, the total payment received by date is . Also, imagine that the household spends dollars every day from date one to date but spends no money on date zero. Then the total spending by date is . Thus, we can interpret () as the requirements for the daily spending .
The first inequality in () requires that the household’s total spending up to each date be no less than the payments accumulated over the previous weeks. Note that the accumulated payments does not change during the week, while the total spending increases every day. Thus, this requirement is equivalent to that the spending accumulated up to each Monday is no less than the payments accumulated over the past weeks.
Recall that the household spends no money on the first Monday. In order for the requirement to be met on the second Monday, the total spending during the day period between the first Tuesday and the second Monday must be no less than one dolor. It is therefore necessary that , or equivalently that . In each week after the second week, this pace of spending uses up one dollar received on Monday by the following Monday. Thus, it is also sufficient for the first inequality of () that . We now formally state and prove this result.
Proof. If for every , setting yields that This establishes the necessity of (). If instead () holds, then for each Thus, the condition () is sufficient.
Now suppose that . Then both and must be a power of two. Thus, the inequality in () is strict if the inequality holds, unless is a power of two. ◻
The second inequality in () requires that the household’s total spending up to date is less than the payments accumulated up to the Monday in the week of the date. If the household spends dollars per day, the requirement is satisfied, because it receives one dollar every Monday. Recall, however, that the household spends no dollars on the first Monday. The dollars that were not spent on the first Monday can be used to increase the daily spending.
Define . Then date is the final Sunday. There are up to days after date . This means that the daily spending satisfying the requirement in the first week also satisfies the requirement in the week after date (if any). Consider spending dollars each day. This pace uses up the dollars that were not spent on date zero during the period between date one and date . Thus, the daily spending must be smaller than it, i.e., or equivalently, . The formal statement of this result and its proof follow.
Proof. If for every , then it holds that , so that Because , we have that Multiplying both sides of this inequality by yields () and establishes the necessity of ().
Suppose instead that () holds. Pick arbitrarily. Then we have that Write . It follows from the above inequality that If , the right-hand side of this inequality is dominated by one, because When , it follows from the definition of that , , and . The right-hand side of () is again dominated by one, because This establishes the sufficiency of ().
Now suppose that () holds. If , we have that , so that () holds with ; hence, . Suppose instead that and . By rewriting (), we obtain that By the definition of , is an integer, so that both sides of this inequality are integers. It follows that or equivalently, Applying this inequality, we obtain that Because by hypothesis, it follows that ◻
Given Propositions and , we can conveniently check if a given pair of and satisfies ().
Proof. The result immediately follows from Propositions and . ◻
Feasibility
The condition () can be interpreted as giving the possible range of to satisfy () given , because they are equivalent to Using this condition, we show that there exists a pair of and that satisfies ().
Proof. If , then it holds that If instead , then The result therefore follows. ◻
Proof. By Proposition , it suffices to show that there exists that satisfies () with . Because there exists an integer that satisfies (), which is equivalent to (). ◻
Along with Proposition , the next proposition shows that there are infinitely many pairs of and that satisfy ().
Proof. By the equivalence between () and () established by Proposition , it suffices to show that () holds with and if it holds with and . This is indeed the case, because ◻
Ideal choice of and
Given that there are infinitely many pairs of and that satisfy (), which pair should we use? Because the division by multiplication method requires the product of the dividend and , we naturally prefer the pair with the smallest to avoid overflow in the multiplication.
Proof. By rewriting (), we obtain an equivalent condition that This condition holds if and only if is no less than the ceiling of the right-hand side, which is . ◻
Given , we should use in the division by multiplication approach, provided that () holds with . The next proposition demonstrates some properties of .
Proof. The first inequality immediately follows from the fact that . To verify the the second inequality, we use the fact that The right-hand side of this inequality, which is an integer, is one of the integers no less than the left-hand side. Thus, ◻
Proposition implies that our best choice of the pair of is the minimum that satisfies () with . If is a power of two, we really don’t need the division by multiplication method, as we can simply apply the bitwise right shift operation, as Section demonstrates. When is not a power of two, there is a lower bound for that can be used in the division by multiplication.
Proof. Propositions and imply that there exists such that for each integer , () holds with some . It thus suffices to show that , i.e., () does not hold with regardless of the value of . As Proposition shows, is the minimum value of that satisfies () with . Because is increasing in , we can establish the result by showing that () does not hold with .
Write . Then it holds that because , and is not a power of two by hypothesis. It also follows from Lemma that i.e., . It thus holds that The result therefore follows. ◻
Define Propositions and establishes lower and upper bounds for . With the bounds, we can find by checking if each between and satisfies that Because is an integer that depends on neither nor , we only need to compute it once in the search for .
Because , is no greater than , whose upper bound is established in the next proposition.
Proof. By definition, we have that Because is an integer, it follows that ◻
Unsigned division of -bit integers
We now focus on the case in which both the divisors and the dividend are -bit unsigned integers, where is an natural number, which is fixed for the rest of this section (e.g., or ). We set , so that . We here restate the results established in Subsections - in this special case of our focus.
Proof. Set . Then it holds that . The claims of the proposition trivially follows from Propositions and –. ◻
Given the facts stated in Proposition , we use the pair of and , where is the least integer between and satisfying ().
The upper bound is tight in the sense that can be equal to . For example:
On the other hand, it is pretty rare that , as the next proposition demonstrates.
Proof. If is a power of two, it holds that and that . Thus the claim holds.
Assume that is not a power of two. Then it holds that , as Proposition () claims. By Proposition (), (), it follows that if and only if Because is not a power of two, it holds that , and that where . Thus, we have that It follows that if and only if or equivalently, Rearranging this inequality yields that Thus, it suffices to show that () holds if , and that it does not hold when .
Suppose that . Then we have that , so that () clearly holds. Suppose instead that . Then we have that . () does not hold because where the second inequality follows from Lemma . ◻
Proof. If is a power of two, we have that . Suppose that is not a power of two. By Proposition , it holds that either or . The result therefore follows by the second claim of Proposition (). ◻
Overflow consideration
While Proposition () guarantees that never exceeds , it can be larger than , the maximum integer in .
Suppose that our computer can handle multiplication of two -bit unsigned integers. To compute , we typically use one of two methods. The first method assumes that the hardware provides the product of two -bit unsigned integers in a -bit register. It takes the product of and , and then logical bitwise right shifts the result by positions.
The second method assumes that the upper bits of the product is given in a -bit register (either discarding the lower bits or storing the lower bits in another register). It takes the product of and , and then bitwise right shifts the upper bits the product by positions.
Both of the methods described above requires that , i.e., . But it is not unusual that . In such cases, we need a twist in the computation methods. Write and . Then it holds that because . Using and , We can express as The values appearing on the right-hand side of this equality involves only values in . But the right shift instruction of the CPU rounds down the fractional prat in the result each time. It turns out that the replacement of the regular division by the round-down division preserves the equality: We verify this equality below.
Proof. Write , , , . Then it holds that , and that . Using these quantities, we can write as Using this equality, we obtain that It follows that The first term on the right-hand side is the left-hand side of the equality in question, while the second term on the right-hand side of this equality is zero, because The result therefore follows. ◻
Proof. Because and , it follows from Lemma that Because is integer, we have that The result therefore follows. ◻
When we use (), it is important to notice that can still overflow if the addition is performed using -bit registers. If the CPU provides a means to logically bitwise right shift the bits in the carry flag and the register together, the overflow does not pose any problems.
When we have no access to such a means, we need to avoid the overflow by further rewriting (). This requires that .
Proof. We can assume that is not a power of two, because otherwise, . By hypothesis, we have that It follows that Division of both sides of this inequality by yields that It follows that so that . ◻
Knowing that , () can be rewritten as On the right-hand side of this identity, we have that It follows that does not overflow. Also, it holds that These verify that no part in the expression on the right-hand side of () overflows using -bit registers, once is calculated.
Large divisors
When , it holds that The division by multiplication method is less efficient than the conditional assignment after checking the condition that .
Round up division
When we want to compute instead of , we can use the facts that for any , and that . Using these facts, we obtain:
In this proposition, can be computed by using the division by multiplication method.
Signed Division by a Number That Is Not a Power of Two
Write . This is the typical range of signed integers in a -bit register. This section mainly considers division of integers in by a execution-invariant positive divisor , where the fractional part of the result rounded towards zero
Division by the absolute dividend and negation
We can handle the nonnegative dividends in by replacing with in the analysis of the previous section. We just need to pick and such that where . For each negative dividend , we have that It follows that except when (i.e., ). Thus, it holds that for each , This requires two additional negation operations (or one absolute value and one negation) compared to the case with a positive dividend. But there is an alternative approach.
Division by multiplication with a shift
Define and let be the integer given by () with this value of . It then holds by Propositions and that for each negative The second inequality is not strict because the largest possible value of is . By applying the fact that to this inequality, multiplying all terms by , and adding one to all terms yields that This inequality is almost what we want, as it implies that or . If the second inequality of () is strict, we can rule out the latter possibility. In fact, we know that the first inequality in () is strict unless is a power of two. Under the strict inequality, we obtain that so that for each negative , .
Proof. As we have seen above, the claim is true if is not a power of two. When for some , we have that and . For any nonnegative , it obviously holds that . For each negative , we have that Write . Then we have that , and that It follows that ◻
When , does not belong to . Because it holds that , however, satisfies that , so that . Define . Then can be rewritten as On the right-hand side of this equality, we have that so that . Also, and have opposite signs. It follows that the computation of never overflows using -bit registers, once is calculated.
Euclidean division
The method described in Subsection rounds down the fractional part of the quotient if the dividend is positive; otherwise rounds up the fractional part. We sometimes want to perform Euclidean division, which rounds down the fractional part regardless of the sign of the dividend.
Because the method of Subsection delivers the desired result for nonnegative dividends, we only consider how to deal with negative dividends. If an integer is negative, we have that Thus:
Round up division
To calculate correctly, we need to modify for positive dividends, as Subsection does. The result is:
Negative divisor
Now, let’s consider the case with . Because , where , we can relate the case to the signed division with a positive divisor by letting and take the roles of the divisor and the dividend, respectively. This, however, requires a little adjustment. The range of is (), to which also belongs. To include in the set of dividends, we need to adjust the choice of and in the division by multiplication approach.
We first consider the division of nonnegative dividends by , where the set of dividends to cover is We here restate the main results from Section adapted to the current problem.
Proof. Set . Then it holds that . The claims of the proposition trivially follows from Propositions and –. ◻
Let be as defined in Proposition and define Because , we can easily find the value of , as discussed in Subsection .
We now know that Suppose that is not a power of two. Then this equality is equivalent to Pick an arbitrary positive integer in . Then is negative, and it belongs to . So, we can plug into in () to obtain that By applying the fact that to this inequality, multiplying all terms by , and adding one to all terms yields that It follows that Combining this result with that for the case with nonpositive dividends, we obtain that In computation of the right-hand side of this equality, it may be useful that .
Proof. If is not a power of two, the claim holds as we have already verified. Suppose that for some . Then it holds that and that . For each negative (so that ), it holds that For any positive , we have that Write . Then it holds that , and that It follows that ◻
As in division by a positive divisor, the multiplier can be less than , the minimum value in , but we know that . Suppose that . Define and . Then we have that so that . Thus, We can perform the multiplication of by by rewriting () as The subtraction from never overflows the using -bit register.
For the Euclidean and round-up divisions, we can also easily verify that for each and where and .
Conclusion
This note implements the division by multiplication method in signed and unsigned division in the round down, round up, and round towards zero mode and demonstrates why the implementations work.