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.

Comments:

Cool trick :-)

Posted by Raymond Tay on 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 Marc on 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 Gove on May 23, 2008 at 03:36 AM PDT #

Post a Comment:
Comments are closed for this entry.
About

Darryl Gove is a senior engineer in the Solaris Studio team, working on optimising applications and benchmarks for current and future processors. He is also the author of the books:
Multicore Application Programming
Solaris Application Programming
The Developer's Edge

Search

Categories
Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
5
6
8
9
10
12
13
14
15
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today
Bookmarks
The Developer's Edge
Solaris Application Programming
Publications
Webcasts
Presentations
OpenSPARC Book
Multicore Application Programming
Docs