# Modular Arithmetic: A Divisive Issue

I'm sure FPGA logic designers have often heard it said: *"We just need to take this number mod 3."* Or maybe something like, *"Just round to the nearest hundred."* This latter case really means: *"Take the number mod 100: over 50, round up, under 50, round down,"* with something more to handle the round-to-even rule for the value 50.

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

*a*+

*b*) mod

*N*= [(

*a*mod

*N*) + (

*b*mod

*N*)] mod

*N*

**Equation 1**

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:

*x*=

*x*+

_{1}*x*+

_{2}*x*+

_{4}*x*+

_{8}*x*+ ...

_{16}
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:

*x*mod 5= [(

*x*mod 5) + (

_{1}*x*mod 5) + (

_{2}*x*mod 5) + (

_{4}*x*mod 5) + (

_{8}*x*mod 5) ...] mod 5

_{16}
Conveniently, bits have two possible values: 0 and 1. That means that (*x _{k}* mod 5) has two possible values: 0 when

*x*= 0, or some

_{k}*N*when

_{k}*x*= 1. Thus...

_{k}

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.