viernes, 1 de febrero de 2008

Recursion and Machine Language

Hanoi Towers

Recursive Algorithm in 8088 DEBUG

The first time I implemented the algorithm to solve the Hanoi Towers puzzle I was learning Pascal, and it was obviously the language I chose to do it. Some time later, I came across an old Motorola 6800 microprosessor development kit and went on and implemented the algorithm by assembling it on paper and punching in the machine codes with an hexadecimal keypad. The output was a 7 segment display!

There is nothing extraordinary about this, except for the fact that I applied a recursive algorithm directly in 6800uP machine language. I had two motivations for doing this: first, the recursive solution is very simple and required less coding and second, I was sick of all the buzz about "recursive languages" and how "magic" they were, and how dumb those "other", "non-recursive" languges were.

So, let's kick some computer nazis's but!


Fig. 1 Recursive Hanoi Algorithm in 8088 Assembly

Recently, I was teaching Excel VBA to a group of students and thought it would be fun to implement the Hanoi algorithm and use Excel graphics to show the "disks". I actualy did it and was really fun and exiting for the students who had never used Excel like that. I went on and thought why not relive the experience, but this time, with a modern PC type computer with display, keyboard and "debug.com" as the "assembler". Fig. 1 shows a "deluxe" version of the program which takes line parameters (N=3 to 9, otherwise assumes the default 3 disks) and prints new line characters.

Much Easier!

The following C++ code shows an implementation of the classical recursive solution. I intentionally defined the variables AX, DX and CX since those registers would be used in my assembly code.

The Algorithm in C

            

  • The poles A (source), B (intermediate) and C (destination) would go respectively to AX, CX and DX. Shame: such a waste!.
  • C++ parameters are: N (number of disks), AX (source), DX (destination) and CX (intermediate).
  • Notice that the first call to de procedure from the main program assigns each variable its "correct" pole. However, inside the procedure, there are two recursive calls with two parameters swapped in each respective call: The first call decrements N and swaps CX and DX (exchanges destination and intermediate). The second call decrements N and swaps AX and CX (exchanges source an intermediate). Between these two procedure calls, it prints N, AX (source) and DX (destination).
  • The fact that the procedure calls itself may seem a little awkward to follow at firs glance, but it actually is very straight forward.

Lets follow the example shown in the above C++ code: N=3, AX='A', DX='C' and CX='B'

Table I The state of "variables" on the run

The Assembly Code

This is the actual assembly code that fully implements the algorithm (see Fig. 2). Afterwards I created a "deluxe" version wich is shown in Fig. 1; is the same basic code with the addition of initialization code to accept N as a line parameter and an a little procedure to print new lines.

Fig. 2 DEBUG'S Recursive Hanoi First Run

Complete Listing in "Debugese"

            

The Saga Continues...

Don't Miss It:

SEE HERE: HANOI GOES BABYLON!

Sergio Otaño

2 comentarios:

Anónimo dijo...

I would like to exchange links with your site www.blogger.com
Is this possible?

Sergio Otaño dijo...

Could you give the URL?