Euclid's Algorithm in MIX Assembly Language vs Scheme
I wrote my first assembly language program today, it was written in Donald Knuth’s MIX Assembly Language. Technically I’ve written some x86 assembly in a class in 2009, but it doesn’t count, it wasn’t a complete program, and I barely understood it.
It is an implementation of Euclid’s Algorithm to compute the greatest common divisor of two positive integers. Writing in an assembly language is so much more work than writing in a high-level language like Ruby, Scheme or even C. However, it gives a much better idea of how the computer actually works, and gives the programmer much more appreciation for all the nice abstractions we use in our day jobs and side projects.
The algorithm is the first example mentioned in The Art of Computer Programming. I found that just reading the algorithm alone doesn’t give much insight as to why it works, but reviewing a little bit of discrete math first, one can see where the steps come from.
First, start by assuming that m and n are positive integers, with m > n, and then the greatest common divisor d is the unique smallest integer such that:
Then, let r = m mod n (the remainder of m divided by n), we will prove that
All we need to show is that there are integers s and t such that
Note that since r = m mod n, it follows that r - m is a multiple of n, this means:
Now, we take the integers a,b in the definition of gcd(m,n) above and add -ar to both sides of the equation:
It is clear from the last equation above that s = (k+b) and t = a, which completes the proof.
Since gcd(m,n)=gcd(n,r), and r has the property that 0 ≤ r < n, we can reduce the problem to a smaller problem, and since the previous inequality always holds, it follows that r will eventually be 0, in which case n is the greatest common divisor.
This recursive form is very naturally captured in Scheme, Here’s the Scheme version (problem 2.01 in SICP):
1 2 3 4
To implement the same algorithm in MIX assembly language, we need to
use much more primitive concepts. Firstly, we designate the X register
to hold the value of m, the I1 register to hold the value of n, and
proceed using the
DIV operation to find the remainder.
Here’s the MIX assembly language version:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
I came up with the above code as an exercise in in MIX Assembly Language so that I could better understand the algorithms in the book. I have a hunch that it is not as efficient as it could be. I do a lot of swapping from registers to memory and back. Although to be fair, I couldn’t find a way to transfer data from a register to any of the other registers (kind of like the MOV instruction in x86 ), if someone knows of a way to do this, please correct me in the comments, I would like to know.