Riempimento degli elementi di una matrice

Programma che definisce una matrice 10x10 in cui ogni elemento assume come valore la somma dell'indice di riga e dell'indice di colonna, cioè matrice(i,j)=i---+j con i,j=0,...,9.

	  .data
	  nrig: .word 10		 # definizione del valore del numero di righe della matrice
	  ncol: .word 10		 # definizione del valore del numero di colonne della matrice
	  matrice: .word 0:100 # definizione dell'area di memoria che conterrà la matrice 
								  # (100 words inizializzate col valore 0)
	  .text
	  .globl main
main:
	  li $t0,0				 # in $t0 viene posto l'indice di riga i che assume valori da 0 a 9
	  li $t1,0				 # in $t1 viene posto l'indice di colonna j che assume valori da 0 a 9
	  li $t2,0				 # in $t2 viene posto l'indice k utilizzato per lo scorrimento delle 
								  # locazioni di memoria
	  lw $t3,nrig	
	  lw $t4,ncol				
ciclo:
	  add $t5, $t0, $t1
	  sw $t5, matrice($t2)
	  addi $t2, $t2, 4
	  addi $t1, $t1, 1
	  blt $t1, $t4, ciclo
	  li $t1, 0
	  addi $t0,$t0,1
	  blt $t0, $t3, ciclo
	  li $v0, 10
	  syscall

# Quando si carica il programma si può osservare che nell'area Data Segments si ha:
# a partire dall'indirizzo 0x10010000			
#  - i dati  0x0000000a 0x0000000a 0x00000000 0x0000000
#  - a partire dall'indirizzo 0x10010010 lo spazio riservato alla matrice	

Fattoriale di un numero intero (ricorsivo)

Programma che calcola il fattoriale di un numero in modo ricorsivo: dato il valore n di cui si vuole calcolare il fattoriale si ha che n!= n x (n-1)! = n x (n-1) x (n-2)! = ... Si procede quindi chiamando fatt (etichetta della parte ricorsiva di programma) sul valore n, si decrementa n e si chiama fatt su n-1 e cosi' via. Ogni volta che si procede ad una nuova chiamata bisogna memorizzare nella pila il valore su cui si va a fare la nuova chiamata e l'indirizzo a cui si vuole tornare alla chiusura di tale chiamata. Osservate che venono usati rispettivamente i registri $a0 per passare il valore e $v0 per riportare il risultato come indicato nelle convenzioni dell'uso dei registri per le chiamate a procedura.

	  .data
	  elemento: .word 4  # definizione del valore di cui si vuole calcolare il fattoriale
	  .text
	  .globl main
main:
	  lw $a0,elemento	# si carica nel registro $a0 elemento (cioè il valore 4)
	  jal fatt			 # salto all'etichetta fatt e memorizzazione dell'indirizzo dell'istruzione
							  # successiva nel registro $31 cioè $ra (ove la sigla ra sta proprio per
							  # return address)
	  move $t0, $v0	  # pone il contenuto del registro $v0 nel registro $t0
	  li $v0,10			# pone nel registro $v0 il valore 10  (codice numerico per la chiamata a
							  # sistema operativo che esegue la terminazione del programma)
	  syscall			  # chiamata a sistema operativo

fatt:
	 beq $a0, $0, esci  # salto all'etichetta esci se il valore attuale di elemento (contenuto nel
							  # registro $a0) è zero
	 subu $sp, $sp, 8	# il valore del puntatore alla pila (registro $sp - stack pointer) viene
							  # decrementato di 8 (8 byte corrispondono a due parole di memoria ognuna 
							  # di 32 bit
	 sw $ra,4($sp)		# si pone il valore presente nel registro $ra nella pila, precisamente nella
							  # locazione precedente a quella indicata dal puntatore alla pila: 4($sp)
	 sw $a0,8($sp)		# si pone il valore presente nel registro $a0 nella pila, precisamente nella
							  # locazione precedente di due posizioni rispetto a quella indicata dal
							  # puntatore alla pila: 8($sp)
	 sub $a0,$a0,1		# si decrementa elemento di uno
	 jal fatt			  # salto all'etichetta fatt
	 lw $a0,8($sp)		# recupero del valore presente nella pila da porre nel registro $a0	
	 lw $ra,4($sp)		# recupero del valore presente nella pila da porre nel registro $ra	
	 mul $v0, $a0,$v0	# si moltiplica il valore attuale contenuto in $v0 con il valore in $a0
							  # appena recuperato dalla pila e si pone in $v0
	 add $sp, $sp,8	  # si aggiorna il valore del puntatore alla pila poichè i dati dono stati
							  # recuperati
	 jr $ra				 # salto all'indirizzo contenuto nel registro $ra (ultimo valore recuperato
							  # dalla pila)

esci:						# si arriva a questa etichetta se il valore attuale di $a0 è zero cioè se
							  #l'ultimo valore di $a0 posto nella pila è uno 
	 li $v0,1			  # inizializzazione del valore di $v0, cioè del fattoriale, con il valore di
							  # $a0 che è uno
	 jr $ra				 # salto all'indirizzo contenuto nel registro $ra

-- AnnalisaMassini - 16 Mar 2001

Numeri di Fibonacci, versione ricorsiva di complessità esponenziale

Programma che calcola il numero di Fibonacci di un numero in modo ricorsivo: dato il valore n di cui si vuole calcolare il numero di Fibonacci si ha che:

• Fib(n) = Fib(n-1)---+Fib(n-2) se n>1
• Fib(1) = 1
• Fib(0) = 1

Si procede quindi chiamando Fib (etichetta della parte ricorsiva di programma) sul valore n, si decrementa n e si chiama Fib su n-1 e di nuovo su n-2, quindi si sommano i due risultati.

Ogni volta che si procede ad una nuova chiamata bisogna memorizzare nella pila il valore su cui si va a fare la nuova chiamata e l'indirizzo a cui si vuole tornare alla chiusura di tale chiamata.

Osservate che venono usati rispettivamente i registri $a0 per passare il valore e $v0 per riportare il risultato come indicato nelle convenzioni dell'uso dei registri per le chiamate a procedura, ed inoltre che il registro temporaneo $t0 va anch'esso salvato su stack.

	  .data
	  elemento: .word 4  # definizione del valore di cui si vuole calcolare il numero di Fibonacci
	  .text
	  .globl main
main:
	  lw $a0,elemento	# si carica nel registro $a0 elemento (cioè il valore 4)
	  li $t1, 1			# carico in $t1 la costante 1 necessaria al confronto ble
	  jal Fib			  # salto all'etichetta Fib e memorizzazione dell'indirizzo dell'istruzione
							  # successiva nel registro $ra (ove la sigla ra sta proprio per return address)
	  move $t0, $v0	  # pone il contenuto del registro $v0 nel registro $t0
	  li $v0,10			# pone nel registro $v0 il valore 10  (codice numerico della syscall per la terminazione del programma)
	  syscall			  # chiamata a sistema operativo

Fib:
	 ble $a0, $t1, esci # salto all'etichetta esci se il valore attuale di n (contenuto nel registro $a0) è zero o 1
	 subu $sp, $sp, 12  # il valore del puntatore alla pila (registro $sp - stack pointer) viene
							  # decrementato di 12 (12 byte corrispondono a tre parole di memoria ognuna di 32 bit)
	 sw $ra,4($sp)		# si pone il valore presente nel registro $ra nella pila, precisamente nella
							  # locazione precedente a quella indicata dal puntatore alla pila: 4($sp)
	 sw $a0,8($sp)		# si pone il valore presente nel registro $a0 nella pila, precisamente nella
							  # locazione precedente di due posizioni rispetto a quella indicata dal puntatore alla pila: 8($sp)
	 sw $t0,12($sp)	  # si pone il valore presente nel registro $t0 nella pila
	 sub $a0,$a0,1		# si decrementa n di uno
	 jal Fib				# salto all'etichetta Fib (calcolo Fib(n-1)
	 move $t0, $v0		# si tiene da parte (in $t0) il valore di Fib(n-1)
	 sub $a0,$a0,1		# si decrementa n di uno
	 jal Fib				# salto all'etichetta Fib (calcolo Fib(n-2))
	 add $v0, $v0, $t0  # somma di Fib(n-1) e Fib(n-2)
	 lw $t0,12($sp)	  # recupero del valore presente nella pila da porre nel registro $t0	
	 lw $a0,8($sp)		# recupero del valore presente nella pila da porre nel registro $a0	
	 lw $ra,4($sp)		# recupero del valore presente nella pila da porre nel registro $ra	
	 add $sp, $sp,12	 # si aggiorna il valore del puntatore alla pila poichè i dati dono stati recuperati
	 jr $ra				 # salto all'indirizzo contenuto nel registro $ra (recuperato dalla pila)

