CSC231 Factorial.asm
(Redirected from CSC220 Factorial.asm)
--D. Thiebaut 15:24, 22 November 2010 (UTC)
Contents
factorial.asm
Python Version
- A very simple python version:
def fact( n ):
if n <= 1:
return 1
return n * fact( n-1 )
def main():
N = input( "N? " )
print "fact( %d ) = %d" % ( N, fact( N ) )
Assembly Version 1
This version passes n to the recursive function fact() in eax, and gets n! back also in eax.
;;; factorial.asm
;;; D. Thiebaut
;;; computes factorial of n
;;; requires driver.c, asm_io.o, and asm_io.inc
;;;
;;; compile and link as follows:
;;;
;;; nasm -f elf -F stabs factorial.asm
;;; gcc -o factorial driver.c asm_io.o factorial.o
;;;
%include "asm_io.inc"
%assign EXIT 1
;; -------------------------
;; data segment
;; -------------------------
section .data
msg1 db "factorial(",0
msg2 db ") = ",0
i dd 0
;; -------------------------
;; code area
;; -------------------------
section .text
global asm_main
;;; ---------------------------------------------------------
;;; main program
;;; ---------------------------------------------------------
asm_main:
;;; for i in range( 10 ):
mov dword[i],0
for: cmp dword[i],10
jge done
;;; print "fact( %d ) = %d" % (i, fact(i) )
forBody:
mov eax, dword[i]
call fact
push eax ; save fact(i) in stack
mov eax, msg1
call print_string ; prints "fact( "
mov eax, dword[i] ; get i
call print_int ; print i
mov eax, msg2 ; print ") = "
call print_string
pop eax ; get fact(i) back from stack
call print_int ; print fact(i)
call print_nl ; next line
inc dword[i]
jmp for
done:
;; return to C program
ret
;;; ---------------------------------------------------------
;;; fact: computes the factorial of n passed in eax
;;; and returns result in eax
;;; ---------------------------------------------------------
fact: cmp eax,1
;; test for stopping condition
jg recurse
mov eax,1
ret
;; recursive step
recurse:
push eax ; save n in eax
dec eax ; n-1 in eax
call fact ; recursive call, get fact(n-1) in eax
pop ebx ; get n back, and save it in ebx
mul ebx ; edx:eax <-- eax * ebx (we drop edx)
ret
Assembly Version 2
This version passes n through the stack, and gets the result back in the stack.
;;; ; factorial.asm
;;; ; D. Thiebaut
;;; ; computes factorial of n
;;; ; requires driver.c, asm_io.o, and asm_io.inc
;;; ;
;;; ; compile and link as follows:
;;; ;
;;; ; nasm -f elf -F stabs factorial.asm
;;; ; ld -melf_i386 -o fact fact.o 231Lib.o
;;; ;
extern _printDec
extern _println
EXIT equ 1
;;; -------------------------
;;; data segment
;;; -------------------------
section .data
msg1 db "factorial(",0
msg2 db ") = ",0
i dd 0
;;; -------------------------
;;; code area
;;; -------------------------
section .text
global _start
;;; ; ---------------------------------------------------------
;;; ; main program
;;; ; ---------------------------------------------------------
_start:
;;; ; for ( int i=0; i<10; i++ )
mov dword[i],0
for: cmp dword[i],10
jge endFor
;;; ; print( fact(i) )
forBody:
mov eax, dword[i]
push eax ; make room in stack for returned value
push eax ; pass i
call fact
pop eax ; get i!
call _printDec
call _println
inc dword[i]
jmp for
endFor:
;;; return to OS
mov eax, EXIT
mov ebx, 0
int 0x80
;;; ; ---------------------------------------------------------
;;; ; fact: computes the factorial of n passed in the stack
;;; ; return n! in the stack
;;; ; +--------------+
;;; ; |(place for n!)| ebp+12
;;; ; +--------------+
;;; ; | n | ebp+8
;;; ; +--------------+
;;; ; | ret addr. * | ebp+4
;;; ; +--------------+
;;; ; | old ebp |<-- esp <-- ebp
;;; ; +--------------+
;;; ;
;;; ; ---------------------------------------------------------
fact: push ebp
mov ebp, esp
%define n dword[ebp+8]
%define nfact dword[ebp+12]
;;; test for stopping condition
cmp n, 1 ; n==1 ?
jg .recurse
mov nfact,1 ; yes, then n! = 1
pop ebp ; return to caller
ret 4
;;; recursive step
.recurse:
push eax ; save regs used
push ebx
push edx
mov eax, n
dec eax ; n-1 in eax
push eax ; make room for returned fact(n-1)
push eax ; pass n-1
call fact ; recursive call
pop ebx ; get fact(n-1) in ebx
mov eax, n
mul ebx ; edx:eax <-- n * (n-1)!
mov nfact, eax ; that's n!
; drop edx
pop edx ; restore regs
pop ebx
pop eax
pop ebp ; return
ret 4
A GUI Version in Python
- This is an illustration of how human beings would "play" factorial
# Illustrated factorial in Python 3
# D. Thiebaut
students = [ "Alka", "Marie", "Alex", "Fiona", "Siri", "Alka" ]
def fact( n, level ):
print( level*3*' ', students[level], "starting fact( %d )" % n )
if n <= 1:
print( level*3*' ', students[level], "n<=1 return 1" )
return 1
print( level*3*' ', students[level], "calling fact( %d )" % (n-1) )
temp = fact( n-1, level+1 )
print( level*3*' ', students[level], "got result: temp = ", temp )
print( level*3*' ', students[level], "returning %d*%d = %d" % (n, temp, n*temp) )
return n * temp
def main():
x = int( input( "N? " ) )
print( "fact( %d ) = %d\n" % ( x, fact( x, 0 ) ) )
main()
Output
N? 5
Alka starting fact( 5 )
Alka calling fact( 4 )
Marie starting fact( 4 )
Marie calling fact( 3 )
Alex starting fact( 3 )
Alex calling fact( 2 )
Fiona starting fact( 2 )
Fiona calling fact( 1 )
Siri starting fact( 1 )
Siri n<=1 return 1
Fiona got result: temp = 1
Fiona returning 2*1 = 2
Alex got result: temp = 2
Alex returning 3*2 = 6
Marie got result: temp = 6
Marie returning 4*6 = 24
Alka got result: temp = 24
Alka returning 5*24 = 120
fact( 5 ) = 120
