Visualizza wikitesto di Architettura degli elaboratori Turno 3/Progetti/Stirling

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

[[Categoria:Progetti]]