The Mod function
Written by Mike James   
Article Index
The Mod function
Storage Mapping And Registers

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, 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 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).

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

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.

Related Articles

Storage Mapping Functions       

Public Key Encryption  

XOR - The Magic Swap           

Introduction to Boolean Logic

JavaScript Bit Manipulation       

Dates are difficult

      

To be informed about new articles on I Programmer, install the I Programmer Toolbar, subscribe to the RSS feed, follow us on, Twitter, FacebookGoogle+ or Linkedin,  or sign up for our weekly newsletter.

blog comments powered by Disqus

 
Banner


What Is Computable?

Performing a computation sounds simple like a simple enough task and it is easy to suppose that everything is computable. In fact there are a range of different types of non-computability that we need [ ... ]



Quick Median

You have probably heard of Quicksort but this is just one of many partitioning algorithms that work in clever ways to do things faster. Here we look at another of the algorithms devised by C.A.R. Hoar [ ... ]


Other Articles
 

 

<ASIN:1598220020>

<ASIN:0750687096>

<ASIN:0071371923>



 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.