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.

For example, int(2.9)=2, 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.

If you have a value x then mod(x,y) gives you the remainder that shows on the clock face and int(x/y) or truncating integer division gives you the number of roll overs needed.

Putting this another way int(x/y) gives you the number of complete groups of y and mod(x,y) gives  you the number left over.

Returning to the previous example we can now write the inches, feet and yards program as:

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

Notice that in this case you don't even have to test for roll over because you can simply allow the addition of zero roll overs!

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 of text taken 66 lines 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=y*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-y*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 with weeks as rows. 

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, i.e the user can edit a single date, without reprinting the entire calendar, made one approach more attractive than the rest.

What is needed is a function daypos(day) 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 is 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).

Notice that what we are doing here is splitting the days up into groups of 7 for the y co-ordinate and the remainder gives the x co-ordinate.  

To see how this works just try it for a few day numbers.

For day 1 we have day-1 is 0 and hence mod(0,7) is 0 and int(0/7) is also 0. For day 2 we have mod(1,7) is 1 and int(1/7) is still 0, for day 3 we have mod(2,7) is 2 and int(2.7) is still 0 and so on. The y value only changes when we reach day 8 and mod(7,7) is 0 again and int(7/7) is 1 - then the pattern repeats for x. 

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.

Mod and integer division often occur when you are trying to convert a grid arrangement into a linear arrangement or vice versa. The reason is that the the position in the grid can be specified as so many rows i.e. complete groups and so many over. 

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ⁿ.

For example an 8 bit register rolls over at 2⁸ or 256. 

This connection between binary registers and the mod function 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 manipulation often do have mod and integer division 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>