esci:						# si arriva a questa etichetta se il valore attuale di $a0 è zero o 1
	 li $v0,1			  # inizializzazione del valore di $v0, cioè del numero di Fibonacci, con il valore 1
	 jr $ra				 # salto all'indirizzo contenuto nel registro $ra

Si noti che, dato che per ogni chiamata di Fib vengono in genere eseguite 2 chiamate ricorsive della stessa funzione, il numero di chiamate eseguite da questa versione di Fib sara' esponenziale (dell'ordine di 2 alla n)

Numeri di Fibonacci, versione ricorsiva di complessità lineare

Per rendere la funzione di Fibonacci più efficiente notiamo che se Fib(n) tornasse la coppia di valori che possiamo chiamare:

• Fib'(n) = Fib(n)
• Fib''(n) = Fib(n-1)

• Fib'(n) = Fib'(n-1)---+ Fib''(n-1)
• Fib''(n) = Fib'(n-1)

n
1	1	1
2		1	2
3			2	3
4				3	5
5					5	8

Il programma precedente si modifica come segue:

	  .data
	  elemento: .word 4  # definizione del valore di cui si vuole calcolare il numero di Fibonacci
	  .text
	  .globl main
main:
	  lw $a0,elemento	# si carica nel registro $a0 elemento (cioè il valore 4)
	  li $t1, 1			# carico in $t1 la costante 1 necessaria al confronto ble
	  jal Fib			  # salto all'etichetta Fib e memorizzazione dell'indirizzo dell'istruzione
							  # successiva nel registro $ra (ove la sigla ra sta proprio per return address)
	  move $t0, $v0	  # pone il contenuto del registro $v0 nel registro $t0
	  li $v0,10			# pone nel registro $v0 il valore 10  (codice numerico della syscall per la terminazione del programma)
	  syscall			  # chiamata a sistema operativo

Fib:
	 ble $a0, $t1, esci # salto all'etichetta esci se il valore attuale di n (contenuto nel registro $a0) è zero o 1
	 subu $sp, $sp, 8	# il valore del puntatore alla pila (registro $sp - stack pointer) viene
							  # decrementato di 8 (8 byte corrispondono a due parole di memoria ognuna di 32 bit)
	 sw $ra,4($sp)		# si pone il valore presente nel registro $ra nella pila, precisamente nella
							  # locazione precedente a quella indicata dal puntatore alla pila: 4($sp)
	 sw $a0,8($sp)		# si pone il valore presente nel registro $a0 nella pila, precisamente nella
							  # locazione precedente di due posizioni rispetto a quella indicata dal puntatore alla pila: 8($sp)
	 sub $a0,$a0,1		# si decrementa n di uno
	 jal Fib				# salto all'etichetta Fib (calcolo Fib(n-1)
	 move $t0, $v0		# si sposta in $t0 il valore di Fib'(n-1)
	 add $v0, $v1, $t0  # somma di Fib'(n-1) e Fib''(n-1)
	 move $v1, $t0		# si sposta Fib'(n-1) in $v1 (così diventa Fib''(n))
	 lw $a0,8($sp)		# recupero del valore presente nella pila da porre nel registro $a0	
	 lw $ra,4($sp)		# recupero del valore presente nella pila da porre nel registro $ra	
	 add $sp, $sp,8	  # si aggiorna il valore del puntatore alla pila poichè i dati dono stati recuperati
	 jr $ra				 # salto all'indirizzo contenuto nel registro $ra (recuperato dalla pila)

esci:						# si arriva a questa etichetta se il valore attuale di $a0 è zero o 1
	 li $v0,1			  # inizializzazione del valore di $v0, cioè del numero di Fibonacci, con il valore 1
	 li $v1,1			  # carico il $v1 il secondo numero della coppia 
	 jr $ra				 # salto all'indirizzo contenuto nel registro $ra

Dato che questa versione di Fib chiama se stessa solo una volta il numero di chiamate ricorsive della funzione Fib e' pari a n, cioe' la complessita' della funzione e' lineare.

-- AndreaSterbini - 16 Mar 2001