Page 2 of 2
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)
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.
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 2n.
For example an 8 bit register rolls over at 28 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
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.
Storage Mapping Functions
Public Key Encryption
XOR - The Magic Swap