Many programmers are puzzled by the mod, short for modulo, and integer division functions/operators found in nearly all languages.

Passive and Active

The mod(x,y) function, or the mod operator x % y in C# say,  is very simple but you can think about it at least two different ways - corresponding, roughly speaking, to passive and active models of what is going on.

• First the passive:
  
  The most obvious definition is:
  mod(x,y) or x % y gives the remainder when you divide x by y
  
  In this case you are thinking of working out what is left over if you do something in `chunks of y'. For example, a text file is 20000 lines long and you can fit 66 lines to a page - how much text is left over? The answer is 2 because mod(20000,66)=20000 % 66 =2.

Whenever you have a problem that involves chopping something up into regular sized groups the mod function/operator comes in handy for working out how to deal with the leftovers.

• Second the active:
  The active approach to mod considers what happens when you use it as part of basic arithmetic operations. This is much closer to the inner workings of the real machine:
  
  mod(x,y) or x % y implements finite arithmetic with a roll over at y
  
  In this case the mod function is just a way of imitating what happens naturally when you do integer arithmetic using a fixed number of bits. You can also think of it as doing the arithmetic modulo some number - so its the + or the * operators which are different and the mod doesn't even appear.
  This definition is a bit more difficult to follow but it's still trivial as long as you studied `clock arithmetic' as part of modern maths at school.

If you didn't then it's not too late.

Clock arithmetic

Imagine a clock face with numbers from 0 to y-1 then counting mod y is simply a process of advancing from number to number until you reach y-1 when you `roll over' to 0 and start the sequence again.

So counting mod 6 goes 0,1,2,3,4,5,0,1,2,.. and so on. Notice that in counting mod 6 the integer 6 doesn't actually occur.

Similarly arithmetic mod y works by moving the clock's hand on or back by the required amount. For example, 4+3 = 1 and 2-5 = 3 in arithmetic mod 6.

Multiplication and division work in exactly the same way.

In general all you have to do is to work out the arithmetic in the usual way e.g. 5*8=40 and then represent it on the "clock face" mod(5*8,6)=mod(40,6)=4.

You can see that this image of a clock face and a pointer advancing is appropriate for all sorts of simulations of real world objects.

For example, a set of dials recording values in mixed units to different bases can be represented by counting in different mod  bases. Counting in yards, feet and inches (with 3 feet in a yard and 12 inches in a foot)  you would use something like

inches=mod(inches+1,12)
IF inches rolls over THEN 
                 feet=mod(feet+1,3)
IF feet rolls over THEN yards=yards+1

Now we come to an interesting question; how to tell when a mod counter has rolled over. Adding one to the counter each time is a bit too easy because you can simply test for the counter being at zero after an update. A more interesting problem is how to check for roll over when an arbitrary value is added. For example, how do you discover how much to increment feet following

inches=mod(inches+inc,12)

The answer needs integer division which is mod's other half. Mod finds the remainder and integer division find the `how many times'.

Many languages do integer division naturally if you divide one integer type by another and there is no need for anything special. But in dynamically typed languages dividing one integer by another automatically gives a floating point number and to convert back to integer you have to use a function something like int, trunc or floor depending on the language. What you need is a function that simply chops off any fractional part of the number.

That is int(x/y) for example is the number of times y divides into x exactly - where int means "take the integer part by truncating the result e.g. int(2.9)=2.

For example, int(14/12)=1, int(25/12)=2 and so on.

Now we have a way to detect not only roll over but how many times the roll over occurred-

inches=mod(inches+inc,12)
finc=int(inc/12)
feet=mod(feet+finc,3)
yinc=int(inc/3)
yards=yards+yinc

Notice that in this case you don't even have to test for roll over!

Integer division comes in useful whenever you are trying to chop something up into a number of parts.Compare this to mod which is useful when you need to know what is left over after chopping something up into a number of parts.

For example, how many pages is 20000 lines taken 66 to a page?

Answer int(20000/66)=303 whole pages plus one with mod(20000/66) lines on the last page.

It isn't difficult to see that y*int(x/y) is the largest multiple of y smaller than or equal to x.

For example, 12*int(33/12)=24.

Equally obvious is that

x=x*int(x/y)+mod(x,y)

because if you add the remainder to the closest exact multiple of y then you get x back again!

This is the basis of the technique used by many a programmer to work out mod(x,y) when a mod function isn't available i.e.

mod(x,y)= x-x*int(x/y)

Building a calendar

As an example of how modular arithmetic can turn up in the most unlikely places I'd like to tell you about an interesting problem.

Write a program that will print a calender one month per page in the `traditional' format. 

There are a number of possible approaches to the problem but an extra condition, namely it has to be possible to modify what is displayed at any given date location without reprinting the entire calender, made one approach more attractive than the rest.

What is needed is a function daypos(day,x,y) that will convert a day number into an x,y position on the screen/page. To accommodate any old month you need six rows of seven columns.

If you first assume that the first day of the month falls on a Sunday (which in general it doesn't but starting from a special case if often easier) then it is obvious that modular arithmetic can be used to calculate the position of each date -

x= mod(day-1,7)
y= int(day/7)

assuming that each date only takes 1 column to represent (if you want more realism just multiply x by n where n is the width of the column).

The only remaining touch is to add the fact that the first day of the month isn't always a Sunday. If you know that the first day of the month falls in the nth day of the week (with Sunday as 0) then the correct formula is

x = mod(day+n,7)

y = int((day+n)/7)

Easy!

You might recognise this method as nothing but a storage mapping function but working in reverse - i.e. taking the linear day number into a two dimensional array x,y instead of converting x,y into linear storage address.

Registers

The final question is what does modular arithmetic have to do with hardware?

The answer is that machines do arithmetic in binary and in fixed size registers. The number of bits that a register can hold is usually 8, 16, 32, 64 etc. If you start counting in such a register by repeatedly adding one you eventually reach a state where the register contains all ones. After this adding one more usually makes it role over to 0 and this is the connection between register and mod arithmetic. If a register has n bits then arithmetic in the register is equivalent to arithmetic mod 2^n.

This is not only interesting from a theoretical point of view, it can also be practically useful. When calling low level routines or programming hardware directly, there is often the need to store a value suitable for use in a register.In most cases you can achieve this using a combination of bit shifts and logical operations - but not all high level languages have such operations. Languages that don't have low level bit manipularion often do have mod and integer divisio and these can be used just as easily.

For example, if you have a value stored in a variable and you want to make sure that it can be stored in a single byte then your problem is solved by

var=mod(var,256)

Taking mod(var,256) effectively chops off the bits above the lower eight that are assumed to fit into the register. You can even extend the idea to splitting data so that it can be stored in more than one fixed size register.

For example, if you have a 16 bit register that can only be loaded 8 bits at a time then the job can be done using

lowbyte = mod(var,256)
highbyte = mod(int(var/256),256)

The second formula simply reduces the contents of the variable dividing by 256 - equivalent to an 8 bit right shift before chopping it off to the low order 8 bits.

Modular arithmetic turns up in lots of other more technical subjects such as checksums, random number generators and security - but these are another story. At least now you know why the mod function crops up occasionally in fairly standard programming.

<ASIN:019512376X>

<ASIN:076373621X

<ASIN:1598220020>

<ASIN:0750687096>

<ASIN:0071371923>