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
E quindi, in genere i numeri di fibonacci seguono la serie 1 , 1 , 2 , 3 , 5 , 8 ....
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)
Allora la formula che definisce la ricorsione diventa:
- Fib'(n) = Fib'(n-1)---+ Fib''(n-1)
- Fib''(n) = Fib'(n-1)
Cioè le coppie sono:
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