Modular Arithmetic: A Divisive Issue

Editor's Note: You may also be interested in my Rounding Algorithms 101 Redux article...

Your first thought as a logic designer might be to tell the person asking to go away and come back with a different question. This is because good techniques for FPGA implementations of the mod operation have not been widely known.

It's really not that bad! Maybe some of the older generation remember "casting out nines." A related technique turns modular arithmetic, for a constant modulus, into a straightforward exercise in combinational logic. You could do it the hard way: divide your variable x by constant N and take the remainder. Or you could think about the problem differently...

The basic approach: one bit at a time
Let's start with a familiar piece of arithmetic:

In other words, you can compute the modulus of a sum term-by-term; you don't have to add everything up and do the mod operation at the end. When you let a and b each be sums in their own right, this expands recursively to sums of any number of terms.

As a concrete example, let's take the modulus N to be 5, and compute some variable x mod 5. In order to use Equation 1, we start by treating the value of unsigned x as the sum of its binary-weighted digits:

In other words, x_j contributes the value j when the corresponding bit is one and contributes zero when the bit value is zero. So, using Equation 1, we can rewrite x mod 5 one binary digit at a time:

Conveniently, bits have two possible values: 0 and 1. That means that (x_k mod 5) has two possible values: 0 when x_k = 0, or some N_k when x_k = 1. Thus...

So, when x is a 32-bit number, computing "x mod 5" means adding up small numbers that total only 80, at most. Then, when you have a sum in the 0-80 range, you can repeat the process or do a table lookup to get the final sum-mod-five value.

Any experienced logic designer will already have noticed lots of clever optimizations that can be applied to that sum of bit-by-bit modulus values. Instead, let's look for bigger efficiency gains by taking another look at x.

By the way, x mod some power of two is the easy case. You already know to take the few least significant bits and discard the rest. If you actually work through Equation 2 for a power-of-two modulus, you'll see that it ends up with the same result.