Coding Practices – The Modulus Operator..

August 11, 2008

During my travels of programming video games for a living, I take great pleasure in the fulfillment of learning, exploring & experimenting with algorithms & the intricacies of programming languages everyday. Being a gamplay programmer I tend to find that I make regular use of the modulus operator & it seems to be one of those little tools that most people seem to overlook but can be really useful for a variety of problems. So I thought it might be a good idea to write a little article about my experiences with lil’ old ‘%’ & hopefully it maybe able to encourage others share good practical uses for it too & hopefully teach me a thing or two.

Before we begin I’d just like to make a note that I’m going to be using C# for all my examples considering this blog are generally c#/XNA-centric (however i’m pretty sure the same functions for the modulus operator can be applied in C/C++ & most other languages)..

So What Is The Ol’ Mod..?

The Modulus operator (sometimes termed ‘Modulo‘ in computing fields) defines an operation which returns the remainder of a division of one number by another. So for example if we take the any dividend ‘a’, & a divisor ‘n’ then we can define a % n (a modulo n) as the remainder.

So if we have 7 % 3 then we look at it as an integer division of only the proportion of the numbers which can evaluate to a whole number. In this case we see that 7 / 3 doesn’t equal a whole number (equals 2.333) however 6/3 does (leaving no remainder) so to find the modulus of this expression we can treat 7 / 3 as 6/3 + remainder which tells us that the remainder is 1. Here’s a few more examples just to help you get your head around the idea:-

8 % 4 = 0
12 % 16 = 12

So a few rules to bear in mind which will help you use the operator in practice:-

  1. if a / n equals a whole number then a % n  always equals 0
  2. if a is less than n then a % n always equals a
  3. if a is greater than n then a % n always equals a value between 1 and n-1

As we can see these three simple rules help put things into perspective & should now hopefully give us a really sound idea of some of the ways we can use the operator in practice.

Let’s Get To The Main Course Already..!

OK so now we’re ready to begin looking at some of the ways we can use the modulus operator & it’s unique properties for something useful. Here’s what I have so far:-

Wrap-Around & Looping Number Iteration

Sometimes in our travels we may need to iterate through an array in such a way that we can use an incremental index value that can be reset once it goes beyond the bounds of the array. Modulus is really useful for doing these tasks as, looking at rules 1, 2 & 3, we can see that it’s zero-based in nature & perfectly suited to this kind of ‘wrap-around’ processing. So where we would have once had something like this

// increment index & return the item in the array
i++;
if (i >= maxNumValues) i = 0;
return foo[i];

We can now substitute it for something like this

// increment index & return the item in the array
return foo[ (i++)  %  maxNumValues ];

Not a massive change but at least we’ve saved ourselves a few extra lines of code & removed the branch statement.

2D Coordinate Indexing

On several occasions i’ve found that I needed to index data in a 2D grid format. Whether it be indexing tiles on a spritesheet or onscreen items in a grid there’s generally a tendencies to define the data in a ‘flattened’ array format & make the grid-like behaviour implicit in it’s use. So say we have a sprite sheet containing a grid of tiled sprites of size d x d pixels and arranged in a grid of 4 x 4 tiles. if we treat the tiles as a 1D array of data then we can index each value from left-to-right, going from top-to-bottom starting at 0 and ending at 15 (4 x 4 -1 since it’s zero-based). in this case if we wanted to get the coordinates of a tile as say index = 9 we could do the following

  • count up the indices from 0 to 9 & in each step:-
  • add 1 to x & if x is greater than the number of tiles in a row then remove the number of tiles in a row from x & add one to y
  • multiply x by the tileWidth & y by the tileHeight & return the two values

This will work if you use a while loop and branch statements but it will end up taking up several lines of code & could end up being overly complex. However if we use the modulus operator we can do it much quicker/cleaner

x = index % numTilesRow;
y = ( index – x ) / numTilesRow;
return new TileDims( x * tileW, y * tileH );

I added the struct TileDims just for illustration purposes but beyond that it’s a pretty neat & cheap solution. Also we can reverse this & retrieve the index from the coordinate values in a simple fashion

// return the index for x & y
return x + ( numTilesRow * y );

