How far do you take modular expressions?

Question

I'm sure that basically every introductory course involves teaching about the ubiquitous mod operation. In my experience, and I'm sure I'm not alone in this, I've found that teaching my students that "mod is the remainder of division" is insufficient if I want them to make any use of the concept later on.

Beyond showing them how to use mod to check divisibility, I have for the last few years gone into far more interesting operations in order to help them achieve some intuitive understanding of what mod is and how it works. So, for instance, I show them how they can increment within a modular circle of numbers from 0 to n-1 (a circle of size n):

[some loop structure] {
    x = (x+1)%n;
}

Or, how to move that circle along so that it ranges from m to (m+n-1) (still a circle of size n, but it no longer starts at 0):

[some loop structure] {
    x = (x+1-m)%n+m;
}

Or how to decrement along a 0 to n-1 circle in a language like Java, which deals with negative modular operations by returning the highest negative congruence (ie. -10 % 4 would return -2 instead of 2. While they are both technically correct answers, Java's answer is decidedly inconvenient for the purpose of moving along a modular circle of numbers, because when you try to move from 0 back to n-1, you get the wrong result.)

[some loop structure] {
    x = (((x-1)%n)+n)%n;
}

Or, doing the same thing by moving n-1 steps clockwise around the circle instead of moving 1 step counterclockwise:

[some loop structure] {
    x = (x+n-1)%n;
}

And, of course, we can generalize this to involve any cyclical pattern of numbers that can be reduced to a proper modular circle where $f(n)$ is the function that takes any number within the cycle to its corresponding location in the modular circle, and $g(n)$ is the function that takes it back:

[some loop structure] {
    x = g(f(x+1)%n);
}

Now, I am reasonable certain that nobody uses structures like this in any production environment. Part of my justification for going to such lengths with mod operators has been that I am not a teacher of software engineering. I am a teacher of computer science, and having a firm understanding of modular arithmetic is important for Some Big Ideas later on. (Like Two's Complement, which has a very intuitive and coherent explanation when you think about it in terms of cycles within a number space.) And when all is said and done, many of my students really do come out with a good, intuitive sense of how the mod operation works.

But I also wonder if I have just gone plum crazy. This stuff takes a lot of class time to get the kids to master, and I'm really wondering if the time would be better spent on other pursuits.

How far should modular arithmetic be taken in the CS classes that are early enough along in the curriculum that they still focus on programming?

Answer 1

A specific example that I've used the mod operator before for (and have seen it used in production code this way) is to represent a higher dimensional array (usually 2D, but higher is possible) as a one dimensional array, and then use some modular arithmetic to retrieve the higher dimensional structure. The reason one might want to do this is if your array structure is a substructure of a more complex object, it might be simpler to implement it one dimensionally, and then add more complexity onto that.

I've seen this done when one is "tiling" some 2D space, where each tile maps to some properties, and where each tile's properties may change in time. This could end up being a very complex structure: potentially, a mapping from time, to the first dimension of the tile, to the second dimension of the tile, to each of the properties of the tile. In such a case, the geometric "2D"-ness of the tiling may not be that important (except for perhaps the display), and so the implementation of the internal model of these tiles could be one dimensional instead, simplifying our model.

Here's a simple 2D array example. Say one has a 3 by 3 array, where the "property" is represented by some integer:

1 4 9

0 2 7

5 6 4

Our 2d array may be indexed with [row, column] as follows:

[0,0] [0,1] [0,2]

[1,0] [1,1] [1,2]

[2,0] [2,1] [2,2]

However, we can represent it with only a single parameter as:

0 1 2

3 4 5

6 7 8

(left to right, then top to bottom is just a convention of course)

Now, how do we retrieve the row and column numbers given one of these indices? This shows some nice symmetry between the / operator (that is, truncated division on integers) and the % operator.

If we're indexing rows and columns as in my first example, the "row number" of an index i above is given by i / 3 (again, truncated), and the "column number" of an index i above is given by i % 3.

In general, if you have an n by n array, and you index it as I did above, the row number is given by i / n and the column number is given by i % n.

Another example, and this one gets closer to the intuition you're trying to achieve, is simplifying computations for cyclic functions. If your functions are over the integers, then your operator % is good enough. However, this wouldn't work for continuous functions. Nicely enough, one can take your discrete cyclic model and make it continuous in programming languages by using fmod or an equivalent.

Specifically, for students with enough background in Calculus that have some familiarity with Taylor series, one can think of how one would write a trig function like cosine. One might realize that the 6th degree Taylor polynomial approximation is "close enough" in the range between $- \pi/2$ to $\pi/2$. Then, one can "mirror" that to get one complete cycle of the cosine curve between $-\pi/2$ and $3\pi/2$ (for example.) Then, with this, one might ask how one would compute the value of $cosine$ for any real number, and the answer is quickly obtained by using some modular arithmetic to get your number in that range, and then use our restricted cosine function for that translated number.

This use of mod also relates to Guy Coder's answer: thinking of taking the mod of a number as involving several subtractions is precisely how one might implement the continuous fmod function (however, whereas a discrete mod function's usual "remainder" intuition may be lost here, the intuition regarding the cyclical nature of mod should be strengthened).

In general, I like to think that the kind of mental modeling required to think about mods is going to help these students regardless of whether they literally use them later on in their programming careers.

Answer 2

How far should modular arithmetic be taken in the CS classes that are early enough along in the curriculum that they still focus on programming?

I view the mod or modulus operator as any other operator that is new to the students. Even though mod is used more often when programming because it results in an integer value which is much more friendly to work with than a mantissa of a real division, I see no reason early on to spend any more time than is necessary to get the idea of how the mod function/operator works.

When students are introduced to the mod operator for the first time it can be confusing. To make it easer for them I tell them that just because it is named mod doesn't mean you have to create a new idea in your head to understand it. Instead just think of it as the remainder, but when you talk to others programmers you have to use the word mod or modulus as that is the currently accepted name. They like that and we only spend a few minutes on it. I obviously show them how it relates to float division and integer division by listing examples of float division, integer division and modulus.

Also if a student says remainder in class I just ask Did you mean mod? and if they say yes we keep going. If they say no then I ask what they mean. If they are getting it wrong I do a quick review. Most students get it rather quickly but do say remainder more often at first but quickly get to using mod or modulus.

If I do have to go over the concept again for some students I do use the concept of having items in my hand and do multiple subtractions until I have just the remainder. When I can subtract no more I ask them what do I have left and they give me an integer number and I say that is the mod value. Haven't had anyone get it wrong after they repeat that exercise back with them holding the items and doing the repeated subtractions, e.g.

1 % 3
I have 1 item in my hand,
Can I subtract 3: No
What do I have left: 1
That is the mod value

5 % 3
I have 5 items in my hand,
Can I subtract 3: Yes
Now I have 2.
Can I subtract 3: No
What do I have left: 2
That is the mod value

7 % 3
I have 7 items in my hand,
Can I subtract 3: Yes
Now I have 4.
Can I subtract 3: Yes
Now I have 1.
Can I subtract 3: No
What do I have left: 1
That is the mod value

0 % 2
I have 0 items in my hand,
Can I subtract 2: No
What do I have left: 0
That is the mod value

1 % 2
I have 1 item in my hand,
Can I subtract 2: No
What do I have left: 1
That is the mod value

4 % 2
I have 4 items in my hand,
Can I subtract 2: Yes
Now I have 2.
Can I subtract 2: Yes
Now I have 0.
Can I subtract 2: No
What do I have left: 0
That is the mod value