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(day1,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 coordinate and the remainder gives the x coordinate.
To see how this works just try it for a few day numbers.
For day 1 we have day1 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^{n}.
For example an 8 bit register rolls over at 2^{8} 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 lowlevel 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.
Joe Celko Comments:
The MOD() Function
The modulo or remainder function is actually trickier than it looks. It appears in most programming languages of have numeric datatypes. If m is zero, then we get a division by zero exception. Otherwise, the result is the unique nonnegative exact numeric value r with scale zero such that
 r has the same sign as n.
 the absolute value of r is less than the absolute value of m.
 n = m * k + r for some exact numeric value k with scale zero.
This is tricky when the values of n and m are not cardinals (i.e., positive, nonzero integers).
Experiment and find out how your Favorite programming language handles negative numbers and decimal places.
This was a major issue for the Pascal Standard at one time, versions of FORTRAN also had different implementations. Originally, MOD(n, m) was defined only for positive values of both m and n, and leaves the result to be implementationdependent when either of m or n is negative.
Negative values of n have no required mathematical meaning and that many implementations of MOD either do not define it at all, or give some result that is the easiest to calculate on a given hardware platform.
However, negative values for (m) do have a very nice mathematical interpretation that we wanted to see preserved in the SQL definition of MOD(). Len Gallagher of NIST proposed the following rules to use in the SQL standard, along with the usual SQL convention That if either parameter is a NULL, then the result is a NULL:
 If n is positive, then the result is the unique non_negative exact numeric quantity r with scale zero such that r is less than m and n = (m * k) + r for some exact numeric quantity k with scale zero .
 Otherwise, the result is an implementationdefined exact numeric quantity r with scale zero which satisfies the requirements that r is strictly between m and (m), and that n = (m * k) + r for some exact numeric quantity k with scale zero, and a completion condition is raised: warning  implementationdefined result.
This definition guarantees that the MOD() function, for a given positive value of n, will be a homomorphism under addition from the mathematical group of all integers, under integer addition, to the modular group of integers {0, 1..., m1} under modular addition. This mapping then preserves the following group properties:
1) The additive identity is preserved: MOD(0, m) = 0
2) Additive inverse is preserved in the modular group defined by
MOD(MOD(n, m), m) = m  MOD(n, m)
MOD(n, m) =  MOD(n, m)
3) The addition property is preserved where "⊕" is modular addition defined by MOD((MOD(m, m) + MOD(n, m)), m)
MOD((m + n), m) = MOD(m, m) ⊕ MOD(n, m)
4) Subtraction is preserve under modular subtraction, which is defined as MOD((MOD(m, m) ⊖ MOD(n, m)), m)
MOD(mn, m) = MOD(m, m) ⊖ MOD(n, m)
From this definition, we would get the following:
MOD(12, 5) = 2 MOD(12, 5) = 3
Storage Mapping Functions
Public Key Encryption
XOR  The Magic Swap
The Memory Principle  Computer Memory and Pigeonholes
We discover why computer memory can be likened to pigeonholes and even include instructions for you to build your own memory device.

Data Structures  Trees
Classic data structures produce classic tutorials. In this edition of Babbage's Bag we investigate the advanced ecology of trees  perfectly balanced trees, AVL trees and BTrees.
 Other Articles 
<ASIN:1598220020>
<ASIN:0750687096>
<ASIN:0071371923>