Detemining Odd or Even Numbers

We can use % to determine whether a number is odd or even by examining exactly what it is we mean by ‘odd’ & by ‘even’ first. by definition an odd number is any number that cannot divide into 2 (i.e. odd / 2 != wholeNum). With this in mind we can do a simple check for this

// odd number check
if ( num % 2 != 0)
// odd number..
else
// even number..

Simple to use but it can save alot of time trying to determine whether this is true using a brute force, iterative approach.
How Many 10s, 100s etc In A Decimal Value

Sometimes we may need to figure out how many 10s are in a number for example, which can be especially useful of you need to separate the digits of a number for rendering on multiple quads. Again the implementation is pretty simple

// find the number of 10s & 100s in num
tens = ( num – (num % 10) ) / 10;
hundrds = ( num – (num % 100) ) / 100;

So that’s it from me!

Please feel free to drop any comments you have & also I’d love to hear about any other neat little % tricks you’ve discovered during your own coding travels..!
– The Hog

About these ads

12 Responses to “Coding Practices – The Modulus Operator..”

  1. Jason Says:

    Hi. It’s worth profiling the two solutions. Modulus, although quick and easy to code and read is likely to be slower at runtime, by a significant amount. Branch prediction, present in C# & other languages, would contribute to this disparity.

    Seems counter intuitive I know, but that little operator can cost you many precious cycles in a time critical routine.

    • oladotunr Says:

      I was under the impression that the built in modulus operator in C# mapped directly to a hardware instruction as it does for most native code compilers these days. A quick search through MSDN also alludes to this being the case.

      However if you have reason to believe otherwise then I’d love to be proven wrong on this?

      Thanks for the response Jason!

      – The Hog

  2. Jason Says:

    @oladotunr, I’d be interested to know where MSDN alludes to this being the case, do you have a link?

  3. oladotunr Says:

    I’ll try & dig it out for you..

  4. oladotunr Says:

    Can’t seem to find the link but it might be worth profiling & checking the disassembly if you get the chance..

    Shouldn’t be too hard..

  5. kerry Says:

    I have been looking for something like this, how can I make a value that goes from -99999 to 99999 behave in a manner to be say from 0 to 149 ??

    N mod 150 = 0 to 149

    But, if N goes negative then the result mirrors?

    • oladotunr Says:

      Negative numbers don’t tend to work out too well with some of the modulus usage methods detailed above…

      However I’m not sure what you’re trying to achieve here.. To get a value that goes from -99999 to 99999 to behave in the same way as a positive range value then you could either scale the range or shift and clamp the value before you use the modulus operator depending on the exact behavior you’re trying to produce..

      Do you have a clearer example of what you are trying to do?

  6. Mnescat Says:

    Interesting arcticle, read the whole thing, not what I was looking for though :) So that should be a complement to dig for in here!

  7. firemystdl Says:

    Nice, easy, simple tutorial with even simpler code to understand. Thank you.

    For those who are more curious, this article examines the fastest way to get the remainder between using modulus or an alternative with addition:
    http://blogs.davelozinski.com/curiousconsultant/csharp-net-use-the-modulus-operator-or-alternative

    It’s obviously more for speed and micro-optimization junkies.
    :-)

    _

  8. gauthier Says:

    2D coordinates, 10s and 100s:
    I don’t know about C#, but standard C has the function div() in : http://en.cppreference.com/w/c/numeric/math/div
    That way you get both the division result and the remainder at once, instead of performing two divisions.
    You can hope that your compiler finds the simplification in the code you wrote (first / then %) and achieve only one division, but I’m not so sure it would.

    Wrap around:
    I am with Jason. Performing a division can be costly, checking for boundary and assigning 0 cannot. You can put the check and zero in a function if you want to reduce the LOC of your functions.
    I like that way better also because it is more descriptive of what is meant. “Increment, but get back to 0 if you got too far.”
    The modulo works, but its meaning is not really that, rather “how much is left in the first bucket that is not full, whatever the number of bucket that were filled beforehand?”.

  9. baezcodes Says:

    Reblogged this on darylbaez and commented:
    Coding Practices… Modulus…


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: