View source for CSC231 Analysis of the Towers of Hanoi

--[[User:Thiebaut|D. Thiebaut]] 16:24, 25 November 2012 (EST)
----
=A High-Level Version in Python=

<br />
<source lang="python">
# hanoi.py  (Python V 2.7)
# D. Thiebaut
# implements the game of hanoi in python.
# uses recursion.
#
# to run, type 
#        python hanoi.py 
# at the command line

def moveDisk( source, dest, extra, n ):
    if n==1:
        print "move disk from %s to %s" % ( source, dest )
        return
    
    # more than 1 disk...
    moveDisk( source, extra, dest, n-1)
    print "move disk from %s to %s" % ( source, dest )
    moveDisk( extra, dest, source, n-1)

def main():
    while True:
        n = input( "# of disks? " )
        moveDisk( "A", "B", "C", n )

main()

</source>
<br />


=Top Down Approach: Version 1=

==Source==
In this version all we do is simply set a main program that calls the function '''moveDisks''' and passes it
* the number of disk to move (in al)
* the source peg (in bl)
* the destination peg (in cl)
* and the extra or temporary peg (in dl)

The '''moveDisks''' function prints a single move, testing the printMove function that prints "X Y" on a line by itself, indicating that a disk must be move from X to Y.

<br />
<source lang="asm">
;;; hanoi1.asm
;;; D.T.
;;; Towers of Hanoi, top down...


;;; assumptions:
;;; al = n   		Number of disk
;;; bl = Source 	character identifying the source
;;; cl = Dest		character identifying the destination
;;; dl = Temp		character identifying the extra peg

		section	.data
moveStr		db	"X --> X", 10
moveStrLen	equ	$-moveStr
source		equ	moveStr + 0
dest		equ	moveStr	+ 6	

	section	.text
	global	_start
;;; ------------------------------------------------------------
;;; M A I N
;;; ------------------------------------------------------------

_start: 	mov	al, 4	; move 4 disks
		mov	bl, 'A'	; from A
		mov	cl, 'B'	; to B
		mov	dl, 'C'	; using C as extra
	
		call	moveDisks

;;; return to OS
		mov	eax, 1
		mov	ebx, 0
		int	0x80

;;; ------------------------------------------------------------
;;; moveDisks:
;;; assumptions:
;;; al = n   		Number of disk
;;; bl = Source 	character identifying the source
;;; cl = Dest		character identifying the destination
;;; dl = Temp		character identifying the extra peg
;;; Does not return anything
;;; does not modify registers
;;; ------------------------------------------------------------
moveDisks:	push	ax
		push	bx
		push	cx
		push	dx

		mov	byte[source], bl
		mov	byte[dest], cl
		call	printMove
	
		pop	dx
		pop	cx
		pop	bx
		pop	ax
		ret

;;; ------------------------------------------------------------
;;; printMove
;;; Prints the string moveStr on the screen
;;; Does not alter any register
;;; ------------------------------------------------------------
printMove:	pushad
		mov	eax, 4
		mov	ebx, 1
		mov	ecx, moveStr
		mov	edx, moveStrLen
		int	0x80
		popad
		ret

</source>
<br />

==Output==

 [231a@beowulf ~/handout]$ nasmld hanoi1
 '''A --> B'''

=Top Down Version 2=

In this version we fully flesh out the recursive function.  It would be hard to go half way with the implementation of '''moveDisks'''.

==Source ==
<br />
<source lang="asm">
;;; hanoi2.asm
;;; D.T.
;;; Towers of Hanoi, top down...


;;; assumptions:
;;; al = n   		Number of disk
;;; bl = Source 	character identifying the source
;;; cl = Dest		character identifying the destination
;;; dl = Temp		character identifying the extra peg

%define		N	6	; number of disks to move
	
		section	.data
moveStr		db	"X X", 10
moveStrLen	equ	$-moveStr
source		equ	moveStr + 0
dest		equ	moveStr	+ 2	

	section	.text
	global	_start
;;; ------------------------------------------------------------
;;; M A I N
;;; ------------------------------------------------------------

_start: 	mov	al,  N	; move 4 disks
		mov	bl, 'A'	; from A
		mov	cl, 'B'	; to B
		mov	dl, 'C'	; using C as extra
	
		call	moveDisks

;;; return to OS
		mov	eax, 1
		mov	ebx, 0
		int	0x80

;;; ------------------------------------------------------------
;;; moveDisks:
;;; assumptions:
;;; al = n   		Number of disk
;;; bl = Source 	character identifying the source
;;; cl = Dest		character identifying the destination
;;; dl = Temp		character identifying the extra peg
;;; Does not return anything
;;; does not modify registers
;;; ------------------------------------------------------------
moveDisks:	push	ax
		push	bx
		push	cx
		push	dx

		cmp	al, 1
		ja	.recurse
	
