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.