CSC231 Recursive Multiplication

--D. Thiebaut 15:10, 29 November 2010 (UTC)

---

Definition

• a and b are integers
• a is a positive integer and can be null
• algorithm
  • mult( a, b ) 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

#! /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()

Assembly Version

;;; ---------------------------------------------------------------------------
;;; 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