Darryl Gove's blog
Modulo arithmetic
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.
Posted at 03:14PM May 22, 2008 by Darryl Gove in Sun | Comments[3]
Cool trick :-)
Posted by Raymond Tay on May 22, 2008 at 11: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 Marc on May 23, 2008 at 03:49 AM 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 Gove on May 23, 2008 at 10:36 AM PDT #