Copyright © 2001, Douglas. W. Jones. This work may be transmitted or stored in electronic form on any computer attached to the Internet or World Wide Web so long as this notice is included in the copy. Individuals may make single copies for their own use. All other rights are reserved.
The ususal way to compute a mod m is to take the remainder after integer division. This is straightforward when the operands are within the range of the available divide hardware, but the divide operation is frequently among the very slowest arithmetic operations available, some small microcontrollers have no divide hardware, and it is occasionally necessary to divide very large numbers outside the range that can be done using the available hardware.
When the modulus m is constant, even where there is a hardware divide instruction, it can be faster to take the modulus directly than to use the divide instruction. These tricks become even more valuable on machines without a hardware divide instruction or where the numbers involved are out of range.
see if the least significant decimal digit is zero.
see if the least significant decimal digit is even.
see if the least significant decimal digit is 0 or 5.
if the sum of the decimal digits is divisible by 3, the original number is also divisible by 3.
if the sum of the decimal digits is divisible by 9, the original number is also divisible by 9.
In the case of divisibility by 2, 5 and 10 for base 10, the term (b mod m) is zero because 2, 5 and 10 all divide evenly into 10. As a result, the divisibility test simplifies to asking whether (a mod b), that is, the least significant digit of the number, is evenly divisible.
In the case of divisibility by 3 or 9 in base 10, the term (b mod m) is one. As a result, the multiplier for the first term is one. Applying the formula recursively leads to the simple sum of the digits.
Thus, for a mod 2, we use a & 1, for a mod 4, we use a & 3, and for a mod 8, we use a & 7.
Recall that the & operator means logical and. When applied to integers, this computes each bit of the result as the and of the corresponding bits of the operands. For all nonzero positive integers i, the binary representation of 2i–1 consists of i consecutive one bits, so anding with 2i–1 preserves the least significant i bits of the operand while forcing all more significant bits to zero.
The problem is more interesting when the modulus is not a power of two.
That is, a mod 3 can be computed from the sum of the digits of the number in base 4. Base 4 is convenient because each base 4 digit of the number consists of 2 bits of the binary represenation; thus a mod 4 can computed using a & 3 and a / 4 can be computed using a >> 2.
Recall that a >> b shifts the binary representation of a left a total of b places. As with logical and, this is a very inexpensive operation on a binary computer, and the effect is the same as dividing a by 2b.
The terminating condition in the above code represents a small optimization. Instead of repeatedly summing the digits until the total is a single base 4 digit in the range 0 to 3, this code stops as soon as the sum is under 6. This is because the final mod operation is done by comparing with 3 and subtracting if out of range; this compare and subtract operation can deal with any value up to twice the modulus.
The constants used in the above version reflect the maximum values in each field of the result at that stage of the computation. A sum of the one bits in a 4-bit field will be no greater than 4, which can be represented in 3 bits and so is selected by the mask value 7. A sum of the one bits in an 8-bit field will be no greater than 8, which can be represented in 4 bits and so is selected by the mask value F16. A sum of the one bits in a 16-bit field will be no greater than 16, which can be represented in 5 bits and so is selected by the mask value 1F16.
The above version uses the optimized constants, although the range of values in each field is now a bit larger: A sum of two base-4 digits will be no greater than 6, which can still be represented in 3 bits and so is selected by the mask value 7. A sum of four base-4 digits will be no greater than 12, which can still be represented in 4 bits and so is selected by the mask value F16. A sum of eight base-4 digits will be no greater than 24, which can still be represented in 5 bits and so is selected by the mask value 1F16.
This code is far faster than the first algorithm we gave. On a 3 Ghz dual-core Intel Core i3 machine, this improved code averages 21 nanoseconds slower than a subroutine using the built-in mod operation, less than half the overhead of the original code presented above.
The payoff for this optimization is significant. On a 3 Ghz dual-core Intel Core i3 machine, this improved code averages 10.4 nanoseconds slower than a subroutine using the built-in mod operation. This is under 1/5 the overhead of our original code and half the overhead of our first attempt at optimizing.
That is, the truncate instruction preserves the b least significant bits of the register r while setting the more significant bits of r to zero. Recall that the << operator means left-shift, so the expression 1 << b is equivalent to 2b and therefore (1 << b)–1 has just b ones. A good C compiler should use this instruction whenever to implement the and operation whenever the binary representation of the operand is a string of b one bits, such as the constants 3, 7, 15 or 31. Even when such an instruction is not available, a sequence of two shift operations can be used to do the same thing. On a 32-bit machine, for example, the following sequence of two shifts will frequently truncate the value in a register in less time than it takes to first load a long constant.
Again, working out the worst cases in order to determine whether we were within reach of the final subtract operation was time consuming. The payoff is significant, but we are approaching the limit of what we can accomplish with this kind of trickery. On a 3 Ghz Intel dual-core Intel Core i3 machine, this improved code averages 6.8 nanoseconds slower than a subroutine using the built-in mod operation. This is about 1/9 the overhead of our original code.
Could we have eliminated one of them? The answer is, it depends on the actual range of the argument. All of the code given above has been tested for all 32-bit integer arguments. If one of the three identical shift and add statements is omitted, the code works for all integers from zero up to 1,359,020,030.
In the SIMD context, there is no obvious way to do an if statement to subtract of 3 from every byte greater than 3, so the final step adds one to each byte and masks to select the carry bit. Where adding 1 produced a carry of 1, the byte was 3 and needs to be zeroed. We zero it by adding the carry bit back into each byte and then masking to delete the new carry.
This code (or similar code on larger words) can compete with code that extracts each byte for division by three. The context in which this idea was originally pointed out to me involved use of the streaming SIMD instructions on the Intel x86, but the idea obviously has broader applications.
The code for computing a mod 65535 above is slightly faster, on average than the hardware mod operator on a 3.06 Ghz Intel Core i3 processor.
On a 3 Ghz Intel dual-core Intel Core i3 machine, this code takes 115 nanoseconds more than a subroutine with the minimalist body "return a%5" — relying on the built-in mod operation. This is worse than half the speed of our first iterative code for mod 3. The explanation for this poor performance lies in the multiply by 3 inside the inner loop. This not only takes a small amount of time, but it forces significantly more iterations in the loop: Where the mod-3 code divided by 4 with each iteration, this code divides by 8/3.
Trial and error is valuable here, but the difference between these code fragments is small.
Before reducing this to C code, note that 2(a/8) is not the same as a/4 because we are using integer division. On a binary computer, this can be correctly expressed in two ways, either (a >> 3)<< 1 or (a >> 2)& –2. Recall that, in 2's complement binary, –2 is ...111110, so anding with this constant forces the least significant bit of the result to zero while preserving the remaining bits.