;;; only 1 to move: move from source to dest!
		mov	byte[source], bl
		mov	byte[dest], cl
		call	printMove
		jmp	.return

.recurse:
;;; move n-1 disk from source to temp
		dec	al	; al <-- n-1
		xchg	cl, dl	; swap dest and temp
		call	moveDisks
		xchg	cl, dl	; swap back dest and temp
	
;;; move 1 from source to dest
		push	ax
		mov	al, 1
		mov	byte[source], bl
		mov	byte[dest], cl
		call	printMove
		pop	ax
	
;;; move n-1 disk from temp to dest
		xchg	bl, dl	; make temp the source
		call	moveDisks
	
.return:	pop	dx
		pop	cx
		pop	bx
		pop	ax
		ret

;;; ------------------------------------------------------------
;;; printMove
;;; Prints the string moveStr on the screen
;;; Does not alter any of the registers
;;; ------------------------------------------------------------
printMove:	pushad
		mov	eax, 4
		mov	ebx, 1
		mov	ecx, moveStr
		mov	edx, moveStrLen
;;; 		int	0x80
		popad
		ret


</source>
<br />
Note here that we are using a '''macro''', ''N'', defined by the '''%define''' statement.   This method of defining a constant is interesting as it allows us to modify the constant at assembly time.

Here's how.
* comment out the '''%define''' statement in the program (this will result in an undefined variable if we assemble as usual)
* when assembling the program, provide a value for the ''macro'' '''N''' as follows:

   nasm -f elf -F stabs '''-dN=4''' hanoi2.asm  ;  ld -melf_i386 -o hanoi2 hanoi2.o ; ./hanoi2

* The result will be that your program will be assembled just as if you had included the line 

   %define N 4

:inside your program.

The section below shows how to make the program run for several values of ''N'':

==Output==

<br />
<code><pre>
[231a@beowulf ~/handout]$ nasm -f elf -dN=2 -F stabs hanoi2.asm ; ld -melf_i386 -o hanoi2 hanoi2.o ; ./hanoi2
A C
A B
C B
[231a@beowulf ~/handout]$ nasm -f elf -dN=3 -F stabs hanoi2.asm ; ld -melf_i386 -o hanoi2 hanoi2.o ; ./hanoi2
A B
A C
B C
A B
C A
C B
A B
[231a@beowulf ~/handout]$ nasm -f elf -dN=4 -F stabs hanoi2.asm ; ld -melf_i386 -o hanoi2 hanoi2.o ; ./hanoi2
A C
A B
C B
A C
B A
B C
A C
A B
C B
C A
B A
C B
A C
A B
C B

</pre></code>
==Trick==
If we want to count the number of moves for a given number of disk, we can ''pipe'' the output of the '''./hanoi2''' program in the command '''wc''', which stands for '''word-count'''.  '''wc''' outputs the number of lines, number of words, and number of characters in the text given to it.

Below are the same commands as above, but filtered by '''wc''':

<code><pre>
[231a@beowulf ~/handout]$ nasm -f elf -dN=2 -F stabs hanoi2.asm ; ld -melf_i386 -o hanoi2 hanoi2.o ; ./hanoi2 | wc
      3       6      12
[231a@beowulf ~/handout]$ nasm -f elf -dN=3 -F stabs hanoi2.asm ; ld -melf_i386 -o hanoi2 hanoi2.o ; ./hanoi2 | wc
      7      14      28
[231a@beowulf ~/handout]$ nasm -f elf -dN=4 -F stabs hanoi2.asm ; ld -melf_i386 -o hanoi2 hanoi2.o ; ./hanoi2 | wc
     15      30      60

</pre></code>
We see that the number of moves for 2 disks is 3, for 3 disks it's 7, for 4 disks it's 15, for ''n'' disks, it's 2<sup>n</sup>-1.
<br />
=Estimating the Execution time=

==Call Tree of MoveDisks( 4, 'A', 'B', 'C' )==

<code><pre>
                                               N, Source, Dest, Extra


                                                     4,A,B,C
                                                        |
                            +---------------------------+-------------------------------+
                            |                           |                               |
                         3,A,C,B                      1,A,B,C                        3,C,B,A
                            |                                                           |
              +-------------+------------+                                 +------------+-------------+
              |             |            |                                 |            |             |
           2,A,B,C       1,A,C,B      2,B,C,A                           2,C,A,B      1,C,B,A       2,A,B,C
              |                          |                                 |                          |
     +--------+--------+        +--------+--------+               +--------+--------+        +--------+--------+
     |        |        |        |        |        |               |        |        |        |        |        |
  1,A,C,B  1,A,B,C  1,C,B,A  1,B,A,C  1,B,C,A  1,A,C,B         1,C,B,A  1,C,A,B  1,B,A,C  1,A,C,B  1,A,B,C  1,C,B,A
     |                 |        |                 |               |                 |        |                 |
  1,A,C,B           1,C,B,A  1,B,A,C           1,A,C,B         1,C,B,A           1,B,A,C  1,A,C,B           1,C,B,A

