TUDOR COMPUTATIONAL WITCHCRAFT

  • Learn a Tudor Algorithm to do hard times tables
  • See a simple (and useful) example of what algorithms are.
  • Understand why algebra is really useful – for proving algorithms ALWAYS work

Algorithms are magic. Even simple algorithms can sometimes look like witchcraft. My favourite is one of the ways the Tudors did multiplication. It is all down to Welsh Tudor polymath Robert Recorde. As well as being a mathematician, who wrote the first arithmetic text book, he was also the physician to two Tudor Monarchs: Edward VI and Mary. Not only that, but along the way he also invented the equal sign using it for the first time as a shorthand for the phrase “ is equalle to” when doing maths (he would have liked the C programming language!). He was particularly good at algorithms and his book contained a cunning way to make the times tables easier.

Learning times tables is a rite of passage of primary school students. Those up to 5 are not too difficult but the 6, 7, 8 and 9 times table are particularly hard to remember (though of course the 9 times table does have a cunning pattern that makes it easier). Robert Recorde had a solution. In his book he gave an algorithm that made those larger times tables easy. If you know your tables up to the 5 times table (the easy ones), then the rest become simple too. It is just a matter of knowing the algorithm and doing some simple subtractions combined with the multiplications you do know. That the algorithm works is barely believable though, it is so odd.

The Algorithm

Here is how it goes. Suppose you have two of those nasty higher numbers to multiply like 8×7.

  1. Draw 7 boxes labelled A, B, C, D, E, F and G. Write one of the numbers you want to multiply in box A and the other in box B.
    • eg if you want to calculate 8 x 7, put 8 in box A and 7 in box B.
  2. Subtract the number in box A from 10 and put the answer in box C.
    • 10-8 = 2, so put 2 in box C.
  3. Subtract the number in box B from 10 and put the answer in box D.
    • 10-7 = 3 , so put 3 in box D.
  4. Multiply the two numbers in box C and D together. Put the answer in box E.
    • 2 x 3 = 6 so we write 6 in box E
    • Because your original two numbers in A and B were above 5, the new ones you must multiply instead are both below 5 so its a nice easy multiplication.
  5. Now subtract the number in box C from Box B (ie the diagonal numbers) and multiply the answer by 10 (stick a 0 on the end) writing the answer in box F.
    • 7-2 = 5, so multiplying by 10 means you put 50 in box F.
  6. Construct the final answer in box G by adding the number in box F to the number in box E.
    • E holds 50 and F holds 6 so 50+6 = 56 is the answer to the original multiplication of 8×7.

TudorMultiplication.jpg

Try the algorithm yourself on some more examples, like 6×9, 7×6 and 8×9. It seems a bizarre way to do multiplication – were the Tudors slightly bonkers? Well possibly, but Robert Recorde was just very clever. At a stroke his clever algorithm gives a way to do all those hard multiplications using only a few much simpler calculations.

Does it always work?

This little computational ‘spell’ seems like witchcraft! Surely it doesn’t really always work? Actually it does. The point of an algorithm is that it always guarantees you get the right answer. We can prove this one does with a bit of algebra.  Of course, as long as you trust Recorde, you don’t have to understand the proof for the algorithm to work for you. It is good to do the proof though (or at least have a rigorous argument) to be sure the algorithm really is fool proof.

The Proof

STEP 1: Let’s call the number in box A, a, the number in box B, b and so on. So we are trying to work out the answer to:

ab (thats just another way to write: a x b)

Now (see the diagram below) instead of doing the multiplication directly we work out

TuderMultiplicationAlgebraProof.jpg

STEP 2: c = 10-a and

STEP 3: d = 10-b

We multiply these together e = c x d so to get the number in box E, replacing c and d by the terms they are equal to, we do

STEP 4:  e = (10-a)(10-b).

We also subtract 10-a from b, and multiply it by 10 to get the number in box F, so

STEP 5: f = 10(b-(10-a))

The final answer is then just g = e + f. This means the calculation we ultimately do is

STEP 6: g = 10(b-(10-a)) + (10-a)(10-b)

We need to show this value g is the same as a x b.  It looks a bit unlikely but let’s simplify it all.

g = 10(b-(10-a)) + (10-a)(10-b)

Expanding the brackets for the part that came from f gives:

= 10(b -10 + a) + (10-a)(10-b)

= 10b -100 + 10a + (10-a)(10-b)

Similarly, multiplying out the brackets from e’s part gives:

= 10b -100 + 10a + 100 -10a -10b + ab

Now having expanded everything, we simplify: the terms +100 and -100 cancel out

= 10b + 10a -10a -10b + ab

