Highest Common Factor: Proving Euclid's Algorithm

The Euclidean algorithm will find the highest common factor of two numbers (the largest number that will divide both numbers). It is a rather simple algorithm to understand and implement having been discovered by the great mathematician Euclid of Alexandria 300 BC making it one of the oldest algorithms still applicable and in use in modern times.

Overview of Euclidean Algorithm

1.) Begin by inputting two numbers m and n
2.) If m < n then swap m and n (the larger number should be set to m)
3.) Divide m by n then get the remainder from this, r. If r = 0 then return n as the highest common factor and stop the algorithm.
4.) Let m = n and n = r. Repeat step 3.

The obvious questions here are "why does this work?" and "how do you know that the answer is always correct?". The best way to answer these questions is through an example.

Example: Find the highest common factor of 216 and 38.
From the algorithm we must set m = 216 and n = 38, m/n gives a remainder of 26. We now set m = 38 and n = 26, m/n gives a remainder of 12. Set m = 26 and n = 12, m/n gives a remainder of 2. Set m = 12 and n = 2, m/n gives a remainder of 0 so the highest common factor of 216 and 38 is 2.

It is clear from this algorithm that the important element from one step to the next relies on the fact that hcf(m,n) = hcf(n,r) is true. We will write this as a lemma.

This is how the algorithm works but it is not a proof as to that it will always work on any two integers, m and n. To prove this we will utilise how the algorithm in a more formal sense and then utilise those facts to prove the algorithm is consistent and thus correct.

And that is how and why the Euclidean algorithm works! It is relatively simple to program this algorithm and because of this and that it is very efficient it has many uses in mathematical programs, most importantly (to me!) is for prime checkers.

Python: Interaction and Variables

The majority of programs require some form of question and answer based interaction. And in Python it is a must know, it is also very easy to get to grips with too.

All variables have to be defined so they can be called up at a later stage in your program, this itself is not overly useful (other than perhaps when a large variable consistently comes up, like Pi).

This is no different with variables that need interaction. It is used so that whatever value the user inputs can be called up at a later point, makes sense right? There are only two main things you need to remember when setting interactive variables is whether the answer you want will be numerical or text based.

name = raw_input ("What is your name? ")

age = input ("How old are you? ")

The key differences here are 'raw_input' and 'input'. You use 'raw_input' for text based data and 'input' for numerical data, easy. The name is just what you apply to the variable that you use when you call it up, just remember that once the user inputs a name to this interactive variable it will not automatically be displayed, in order to do that you must print their variable, my example should make more sense.

name = raw_input ("What is your name? ")
age = input ("How old are you? ")
print "Hello,", name, age, "is a great age!"

This small program would look like this when ran:

What is your name? Mersenne
How old are you? 16
Hello, Mersenne 16 is a great age!

Remember how that if you want to show the solution to a mathematical problem you separate the problem with a comma? Well that's the same with variables you have defined, if you can remember these few simple rules you can begin to create more complex programs that involve user interaction.

Python: Mathematical Terminology

This will be my first actual "mini-python" lesson, I'm going to assume you've read my previous post on Python, if you haven't please read it: an introduction to Python. Got everything you need downloaded? Then I'll begin.

Again this is just going to cover the absolute basics, but they are incredibly vital to know. Maths is the core behind the majority of programs, regardless of what you want to program you're bound to come across maths at some point when programming (especially with my posts, seeing as I am mathematical nerd).

Most of the mathematical characters are fairly obvious; "*" meaning times, "+" meaning add, "-" meaning minus, "/" meaning divide and "=" meaning equals. Some of the less obvious ones are to the power of, "**" and to show the remainder when divided is "%". But once you can remember these it's very easy to apply these.

Another important thing to remember is that if you want to 'print' the answer to mathematical you do not use quotes, if you just want to show the expression you do.

print "2 + 2 =", 2+2

Will show:

2 + 2 = 4

Simple right? Just remember to separate the different strings you want to print with a comma. Now let's create a basic program using these concepts.

print "The area of a circle with radius 15 is", 3.142 * 15**2

That would show:

The area of a circle with radius 15 is 706.85834715

Try this out with different numbers, expressions and signs. Only through doing this yourself will you begin learning. In the next lesson I will bring in variables and begin coding a small working program where the user inputs data.

An introduction to Python

Now, I am by no means adept at python; far from it in fact. I have attempted to learn many programming languages several times, all end within a couple of days and finish up with me not wanting to touch another programming language again. But I got to thinking, I need to regularly update my blog and need ideas on what to do each post on. So I thought, I will update as a go along with mini lessons that should hopefully inspire and help people who are first beginning to code in Python.

Why Python first of all? Well, it is one of the simpler first languages to learn that is actually used by large corporations (one of the most notable are Walt Disney). It isn't exactly too complex to begin with and has a steady difficulty curve. And an added bonus? It's very mathematical!

The first thing you need to do really is download Python. The current version (as of 19th March 2011) is 3.2, but the majority of what I will discuss is from the 2.x versions, however they are not too different and the 3.x versions is basically just cleaned up from 2.x versions. However 2.x has a far greater library support, meaning custom variables that other people have created are much more readily available.

Download Python here. Another download that you may want is Notepad++ the amount of languages it recognises is pretty phenomenal; from HTML to Python and everything in between. If you'd like this brilliant open source software go here.

Once you've downloaded all of these we'll start you off with your first lesson. I will begin by introducing probably the most important command in Python, it's incredibly simple but is used to display any text.

"Hello world!" is the absolute must as it goes for starter programs, so that's what we'll do.

print "Hello world!"

When the program is ran it shows:

Hello world! 

 And that's it. Things to take note of are; the print command and the quotes. Any string of text has to have quotes surrounding it, else it does not make sense. And the print command has to come before any text you want to be "printed". And that's it for now, but the next lesson will be far more technical.