Programming Math101 : Modular Arithmetic

Posted by blainegarrett

August 13, 2008

The below is a article I wrote for TCPHP mailing list in 2005. I thought of it today and decided to re-post it.
——————-

Hi,

This is the first part in a small series of requested math articles as it pertains
to programming. Please critique the article and give me feed back offlist. Let me
know if this is too mathy, too overview, etc etc. This article starts off with
some easy programming-wise stuff. It might get boring, i’ll try to make the others
a bit more interesting.

————————————-
1. Intro The topic of this article is modular arithmetic. It is not a very hard
concept, but falls under the cataegory of "number theory" and thus is not really
taught until upper college maths for engineers and scientists.

Think of modular arithmatic like a hours and minutes on a clock. Every top of the
hour, your minute hand is at 0, regardless of what hour it is. At every quarter of
an hour, the minute hand is at 15. Every bottom of the hour, 30. etc Again, this
happens regardless of the hour.

Another analogy is a binary one. If you have 2 people and an odd   number of apples,
there will be one left over if both get equal   numbers of apples. If there are an
even number of apples, then   there will be none left over.

Not overly complicated stuff… the wording there is probably more akward than the
math involved.

————————————
2. Onto the Math
The modulus of 2 numbers is related to the division of the two numbers and
"returns" the remainder of the division. If one number divides another evenly, then
there is no remainder. Otherwise, there will be a remainder. In the apples example
above, lets say we have 10 apples, 2 evenly divides 10 and thus we have no
remainder. 2 does not evenly divide 11. In number theory, there is an algorithm
called the "reduction algorithm" which allows you to do division with remainders
via an algorithm nicely as well as covert numbers between bases (base 10 to base 2
for example) in a generic algorithm. This is a handly little algrorithm.

Let N, q, m, r be intergers with interger q and 0 <= r <= |m|
then N = q * m + r

Non negative m is the modulus, r is the remainder.

This essentially says our original number (N) is something * the modulus (m) + some
left over stuff. We are interested in the left over stuff, which is the remainder.
If you feel up to it, you can rearrage this equation to get the standard division
syntax.

Binary examples : 0 mod 2 = 0      since 0 = 2 * (0) + 0
1 mod 2 = 1      since 1 = 2 * (0) + 1
2 mod 2 = 0      since 2 = 2 * (1) + 0
3 mod 2 = 1      since 3 = 2 * (1) + 1
4 mod 2 = 0      since 4 = 2 * (2) + 0
…

Notice that for every even number, the remainder is 0.

To somewhat illustrate the Clock example, let’s use 4 for quarter hours instead of
60 mins to keep it short.

0 mod 4 = 0      since 0 = 4 * (0) + 0 //12:00 noon
1 mod 4 = 1      since 1 = 4 * (0) + 1 //12:15
2 mod 4 = 2      since 2 = 4 * (0) + 2 //12:30
3 mod 4 = 3      since 3 = 4 * (0) + 3 //12:45
4 mod 4 = 0      since 4 = 4 * (1) + 0 //1:00 PM
5 mod 4 = 1      since 5 = 4 * (1) + 1 //1:15
6 mod 4 = 2      since 6 = 4 * (1) + 2 //1:30
7 mod 4 = 3      since 7 = 4 * (1) + 3 //1:45
8 mod 4 = 0      since 8 = 4 * (2) + 0 //2:00PM
…

Things to notice. Numbers that are m away from eachother have congruent remainders
(i.e. every quarter hour is always 15 mins). Likewise, any number modulus that
number is 0. The remainder is always less than the m.

—————————————-
3. For use in programming…

I use this in a variety of areas, but the most common is in alternating row colors.

In most programming langs, x mod y is represented as x % y.

Lets make some alternating rows….
$array_of_names = array(…);

foreach ($array_of_names as $index => $name) {
    //calculate row color
    $remainder = 2 % $index;
       if ($remainder = 0) { //output a tr with black   bg      }       else {
//output a tr with a red   bg                     }
}

So all that explaining for alternating rows. You may have known how to do this
before, but now you know what it works.

As a exercise, you should make a checkerboard. Hint, it requres a mod 2 check to
alternate row color a mod 5 check to create a new row. It also takes a little trick
to make the columns not have have the same color.

As an even more advanced exercies, try to do this in a recursive only language such
as XSL. It still uses modulus, but you have to rethink where you are outputting
your opening and closing row tags to keep the XSL wellformed. It is an interesting
little problem. Hint : requires a template for tr, td, and some xsl:for calls.

—————————————-
4. Closing notes

As we have seen something simple like alternating row color actually has some nifty
math behind it. We take for granted a lot of what PHP and other langs give to us.
Yet, to really be able to weild a programming language like a sword, you need to
understand even little details such as this.

—————————————–
5. Links with more info

http://en.wikipedia.org/wiki/Division_%28mathematics%29
http://en.wikipedia.org/wiki/Modular_arithmetic

Blaine
http://blainegarrett.com