CSC231 Homework 8 2015

--D. Thiebaut (talk) 12:40, 2 December 2015 (EST)

---

This is the last homework, and it is due on 12/14/15, the last day of class, at 11:55 p.m.

Problem 1

Write an assembly program called hw8.asm that computes the product of 2 integer numbers recursively, using only additions, as the algorithm below illustrates.

Algorithm

Inputs

a and b are integers

a is a positive integer and can be null

Algorithm

mult( a, b ) is recursive, and returns a multiplied by b

if a==0 mult( a, b ) = 0

if a==1 mult( a, b ) = b

otherwise mult( a, b ) = mult( a-1, b ) + b

Python Version

Your program should emulate the Python program below, at least in the way the mult() function operates.

#! /usr/bin/python
# mult.py
# implements multiplication as a recursive
# process.  Works only with integers. a must
# be positive.
# mult( a, b ) = 0    if a == 0
# mult( a, b ) = b    if a == 1 
#              = b + mult( a-1, b ) otherwise
#

def mult( a, b ):
    if a==0: return 0
    if a==1: return b
    return b + mult( a-1, b )


def main():
    a = 0
    b = 100
    print "a = %d  b = %d  mult( %d, %d ) = %d " \
          % ( a, b, a, b, mult( a, b ) )


    a = 1
    b = 100
    print "a = %d  b = %d  mult( %d, %d ) = %d " \
          % ( a, b, a, b, mult( a, b ) )


    a = 3
    b = 100
    print "a = %d  b = %d  mult( %d, %d ) = %d " \
          % ( a, b, a, b, mult( a, b ) )


    a = 100
    b = 0
    print "a = %d  b = %d  mult( %d, %d ) = %d " \
          % ( a, b, a, b, mult( a, b ) )

main()

Note

• Only positive numbers will be used to test your program.

Main Program

• Your main program should prompt the user for 2 integers, as illustrated below, output a blank line, and then output the result.
• The blank line is important, as it will be used to separate input from output.
• Example of user interaction:

./hw8
> 3
> 10

30

./hw8
> 5
> 11

55

Additional Questions & Submission

• Document your code well! Your program will be reviewed for documentation and style.
• In the header of the program, indicate how much stack space will be used as a function of a and b. Express your answer in bytes.
• In the header of the program, indicate as well, how much faster or slower the recursive method implemented by your function is, relative to:

• The mul instruction.
• a for-loop that would accumulate the product of a and b by adding a to some sum b times, or by adding b to some sum a times.

You may assume that each instruction takes 1 cycle. Since we are interested in a ration, you don't need to specify the actual speed of the processor.

• Submit your program to Moodle, in the HW 8 section. The grade you get is only for the execution of the program. It may get reduced for poor style and/or documentation, or the use of the MUL instruction, which should not appear in your program!
• You do not need to submit the 231Lib.asm library.

<showafterdate after="20151215 00:00" before="20151230 00:00">

Solution Program

;;; ---------------------------------------------------------------------------
;;; mult.asm 
;;; D. Thiebaut
;;; computes the product of two positive integers a, and b, using
;;; a recursive method.
;;; ---------------------------------------------------------------------------
%include "asm_io.inc"

	section 	.data
a	dd		3
b	dd		100
	
	section		.text
	global		asm_main
;;; ---------------------------------------------------------------------------
asm_main:
	mov		eax, [ a ] 		; print a
	call		print_int
	call		print_nl
	
	mov		eax, [ b ] 		; print b
	call		print_int
	call		print_nl
	
	push		eax			; make room for returned value
	push		dword[ a ]              ; pass a
	push		dword[ b ]              ; pass b
	call		mult                    ; call mult( a, b )
	pop		eax                     ; get product
	call		print_int               ; print it
	call		print_nl
	call		print_nl
	ret
	
;;; ---------------------------------------------------------------------------
;;; mult( a, b )
;;; implements following algorithm:
;;; def mult( a, b ):
;;;     if a==0: return 0
;;;     if a==1: return b
;;;     return b + mult( a-1, b )
;;; 
;;;  stack after "mov ebp, esp"
;;;         ??     <---ebp+16
;;;          a     <---ebp+12
;;;          b     <---ebp+8
;;;       ret addr <---ebp+4
;;;       old ebp  <---ebp
;;; 
mult:	push		ebp
	mov		ebp, esp

%define m_result  dword[ebp+16]
%define m_a       dword[ebp+12]
%define m_b       dword[ebp+8]

.if1:	
	cmp		m_a, 0			; is a == 0 ?
	jne		.if2
	mov		m_result, 0 		; yes: return 0
	pop		ebp
	ret		2*4

.if2:	cmp		m_a, 1			; is a == 1 ?
	jne		.else2	
	mov		eax, m_b 		; yes: return b 
	mov		m_result, eax
	pop		ebp
	ret		2*4

.else2:	push		eax			; make room for value returned
	mov		eax, m_a		; by mult( )
	dec		eax
	push		eax			; pass a-1
	mov		eax, m_b
	push		eax			; pass b
	call		mult			; compute mult( a-1, b )
	pop		ebx			; ebx <-- (a-1)*b
	mov		eax, m_b		; eax <-- b
	add		eax, ebx		; eax <-- b+(a-1)*b
	mov		m_result, eax		; pass back
	
	pop		ebp
	ret		2*4

</showafterdate>