#-----------------------------------------------------------------------------#
# Stirling
#
# Programma sviluppato con MIPSter 1.04, PCSpim 1.0, SPIM 6.5 su Windows 2000
# Il programma calcola la ricorrenza dei numeri di Stirling di seconda specie
#-----------------------------------------------------------------------------#
.data
#-----------------------------------------------------------------------------#
# Stringhe di testo utilizzate dal programma.
#-----------------------------------------------------------------------------#
ask_n:
.asciiz "\nInserisci n per S(n,k): "
ask_k:
.asciiz "\nInserisci k per S(n,k): "
risultato_a:
.asciiz "\nS("
risultato_b:
.asciiz ","
risultato_c:
.asciiz ") e' uguale a "
.text
.globl main
#-----------------------------------------------------------------------------#
# Corpo main del programma.
#-----------------------------------------------------------------------------#
main:
la $a0, ask_n # Richiesta del valore n di S(n,k)
li $v0, 4
syscall
li $v0, 5 # Memorizzazione del valore n in $t1
syscall # ($t1 utilizzato per la visualizzazione finale)
move $t1, $v0
la $a0, ask_k # Richiesta del valore n di S(n,k)
li $v0, 4
syscall
li $v0, 5 # Memorizzazione del valore k in $a1 e $t2
syscall # ($t2 utilizzato per la visualizzazione finale)
move $a1, $v0 # ($a1 utilizzato per il calcolo di S(n,k)
move $t2, $v0
move $a0, $t1 # Memorizzazione del valore n in $a0 per S(n,k)
jal Stirling # Chiamata della procedura di calcolo di S(n,k)
move $t0, $v0 # Memorizzazione di S(n,k) in $t0 (temporaneo)
#-----------------------------------------------------------------------------#
# Visualizzazione del risultato finale della computazione. #
# ( es.: S(5,2) è uguale a 15 ) #
#-----------------------------------------------------------------------------#
la $a0, risultato_a # Visualizzazione della stringa "S("
li $v0, 4
syscall
move $a0, $t1 # Visualizzazione di n inserito inizialmente
li $v0, 1
syscall
li $v0, 4 # Visualizzazione della stringa ","
la $a0, risultato_b
syscall
move $a0, $t2 # Visualizzazione di k inserito inizialmente
li $v0, 1
syscall
li $v0, 4 # Visualizzazione della stringa ") e' uguale a "
la $a0, risultato_c
syscall
move $a0, $t0 # Stampa del valore di S(n,k) calcolato
li $v0, 1
syscall
li $v0, 10 # Uscita dal programma
syscall
#-----------------------------------------------------------------------------#
# Calcolo di S(n,k) = S(n-1,k-1) + kS(n-1,k) tramite ricorsione.
#-----------------------------------------------------------------------------#
Stirling:
subu $sp, $sp, 20 # Allocazione dello stack
sw $ra, 16($sp) # Memorizzazione del return address
sw $s0, 4($sp)
move $s0, $a0 # Memorizzazione di n in $s0
sw $s1, 8($sp)
move $s1, $a1 # Memorizzazione di k in $s1
sw $s2, 12($sp)
#-----------------------------------------------------------------------------#
# Test di controllo dei valori di n e k.
#
# Viene considerato che S(n,k) risulta essere:
#
# S(n,k) = 1 se n = k oppure n > 1 e k = 1.
# S(n,k) = 0 se k > n.
#
# In tutti gli altri casi S(n,k) = S(n-1,k-1) + kS(n-1,k).
#
# Viene inoltre controllato che sia n, k > 0.
#-----------------------------------------------------------------------------#
beq $s0, $zero, zero # Controllo di correttezza dei valori
beq $s1, $zero, zero # Se n,k = 0 allora S(n,k) = 0
beq $s1, $s0, uno # Se k = n allora S(n,k) = 1
beq $s1, 1, k_equal_1 # Se k = 1 allora controlla se n > 1
bgt $s1, $s0, zero # Se k > n allora S(n,k) = 0
j end_check # In tutti gli altri casi fine controllo valori
k_equal_1: # Se k = 1
bgeu $s0, 1, uno # controlla se n > 1 e quindi S(n,k) = 1
j end_check # altrimenti fine del controllo dei valori
uno: # Se k = n oppure k = 1, n > 1
li $v0, 1 # allora S(n,k) = 1
j snk # e salta alla visualizzazione del valore finale
zero: # Se n = 0 oppure k = 0 oppure k > n
li $v0, 0 # allora S(n,k) = 0
j snk # e salta alla visualizzazione del valore finale
#-----------------------------------------------------------------------------#
# Vengono decrementati i valori di n e k secondo la formula di Stirling e si
# procede alla ricorsione di S(n-1,k-1) e kS(n-1,k)
#-----------------------------------------------------------------------------#
end_check:
addu $a0, $s0, -1 # Memorizza n = n - 1 in $a0
addu $a1,$s1,-1 # Memorizza k = k - 1 in $a1
jal Stirling # Chiamata della procedura per S(n-1,k-1)
move $s2,$v0 # Memorizza il risultato di S(n-1,k-1) in $s2
addu $a0,$s0,-1 # Memorizza n = n - 1 in $a0
move $a1,$s1 # Memorizza k in $a1
jal Stirling # Chiamata della procedura per S(n-1,k)
mul $v0,$v0,$a1 # Memorizza il risultato di kS(n-1,k) in $v0
addu $v0,$v0,$s2 # Memorizza S(n-1,k-1) + kS(n-1,k) in $v0
#-----------------------------------------------------------------------------#
# Ripristino dei valori dallo stack.
#-----------------------------------------------------------------------------#
snk:
lw $ra, 16($sp) # Ripristino del return address in $ra
lw $s0, 4($sp) # Ripristino di n in $s0
lw $s1, 8($sp) # Ripristino di k in $s1
lw $s2, 12($sp) # Ripristino di S(n,k) in $s2
addu $sp, $sp, 20 # Deallocazione dello stack
jr $ra # Ritorno al chiamante
#-----------------------------------------------------------------------------#
# FINE DEL PROGRAMMA
#-----------------------------------------------------------------------------#
