### Modulo arithmetic

#### By Darryl Gove on May 22, 2008

Modulo arithmetic (or clock arithmetic) is quite a costly computation. The C code looks like:

d = a % b;

This gets translated into:

d = a - ( trunc(a/b) \* b);

which is a division, multiplication, and subtraction. The integer division instruction is particularly time consuming, but integer multiplication can also be a tad slow on some platforms (perhaps a total of a hundred cycles in worst cases).

If it's possible, it would be a good idea to restrict the variable `b`

to be a power of two. In this case the code becomes:

d = a & (b-1);

Which is a single `and`

instruction - which takes a single cycle on almost all platforms.

Cool trick :-)

Posted by

Raymond Tayon May 22, 2008 at 04:52 PM PDT #And if b is an appropriate power of 2, you can even use unsigned short/int/long and require 0 instruction. However, in most cases where I use modulo, b is a prime number, which is hard to coerce to a power of 2 ;-)

Now I agree that if you are using modulo just to do an operation once in a while, it is better if "a while" equals 1024 rather than 1000.

You say that a%b is replaced by a-trunc(a/b)\*b. If a/b is an integer division, I don't see what there is to truncate. Aren't there architectures where the rest of an integer division can be computed much more efficiently?

Also, the case where b is known at compile time is different from the general case, because the compiler can sometimes replace the division by something more efficient.

Posted by

Marcon May 22, 2008 at 08:49 PM PDT #Marc, I'll agree with your comments!

Yes, primes are the common reason to use mod, and they don't represent well.

I put the explicit trunc in there to clarify. Otherwise there's a chance that someone would do the simplification of a-a\*b/b=a-a=0. :)

As you say for some values of b there's more efficient ways of calculating it. The compiler normally recognises these situations, and can add the code appropriately.

The other thing to bear in mind is that if most of the time a<b, then doing

if (a<b)

{return a;}

else

{return a%b;}

can be a win.

Anyway, thanks for the comment - it's reminded me of a couple of books that I read many years ago. See next post.

Posted by

Darryl Goveon May 23, 2008 at 03:36 AM PDT #