Difference between revisions of "CSC231 Homework 10 2012"

From dftwiki3
Jump to: navigation, search
(Created page with "--~~~~ ---- <bluebox> This assignment is due on 11/28/12 evening, at midnight. </bluebox> =Problem 1= Implement a recursive version of the Towers of Hanoi in assembly. You can...")
 
 
(11 intermediate revisions by the same user not shown)
Line 4: Line 4:
 
This assignment is due on 11/28/12 evening, at midnight.
 
This assignment is due on 11/28/12 evening, at midnight.
 
</bluebox>
 
</bluebox>
−
 
+
<onlydft>
 
=Problem 1=
 
=Problem 1=
 +
( 1 point for documentation, 1 point for efficiency, 2 points for correctness of implementation)
 +
<br />
  
−
Implement a recursive version of the Towers of Hanoi in assembly.
+
Your assignment is to implement a recursive version of the Towers of Hanoi in assembly.
  
 
You can use this Python version for inspiration:
 
You can use this Python version for inspiration:
Line 73: Line 75:
  
 
==Requirements==
 
==Requirements==
−
* Your program will call the recursive function moveDisk and pass it the characters 'A', 'B', 'C' and the number 5, and will display the same output as shown above.
+
* Your program will call the recursive function moveDisk and pass it the characters 'A', 'B', 'C' and the number 5, and will display an output similar to the one shown above.
−
* You can pass the parameters using registers for full credits, but you get 1/3 extra credits if you pass all four parameters through the stack.
+
* You may not pass the parameters via registers.  Instead you must pass all four parameters through the stack.
 +
* Your program will also output at the end of the output the number of moves that were performed.  You may not use a global variable to keep track of the count.  If you are not sure how to do this in assembly, modify the python program to make it display the number of moves, then translate the python program in assembly.
 +
 
 +
==Submission==
 +
 
 +
rsubmit hw10 hw10a.asm
 +
 
 +
=Problem #2: Optional and Extra Credits (0.6 points)=
 +
 
 +
First study the program below, which is purposefully undocumented, and which computes the 46th term of the Fibonacci series using a recursive function.
 +
<br />
 +
<source lang="asm">
 +
; recurseFib.asm
 +
; include dumpRegs.asm, available from solution page for Homework 9
 +
%include "dumpRegs.asm"
 +
 
 +
section .text
 +
 
 +
global _start
 +
 
 +
_start: push eax ; make room for return value
 +
push dword 46 ; compute fib(46)
 +
call fib
 +
pop eax ; get fib(46) in eax and display eax
 +
call dumpRegs
 +
 
 +
mov eax, 1
 +
mov ebx, 0
 +
int 0x80
 +
 
 +
 
 +
fib: push ebp
 +
mov ebp, esp
 +
;;; ebp+8 is N
 +
;;; ebp+12 is return value
 +
mov eax, [ebp+8]
 +
 
 +
cmp eax, 2
 +
jg .recurse
 +
mov dword [ebp+12], 1
 +
pop ebp
 +
ret 4
 +
 
 +
.recurse:
 +
push eax
 +
dec eax
 +
push eax
 +
call fib
 +
 
 +
mov eax, [ebp+8]
 +
sub eax, 2
 +
push eax
 +
push eax
 +
call fib
 +
 
 +
pop eax
 +
pop ebx
 +
add eax, ebx
 +
mov dword [ebp+12], eax
 +
 
 +
pop ebp
 +
ret 4
 +
</source>
 +
<br />
 +
* Run the program:
 +
 
 +
    ./recurseFib
 +
 
 +
* The output is:
 +
 
 +
+-----------------+
 +
<font color="magenta">| eax = 6D73 E55F |</font>
 +
| ebx = 43A5 3F82 |
 +
| ecx = 0000 0000 |
 +
| edx = 0000 0000 |
 +
| esi = 0000 0000 |
 +
| edi = 0000 0000 |
 +
+-----------------+
 +
 
 +
:indicating that fib(46) = 0x6d73e55f, or 1,836,311,903.  More interestingly for us, the program takes a significant amount of time to compute this result.  When I tested this program it took 19.39 seconds:
 +
 
 +
'''time recursFib'''
 +
 +
+-----------------+
 +
| eax = 6D73 E55F |
 +
| ebx = 43A5 3F82 |
 +
| ecx = 0000 0000 |
 +
| edx = 0000 0000 |
 +
| esi = 0000 0000 |
 +
| edi = 0000 0000 |
 +
+-----------------+
 +
'''<font color="magenta">19.392u</font>''' 0.006s 0:19.55 99.1% 0+0k 0+16io 0pf+0w
 +
 
 +
==Your assignment==
 +
 
 +
* Keep the recursive nature of the fib function but improve it so that the execution of the program becomes less than one second when launched on beowulf.
 +
* How much stack space is used by your program, expressed in dwords or bytes..  Explain how you compute the amount of stack space in the header of your program.
 +
 
 +
==Submission==
 +
* Store your documented and modified program in a file called hw10b.asm and submit it as follows:
 +
 
 +
    rsubmit  hw10 hw10b.asm
 +
 
 +
</onlydft>

Latest revision as of 17:38, 4 December 2017

--D. Thiebaut 20:51, 14 November 2012 (EST)

This assignment is due on 11/28/12 evening, at midnight.


...

Retrieved from "http://dominiquethiebaut.com/dftwiki3/index.php?title=CSC231_Homework_10_2012&oldid=32318"