Page 1 of 2
What has modular arithmetic got to do with the real world?
The answer any experienced programmer should give you is "a lot". Not only is it the basis for many an algorithm, it is part of the hardware.
Many programmers are puzzled by the mod, short for modulo, and integer division functions/operators found in nearly all languages.
Modular arithmetic used to be something that every programmer encountered because it is part of the hardware of every machine. You find it in the way numbers are represented in binary and in machine code or assembly language instructions.
Once you get away from the representation of numbers as bit strings and arithmetic via registers then many mod and remainder operations lose their immediate meaning so familiar to assembly language programmers.
You may not meet the mod function or operator in the course of learning to program, but once you start to write real code you will certainly meet it. As soon as you start implementing even the simplest of algorithms the need to understand mod will occur.
Passive and Active
- 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. it tells you the remainder after you have grouped x things into groups of size y.
- 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 modified 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.
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.
That is on a clock face numbered 0 to 5 start at 4 and move the hand on by 3 and it points to 1. Similarly starting at 2 and moving 5 back gets the hand to 3.
Multiplication and division work in exactly the same way once you remember that multiplication is repeated addition and division repeated subtraction.
However it is generally easier to do the arithmetic ignoring the "clock face" and then finding the representation of the result on the clock face. For example, 5*8 is 60 and if you start with the clock hand on 0 and move it sixty places on you end up at 4.
In programming all you have to do is to work out the arithmetic in the usual way e.g. 5*8=40 and then use the mod function to find its representation on the clock face -
For another example consider arithmetic mod 7 then 4*2 in mod 7 is:
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
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
The answer needs integer division which is mod's other half.
This is obvious if you think about Mod in its first interpretation as the remainder function. If you use Mod to divide up x things into groups of y then the remainder is what the clock dial shows. The number of groups of y that you formed is the number of times the clock "rolled over". You can find this out by working out the integer division of x by y i.e. how many whole times does y divide x - and this is integer division.
Mod finds the remainder on the clock and integer division find the `how many times the clock rolled over'.
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.
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) 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:
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
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.