The +10b and -10b cancel out too.

= 10a -10a + ab

The +10a and -10a also cancel out, leaving just a single term.

= ab

So what this says is that following the algorithm leaves the answer of calculating a x b in box G which is just what we wanted.

Algorithms

Algorithms are just sequences of steps to follow that guarantee a result (whether you understand why it works or not). Here the result is to multiply two numbers doing only simpler calculations. Of course, computers don’t know what they are doing. They can only follow rules blindly. While perhaps not using exactly this algorithm, they do use lots of clever algorithms to allow them to do arithmetic quickly.

This bit of witchcraft also shows why algebra is such a useful thing. It is a great way of proving useful algorithms really do always work.

The Tudors may still mistakenly have believed in witchcraft, and may not have had computers, but their computational witchcraft was still a really useful thing.

This one is for Peter,  the only person I imagine ever to get spontaneous applause from a class of teenagers for algebra… and a wonderful computational magician. 

He also loved hiding Easter Eggs in our work.

Feedback matters

Here is the next in our series of tips about learning to learn (to program).

TIP 8 :  Immediate, Frequent Feedback Matters

Paul Curzon, Queen Mary University of London

The real key to deliberate practice, to putting in hours of practice that is as effective as possible, is to have immediate and frequent feedback. You need to find ways to be sure what you are doing is right (or wrong). You need to practice the right things and fix the causes when you get things wrong. Otherwise, with all that practice you could just  be getting better and better at doing it badly.

Building appropriate mental models of sub-skills is an important part of this as it can give a basis of being able to providing feedback yourself. The understanding you have can help you work out what you must have done wrong. When a musician plays the wrong note, if they can hear it sounds wrong, they have some feedback. They can work on that note until they consistently get it right.

Programming provides natural forms of feedback. If you write nonsense that isn’t a program at all, perhaps because a single bracket is missing, or because something was mis-spelled, then when you compile the program, the compiler will tell you about your mistakes. The feedback is immediate.  Compile your program frequently and you will get frequent feedback.

Similarly with a good test plan, and knowing what you are trying to implement you can get immediate feedback as to whether a program does the thing you intended or not in all situations.

This will only be helpful if you were not trying to do too much at once. If you spend days (or even hours) trying to write complex programs, before compiling and running then the feedback is not immediate. You only get feedback when you finally finish the whole thing. Therefore it is really, really important you practice by writing small programs, not large ones bigger than anything you’ve tried before.

When you do write larger programs, it is important that you build them a step at a time, adding to them a little at a time, then recompiling and testing them. This requires you to have understanding of the structure of programs as you need with each change to still have what you think is a valid program. This is a skill to gradually develop too.

So again we see that it is important to not try and make too large steps at once, to learn to program effectively.

It is because there are these natural feedback mechanisms in programming that many people teach themselves to program. As long as they are not put off by making mistakes and see them as learning opportunities they can use feedback from compiling and running programs to get better and better.

If you are a:

  • student
    • Practice writing small programs that introduce single new things at a time.
    • Write programs a little at a time, recompiling, running and testing frequently.
    • Don’t be frustrated by compiler messages, see them as feedback to help you improve.
    • Test programs thoroughly, not just once and then assume it works
  • teacher:
    • Set programming exercises that are small
    • For large programs encourage iterative development.
    • Provide exercises with test plans, teaching debugging skills.
    • Provide other mechanisms for immediate feedback if you can, eg marking programs on the spot as a student completes them, not having them handed in with feedback days or weeks later.

More on Learning to Learn (to program)


IoC logo on white

 

 

 

Draw Concept Maps

Here is the next in our series of tips about learning to learn (to program).

TIP 7 :  Reinforce understanding with concept maps

Paul Curzon, Queen Mary University of London

Once you have worked out the basics of a mental model (such as what a programming construct does), you need to reinforce and refine that understanding. You need to do that actively. Weak learners often try and memorise explanations by repetition but that doesn’t help understanding. Reading an explanation and then drawing a concept map, by contrast, is a powerful way to reinforce your understanding.

A concept map is just a simple kind of diagram. It has:

  • circles which represent concepts (think nouns) and
  • arrows between circles that show their relationship (think verbs)

You start by making a list of all the concepts (the nouns) that are relevant. For example, having encountered a print statement you might (based on your initial limited understanding) include in your list:

  • A print statement
  • A print command
  • A String

and draw them as circles. Then you work out how they are related with those links giving you the arrows. So you might draw a concept map of a print statement as:

PrintStatement1

