(Or Why You Should Know About Modular Arithmetic)
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
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)]
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 rewriting
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:
Student

Student Index

Student Index % 3 (i.e. Team index)

Team

Tom

0

0

A

Dick

1

1

B

Harry

2

2

C

Rita

3

0

A

Sue

4

1

B

Bob

5

2

C

Peter

6

0

A

Paul

7

1

B

Mary

8

2

C

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 webpage 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 nthoftype
selector, e.g.
h1:nthoftype(3n+0)
{color: red}
h1:nthoftype(3n+1) {color: white}
h1:nthoftype(3n+2) {color: blue}
h1:nthoftype(3n+1) {color: white}
h1:nthoftype(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.
No comments:
Post a comment