Remainders Today (or Why You Should Know About Modular Arithmetic)

You probably left "remainders" behind in primary school - why are they so important in programming?

This might appear to be a strange first topic in a sequence of blogs about Computing, but its content is directly relevant to a current GCSE controlled assessment task – although, of course, I’m not going to say which one!

One of the problems with coming new to Computing or is that (without wishing to sound like Donald Rumsfeld) you don’t know what you don’t know. Most teachers can probably see the name of a topic with which they’re not familiar, read about it, and teach it, but modular arithmetic is a simple mathematical concept and very useful programming technique that isn’t mentioned in the National Curriculum and I haven’t noticed it in any GCSE specification.

If I were to ask you, "What is 10 ÷ 4?", what would you say? I suspect that most adults and KS4 students (and, indeed, most programming languages other than Python) would say “2.5”. But think back to your primary school days - when you first started to learn about division, all of the answers were integers. The answer you’d have given would have been, "2 remainder 2".

That’s basically all modular arithmetic is – division with remainders, where we’re particularly interested in the remainder part.

Why the remainder, though? That seems like the least important part of the answer. In my example, dividing by four, how many possible remainders are there? The remainder can only be 0, 1, 2 or 3 (as 4 is divisible by four), so there are four possible remainders. Modular arithmetic is therefore a good way of creating a function with a limited number of outputs.

We actually use this technique already with things like times and angles, although you possibly haven’t thought about it in this way or given it a name.

For example, if it’s now 10 o’clock, what time will it be in four hours’ time? We know that a standard analogue clock only shows twelve hours, but 10 + 4 = 14, so what do we do? We divide the time by twelve and use the remainder; 14 ÷ 12 is 1 remainder 2, so the time would be 2 o’clock.

Similarly, if we’re using a compass to find directions and we’re currently heading on a bearing of 280°, which way would we be facing if we turned 100° clockwise? Adding 280 and 100 gives us 380, but the compass only goes up to 360. Dividing 380 by 360 gives 1 remainder 20, so the new direction is 20°.

So modular arithmetic is very useful for things that are cyclical in nature, and all programming languages (that I’ve used) allow you to do it. It is often referred to in the reference documents as the modulo, and the operator you need to use is most commonly % (e.g. in Python or JavaScript) or simply MOD (e.g. in BASIC).

Programming the previous two examples, therefore, could give you something like this:

time = 10
time = (time + 4) % 12
bearing = 280
bearing = (bearing + 100) % 360

Note my use of brackets to force to the addition to be done first – programming languages follow the standard BIDMAS rules.

How about a less numerical example? When I was at school, the PE teachers used to allocate us to teams by lining us up and moving along the line, cycling through the team names, e.g. “A, B, C, A, B, C…”, etc. Here’s a short Python program that does the same thing:

students = ("Tom", "Dick", "Harry", "Rita", "Sue", "Bob", "Peter", "Paul", "Mary")
teams = ("A", "B", "C") 
for student in range(len(students)):
    print students[student],"is in team", teams[student % len(teams)]

I’ve used Python because lists make for a shorter program, but the idea can be used with any programming language, e.g. using arrays instead.

The first thing to notice is that finding the modulo is a numerical technique, but the student and team names aren’t numbers. You might also come across this problem when wanting to choose a random item (e.g. a day or a name) from a list when we can only generate random numbers. We need to find something we can use that is a number; most often this will be the list or array index.

The program loops through all of the students in the list (because they all need to be in a team) and uses the modulo to work out which team they should be in. As there are three teams we need to divide by three, but my program actually uses the length of the list as the divisor so that we can amend the lists without re-writing the code (it would be more efficient to calculate the length of the list once and store it in a variable).

Using the list indexes, and remembering that they begin at zero in Python, this is how the student index would be translated into the team index:

In summary, then, if you have a program that you want to cycle through n options, you can simply enumerate them and use modulo n as an index.

You can also use this technique in CSS. Imagine that you were creating a web-page for the French department and you wanted to cycle through red, white and blue for the heading colours. You could style each heading explicitly, or create classes for red, white and blue headings, but that would cause problems if you were to insert an extra heading in the middle of the page. Instead of styling each heading explicitly, you can use the remainder idea and the nth-of-type selector, e.g.

h1:nth-of-type(3n+0)   {color: red}
h1:nth-of-type(3n+1)   {color: white}
h1:nth-of-type(3n+2)   {color: blue}

Inside the brackets, the coefficient of n is effectively the number of options (i.e. 3n for three colours), and the number added is the remainder (i.e. +0 for the first heading) – e.g. if you take the index of the heading, divide it by three and the remainder is zero, then the text will be red.

This blog originally appeared in the TES Subject Genius series in October 2015.