This focusses on the structure – the bits that make up a print statement – rather than what it does. There are lots of ways to draw a concept map around any given concept or area – its not about right and wrong so much as getting down your current personal understanding. However, in programming you will get most benefit if the concept map focusses on what a programming construct does when it is executed.

Including what the print statement does may lead your next version of the concept map to be a little more sophisticated, so something like:

PrintStatement2

As you understand more then future versions will be more sophisticated still – for example you might in a later version include how the print statement actually takes a string expression not just a string and it is evaluated first to give a string value.

Reading (or listening to) the explanations of experts is important when creating concept maps as that is how you pick up the terminology of an expert – and so the concepts that matter like “statements” and “expressions”. To become an expert you need to talk the language of experts, not just have the skill of an expert. Concept maps can help bring together the terminology and your developing mental models.

Having created a concept map you can now turn it in to your own explanation, in your own words. From the above we get an explanation in our own words such as:

A print statement consists of a print command and a string. The execution of the print statement makes the string appear on the screen.

The benefit of drawing concept maps is it helps reinforce your understanding of the relationships of concepts to each other and to the concepts you have come across previously….and that is the core of what understanding is about.

If you are a:

  • student
    • Draw a concept map for each new programming concept you learn
    • Keep redrawing it again later as you understand more: you will probably be able to draw a more complex concept map.
    • Write explanations based on your concept map
  • teacher:
    • Show students how to draw concept maps
    • Provide some simple examples to show the idea, but remember the biggest benefits come when students create their own concept maps.
    • Set exercises to create concept maps for each new concept, once students have done some experimentation.
    • Set exercises to write prose explanations from concept maps.

More on Learning to Learn (to program)


IoC logo on white

 

 

 

Learning to Learn (to program): Experiment to learn

Here is the next in our series of tips about learning to learn (to program).

TIP 6 :  Build mental models by experimenting

Paul Curzon, Queen Mary University of London

Before you can practice effectively you need to have built the right mental models. Knowledge and skill join. One way to do this is to read explanations written by others. Sometimes there is a much better way: work it out for yourself! Learn by experimenting! For programming, this is a really powerful way to learn. Instead of building a mental model of constructs from explanations, first try and build your own mental models by reading programs others have written (simple ones to start with), and trying to work out how they work. Learn by making changes based on that and predicting what will happen, then trying by running the program.

This works well with programs because you can execute them and see what they do. Take a program, execute it, then look back at the program and see if you can see how it does what you can see it doing. Make a small change with a clear idea in your head now of what you think it wilo now do, then execute it again. If you were right then you have some confirmation of the mental model you have started to form. Try a different change, and so on.

To take a simple example, here is a Python program.

print "Hello World"

If you execute it, the following appears on your screen:

Hello World

Looking back at the program form an idea of what is happening… Try it before reading on.

 

The program prints messages, and there is only one line so that line must be a command to do so. Based on that, make a change to the program with a prediction that the new program will make Hello Paul (or perhaps your name) appear:

print "Hello Paul"

You execute it. It does. Now try a different change to the program:

print "Hello World"
print "Hello World"

What do you think it will do now? And so on…

You are working like a scientist, gradually building a theory based on experiment. As a good scientist you should look for changes that don’t just confirm your idea, but that will show you are wrong if you are, you want to stretch the edges of your understanding.

Once you have run out of experiments or are really stuck, then read (or listen to) the explanations. Now you have a solid basis to understand what they say. You know what they are talking about as you’ve seen it. You are also in a position to understand subtleties you have missed. If the explanations do tell you something you hadn’t worked out, go back and experiment with those aspects.

It is important that you don’t try and do too much in one go. Programs you start experimenting on should only be a little more complicated than you already understand. Changes you make should only be small and one at a time. If things go wrong, revert to a version that did work and you did understand.

Do this learning by experimentation with each new programming construct as you start to learn about it (having mastered the earlier ones first). Only read the explanations after you have experimented a little. You will understand and remember the explanations so much better that way round.

If you are a:

  • student
    • Don’t just rely on explanations, experiment with existing programs.
    • Don’t spend your time copying programs, spend it making small changes to existing programs and predicting what will happen.
  • teacher:
    • Encourage students to experiment and give them time to do so.
    • Provide a series of starting programs for them to experiment with.
    • Give them that code – don’t waste their time making them type it in.

Further Reading

A programming pedagogic framework that follows a similar investigative approach to this is PRIMM.

https://blogs.kcl.ac.uk/cser/2017/09/01/primm-a-structured-approach-to-teaching-programming/

A difference is we advocate above a first stage of Run code first to start a PRIMM like cycle with new constructs. The most important point though in both is that reading and predicting code in an experimental cycle matters.


More on Learning to Learn (to program)


IoC logo on white