The Mod Function
The Mod Function
Written by Mike James   
Tuesday, 31 March 2015
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 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 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.

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 non-negative exact numeric value r with scale zero such that 

  1.  r has the same sign as n.
  2.  the absolute value of r is less than the absolute value of m.
  3.  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, non-zero 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 implementation-dependent 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:

  1. 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 .
  2. Otherwise, the result is an implementation-defined 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 -- implementation-defined 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..., m-1} 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(m-n, m) = MOD(m, m) ⊖ MOD(n, m)

From this definition, we would get the following:

MOD(12, 5) = 2
MOD(-12, 5) = 3

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


Introduction To The Genetic Algorithm

Genetic algorithms pop up all over computer science and applied computing. They are simple, easy to apply and easy to understand. What mystery remains is why they work at all? How can something seemin [ ... ]



Codd and his Rules

Theories of how we should organize databases are thin on the ground. The one exception is the work of E.F. Codd, the originator of the commandment-like “Codd’s Rules”. This approach to database  [ ... ]


Other Articles
 

 

<ASIN:1598220020>

<ASIN:0750687096>

<ASIN:0071371923>

 



Last Updated ( Friday, 18 August 2017 )
 
 

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