Difference between revisions of "CSC231 Recursive Multiplication"
(→Assembly Version) |
(→Assembly Version) |
||
| Line 79: | Line 79: | ||
;;; --------------------------------------------------------------------------- | ;;; --------------------------------------------------------------------------- | ||
asm_main: | asm_main: | ||
| − | mov eax, [ a ] | + | mov eax, [ a ] ; print a |
call print_int | call print_int | ||
call print_nl | call print_nl | ||
| − | mov eax, [ b ] | + | mov eax, [ b ] ; print b |
call print_int | call print_int | ||
call print_nl | call print_nl | ||
| − | push eax ; make room for | + | push eax ; make room for returned value |
| − | push dword[ a ] | + | push dword[ a ] ; pass a |
| − | push dword[ b ] | + | push dword[ b ] ; pass b |
| − | call mult | + | call mult ; call mult( a, b ) |
| − | pop eax | + | pop eax ; get product |
| − | call print_int | + | call print_int ; print it |
call print_nl | call print_nl | ||
call print_nl | call print_nl | ||
| Line 98: | Line 98: | ||
;;; --------------------------------------------------------------------------- | ;;; --------------------------------------------------------------------------- | ||
| − | ;;; stack | + | ;;; 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 | ;;; ?? <---ebp+16 | ||
;;; a <---ebp+12 | ;;; a <---ebp+12 | ||
| Line 104: | Line 111: | ||
;;; ret addr <---ebp+4 | ;;; ret addr <---ebp+4 | ||
;;; old ebp <---ebp | ;;; old ebp <---ebp | ||
| − | |||
| − | |||
| − | |||
| − | |||
;;; | ;;; | ||
mult: push ebp | mult: push ebp | ||
| Line 117: | Line 120: | ||
.if1: | .if1: | ||
| − | cmp m_a, 0 | + | cmp m_a, 0 ; is a == 0 ? |
jne .if2 | jne .if2 | ||
| − | mov m_result, 0 | + | mov m_result, 0 ; yes: return 0 |
pop ebp | pop ebp | ||
ret 2*4 | ret 2*4 | ||
| − | .if2: cmp m_a, 1 | + | .if2: cmp m_a, 1 ; is a == 1 ? |
| − | jne .else2 | + | jne .else2 |
| − | mov eax, m_b | + | mov eax, m_b ; yes: return b |
mov m_result, eax | mov m_result, eax | ||
pop ebp | pop ebp | ||
ret 2*4 | ret 2*4 | ||
| − | .else2: push eax ; make room | + | .else2: push eax ; make room for value returned |
| − | mov eax, m_a | + | mov eax, m_a ; by mult( ) |
dec eax | dec eax | ||
push eax ; pass a-1 | push eax ; pass a-1 | ||
| Line 141: | Line 144: | ||
add eax, ebx ; eax <-- b+(a-1)*b | add eax, ebx ; eax <-- b+(a-1)*b | ||
mov m_result, eax ; pass back | mov m_result, eax ; pass back | ||
| + | |||
pop ebp | pop ebp | ||
ret 2*4 | ret 2*4 | ||
| + | |||
</pre></code> | </pre></code> | ||
Revision as of 10:18, 29 November 2010
--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