</pre></code>
<br />
Let's look at the top two levels of the tree:
<code><pre>
                                                     4,A,B,C
                                                        |
                            +---------------------------+-------------------------------+
                            |                           |                               |
                         3,A,C,B                      1,A,B,C                        3,C,B,A
                            |                                                           |
 
</pre></code>
We read it as follows.  

::''MoveDisks is called to move 4 disks from A to B, using C as an extra peg.  To do so it calls itself once to move 3 disks from A to C, to put them "out of the way", and uses B as a temporary peg to do so.  Then it moves 1 disk from A to B.  Then it has to move the 3 disks that were on C back to B where the belong, and it uses A as an extra peg in the process.''

==Instruction Count==

Let's figure out how many instructions are executed by the different parts:
<br />
<center>
{|class="wikitable" style="text-align: center; color: green;"
! Tree part 
! Number of instructions
|-
|
4,A,B,C                                                     
| 
Start function: 4 pushes + 1 cmp + 1 jump = 6
|-
|
3,A,C,B
|
Start recursion: 1 dec, 2 xchng, 1 call = 4
|-
|
1,A,B,C
|
Print 1 move: 6 instructions + printMove code = 6 + 7 + int 80
|-
|
3,C,B,A
|
Start 2nd recursion: 1 xchang, 1 call, 4 pops, 1 ret = 7
|}
</center>
We can see that we can figure out the number of instructions accurately except for the '''int 0x80''' instruction which is a total unknown.  We have ''no idea'' how many instructions Linux is executing to print the string on the screen.  So let's just comment out this instruction and see what we get.
<br />
                                               N, Source, Dest, Extra
 
 
                                                     4,A,B,C
                                                        |6
                            +---------------------------+-------------------------------+
                            |4                          |13                             |7
                         3,A,C,B                      1,A,B,C                        3,C,B,A
                            |6                                                          |6
              +-------------+------------+                                 +------------+-------------+
              |4            |13          |7                                |4           |13           |7
           2,A,B,C       1,A,C,B      2,B,C,A                           2,C,A,B      1,C,B,A       2,A,B,C
              |6                         |6                                |6                         |6
     +--------+--------+        +--------+--------+               +--------+--------+        +--------+--------+
     |4       |13      |7       |4       |13      |7              |4       |13      |7       |4       |13      |7
  1,A,C,B  1,A,B,C  1,C,B,A  1,B,A,C  1,B,C,A  1,A,C,B         1,C,B,A  1,C,A,B  1,B,A,C  1,A,C,B  1,A,B,C  1,C,B,A
     |6                |6       |6                |6              |6                |6       |6                |6
  1,A,C,B           1,C,B,A  1,B,A,C           1,A,C,B         1,C,B,A           1,B,A,C  1,A,C,B           1,C,B,A
    9+7	      	     9+7      9+7    	      	 9+7  	      	 9+7  	      	   9+7	    9+7	      	      9+7

<br />
Which simplifies to this:

 
      	      	 +--------------( )--------------+    	      	   (6+13)x1
      	      	 |    	      	 |    	      	 |
      	 +------( )------+    	      	 +------( )------+    	   (6+13)x2 + 11x2
      	 |       |     	|    	      	 |       |       |
     +--( )--+ 	     +--( )--+	     +--( )--+	     +--( )--+	   (6+13)x4 + 11x4
     |	 |   |	     |	 |   |	     |   |   |       |   |   |
    ( )     ( )	    ( )     ( )	    ( )     ( )     ( )     ( )	   (6+9+7)x8
     |	     |	     |       |	     |	     |	     |	     |	
 
 
The total number of instructions is thus (6+13) x ( 1 + 2 + 4 ) + 11 x (2 + 4 ) + (6+9+7)x 8

The tree above is for ''N''=4 disks.  The expression above simplifies to

 Number of Instructions  = (6+13)x( 2<sup>4-1</sup> - 1 ) + 11 x (2<sup>4-1</sup> - 2 ) + (6+9+7)x 2<sup>4-1</sup>
            
           = (6+13+11+6+9+7) x 2<sup>N-1</sup> - 6-13-11x2
 
           = 52 x 2<sup>N-1</sup> - 41
 
           &asymp; 52 x 2<sup>N-1</sup>                
<br />

<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
[[Category:CSC231]]