[Assembly] Aiuto per un programma

Sick Boy · 27-12-2006, 12:38

ho bisogno di aiuto per un programmino assembly che calcola le 3-partizioni di un insieme:

lasciando stare il significato di 3-partizioni, il programma calcola una funzione a(n) in base al numero positivo n inserito, che ha 3 casi base e un caso ricorsivo:

- se n = 1 --> a(n) = 1
- se n = 2 --> a(n) = 2
- se n = 3 --> a(n) = 5

Mentre

per n >= 4

a(n) = a(n - 1) + [(n - 1) * a(n - 2)] + {[(n - 1) * (n - 2)]\2} * a(n - 3)

io sono arrivato ad un buon punto, ma la computazione mi restituisce risultati sbagliati perchè credo che calcolando a(n-1) o a(n-2) o a(n-3) rientra in uno dei casi base e mi esce dalla computazione prima di finire, con risultati diversi da quelli attesi..

ecco il codice di quello che ho fatto fin'ora!

Codice:

# DATA SEGMENT 
  
  .data 

# Stringhe che il programma utilizza per l'output 
Msg1: 
.asciiz "\n3-partizioni\n\nUn programma assembly per contare" 

Msg2: 
.asciiz " il numero di 3-partizioni di un numero naturale positivo" 

MsgMinZero: 
.asciiz "\nAttenzione! Il numero inserito e' minore di 0\nRipetere l'inserimento di n:\n" 

RicNum: 
.asciiz "\nInserire un numero intero n con n > 0 : " 

RisA: 
.asciiz "\nIl numero di 3-partizioni di insiemi di " 

RisB: 
.asciiz " elementi e': " 

RicA: 
.asciiz "\n\n1. Calcolare di nuovo\n2. Terminare il programma\n\n" 
RicB: 
.asciiz "Scegli: " 



# TEXT SEGMENT 

  .text 

main: 
  
# Descrizione programma 

  li $v0, 4        # $v0 a 4 --> print_string 
  la $a0, Msg1      # Carica la Stringa Msg1 in $a0 per successiva chiamata di sistema 
  syscall        # Stampa a video la seconda parte del messaggio di descrizione del programma 

  li $v0, 4        # $v0 a 4 --> print_string 
  la $a0, Msg2      # Carica la Stringa Msg1 in $a0 per successiva chiamata di sistema 
  syscall # Stampa a video la seconda parte del messaggio di descrizione del programma 

# Ricezione dell'input 

Ricomincia: 
  li $v0, 4          # $v0 a 4 --> print_string 
  la $a0, RicNum    # Carica la Stringa RicNum in $a0 per successiva chiamata di sistema 
  syscall          # Stampa a video la richiesta di un numero intero n > 0 

  li $v0, 5          # $v0 a 5 --> read_int 
  syscall          # Chimata di sistema - read_int 
  move $a1, $v0        # n --> $a1 
  


# CONTROLLO DELL'INPUT 

# Controllo il numero inserito non sia minore di 0: se il numero è minore di 0 
# salta ad Errminzero dove si comunica l'errore e 
# si ritorna alla fase di inserimento 
  
  blt $a1, $zero Errminzero # se n < 0 --> salta ad Errminzero 



  move $s1, $a1    # n --> $s1 


# Chiamata di procedura 

  
  jal Calcola     # Chiamata procedura di calcolo delle 3-partizioni 

  move $t0, $v0 # Risultato procedura --> $t0 


# RISULTATO 
  
  li $v0, 4        # $v0 a 4 --> print_string 
  la $a0, RisA     # Carico la Stringa nel registro $a0 per successiva chiamata di sistema 
  syscall        # Stampa a Video della stringa RisA 
  
  li $v0, 1   # $v0 a 1 --> print_int 
  move $a0, $s1      # Imposto $a0 con il valore iniziale di n 
  syscall        # Stampo a video il numero n inserito 
  
  li $v0, 4        # $v0 a 4 --> print_string 
  la $a0, RisB     # Stampa a video RisB 
  syscall 


  li $v0, 1 # $v0 a 1 --> print_int 
  move $a0, $t0 # Imposto $a0 al valore risultato precedentemente salvato in $t0 
  syscall # Stampa del risultato 


# RICHIESTA SE PROSEGUIRE CON NUOVO CALCOLO 

  
  li $v0, 4          # $v0 a 4 --> print_string 
  la $a0, RicA    # Stampa RicA 
  syscall 

Scelta:  
  li $v0, 4          # $v0 a 4 --> print_string 
  la $a0, RicB    # Stampa RicB 
  syscall 

  li $v0, 5       # $v0 a 5 --> read_int 
  syscall          # Chiamata di sistema per eseguire read_int 
  move $t0, $v0        # numero letto --> $t0 
  
  beq $t0, 1, Ricomincia  # Se = 1 --> nuova compurtazione 
  beq $t0, 2, Fine  # Se = 2 --> termina programma 
  j Scelta      # Se != 1 e != 2 --> scelta errata richiedi nuovamente di scegliere 



# PROCEDURA RICORSIVA DI CALCOLO 


# ALLOCAZIONE STACK 

Calcola: 

  subu $sp, $sp, 20    # Allocazione dello stack 
  sw $ra, 20($sp)    # Memorizza il return address 
  sw $s1, 4($sp)    # Alloca spazio per $s1 
  move $s1, $a1    # Memorizza n in $s1 
  sw $s2, 8($sp)    # Alloca spazio per $s2 
  sw $s3, 12($sp)    # Alloca spazio per $s3 
  sw $s0, 16($sp)    # Alloca spazio per $s3 



# CONTROLLO CASI PARTICOLARI 

#Il programma durante questa fase controlla se ci troviamo in uno dei casi particolari 
# 1) a(1) = 1 
# 2) a(2) = 2 
# 3) a(3) = 5 

#Se non ci troviamo in nessuno dei casi particolari il programma prosegue nella computazione di s(n,k) 
#sulla base della relazione di ricorenza 

  beq $s1, 1, Caso1 # se n = 0 --> caso 1 
  beq $s1, 2, Caso2 # se n = 2 --> caso 2 
  beq $s1, 3, Caso3 # se n = 3 --> caso 3 
  j NoCaso      # se n > 3 --> nessuno dei casi particolari 



# CASO BASE 1: a(1) = 1 

Caso1: 
  li $v0, 1 # $v0 --> 1 e prosegue con la fase finale della procedura 
  j FaseFinale 


# CASO BASE 2: a(2) = 2 

Caso2: 
   li $v0, 2 # $v0 --> 2 e prosegue con la fase finale della procedura 
   j FaseFinale 


# CASO BASE 3: a(3) = 5 

Caso3: 
   li $v0, 5 # $v0 --> 5 e prosegue con la fase finale della procedura 
   j FaseFinale 



# CASO PASSO : a(n) = a(n - 1) + (n - 1) * a(n - 2) + (((n - 1)*(n - 2))/2) * a(n - 3) con n > 3 

NoCaso: 

  addu $a1, $s1, -1    # Memorizzo n = n - 1 in $a1 
  jal Calcola      # Chiamata di procedura a(n - 1) 
  move $s2,$v0    # Memorizzo il risultato di a(n - 1) in $s2 

  addu $a0, $s1, -2    # Memorizzo n = n - 2 in $a0 
  jal Calcola      # Chiamata di procedura a(n - 2) 
  move $s3,$v0 # Memorizza il risultato di a(n - 2) in $s3 

  addu $a1, $s1, -1    # Memorizzo n = n - 1 in $a1 
  mul $a3,$a1,$s3    # Eseguo la moltiplicazione (n - 1) * a(n - 2) e la memorizzo in $a3 
  addu $a2,$s2,$a3    # Memorizzo a(n - 1) + (n - 1) * a(n - 2) in $a2 

  addu $a3, $s1, -3    # Memorizzo n = n - 3 in $a3 
  jal Calcola # Chiamata di procedura a(n - 3) 
  move $s0,$v0 # Memorizzo il risultato di a(n - 3) in $s0 

  addu $a0, $s1, -2    # Memorizzo n = n - 2 in $a0 
  mul $a0,$a0,$a1 # Eseguo la moltiplicazione (n - 1) * (n - 2) e la memorizzo in $a0 
  divu $a0,$a0, 2 # Eseguo la divisione ((n - 1) * (n - 2))/2 e la memorizzo in $a0 
  mul $a0,$a0,$s0 # Eseguo la moltiplicazione (((n - 1) * (n - 2))/2) * a(n - 3) e la memorizzo in $a0 

  addu $v0, $a2, $a0 # Calcolo di a(n) con n > 3 memorizzato in $v0 


# RIPRISTINO STACK E RITORNO AL CHIAMANTE 

FaseFinale: 

  lw $ra, 20($sp)    # Risetto il registro $ra con il corretto valore di Return Address 
  lw $s1, 4($sp)    # Ripristino $s1 
  lw $s2, 8($sp)    # Ripristino $s2 
  lw $s3, 12($sp)    # Ripristino $s3 
  lw $s0, 16($sp)    # Ripristino $s0 
  addu $sp, $sp, 20    # Deallocazione dello stack 
  jr $ra      # Ritorno al chiamante 



# SE INPUT MINORE DI ZERO 

Errminzero: 
  
  li $v0, 4     # $v0 a 4 --> print_string 
  la $a0, MsgMinZero  # Stampa Messaggio di errore 
  syscall 
  j Ricomincia #ritorna all'inizio del preogramma 


Fine: 
  li $v0, 10      # $v0 a 10 --> exit 
  syscall      # Chiamata d sistema exit

mi serve assolutamente una mano entro la fine dell'anno perchè è la data di consegna di questo programma!

aiuto!

recoil · 27-12-2006, 14:48

hai dimenticato di specificare che si tratta di assembly del MIPS, a occhio mi pare di riconoscerlo
io me lo ricordo ancora bene, se più tardi ho tempo do un'occhiata

Sick Boy · 27-12-2006, 14:59

grazie mille!

devo consegnarlo entro fine mese, quindi spero riuscirai ad aiutarmi, non dovrebbe essere un problema impossibile da risolvere

recoil · 27-12-2006, 21:53

Codice:

# DATA SEGMENT 
  
  .data 

# Stringhe che il programma utilizza per l'output 
Msg1: 
.asciiz "\n3-partizioni\n\nUn programma assembly per contare" 

Msg2: 
.asciiz " il numero di 3-partizioni di un numero naturale positivo" 

MsgMinZero: 
.asciiz "\nAttenzione! Il numero inserito e' minore di 0\nRipetere l'inserimento di n:\n" 

RicNum: 
.asciiz "\nInserire un numero intero n con n > 0 : " 

RisA: 
.asciiz "\nIl numero di 3-partizioni di insiemi di " 

RisB: 
.asciiz " elementi e': " 

RicA: 
.asciiz "\n\n1. Calcolare di nuovo\n2. Terminare il programma\n\n" 
RicB: 
.asciiz "Scegli: " 



# TEXT SEGMENT 

  .text 

main: 
  
# Descrizione programma 

  li $v0, 4        # $v0 a 4 --> print_string 
  la $a0, Msg1      # Carica la Stringa Msg1 in $a0 per successiva chiamata di sistema 
  syscall        # Stampa a video la seconda parte del messaggio di descrizione del programma 

  li $v0, 4        # $v0 a 4 --> print_string 
  la $a0, Msg2      # Carica la Stringa Msg1 in $a0 per successiva chiamata di sistema 
  syscall # Stampa a video la seconda parte del messaggio di descrizione del programma 

# Ricezione dell'input 

Ricomincia: 
  li $v0, 4          # $v0 a 4 --> print_string 
  la $a0, RicNum    # Carica la Stringa RicNum in $a0 per successiva chiamata di sistema 
  syscall          # Stampa a video la richiesta di un numero intero n > 0 

  li $v0, 5          # $v0 a 5 --> read_int 
  syscall          # Chimata di sistema - read_int 
  move $a1, $v0        # n --> $a1 
  


# CONTROLLO DELL'INPUT 

# Controllo il numero inserito non sia minore di 0: se il numero è minore di 0 
# salta ad Errminzero dove si comunica l'errore e 
# si ritorna alla fase di inserimento 
  
  blt $a1, $zero Errminzero # se n < 0 --> salta ad Errminzero 



  move $s1, $a1    # n --> $s1 


# Chiamata di procedura 

  
  jal Calcola     # Chiamata procedura di calcolo delle 3-partizioni 

  move $t0, $v0 # Risultato procedura --> $t0 


# RISULTATO 
  
  li $v0, 4        # $v0 a 4 --> print_string 
  la $a0, RisA     # Carico la Stringa nel registro $a0 per successiva chiamata di sistema 
  syscall        # Stampa a Video della stringa RisA 
  
  li $v0, 1   # $v0 a 1 --> print_int 
  move $a0, $s1      # Imposto $a0 con il valore iniziale di n 
  syscall        # Stampo a video il numero n inserito 
  
  li $v0, 4        # $v0 a 4 --> print_string 
  la $a0, RisB     # Stampa a video RisB 
  syscall 


  li $v0, 1 # $v0 a 1 --> print_int 
  move $a0, $t0 # Imposto $a0 al valore risultato precedentemente salvato in $t0 
  syscall # Stampa del risultato 


# RICHIESTA SE PROSEGUIRE CON NUOVO CALCOLO 

  
  li $v0, 4          # $v0 a 4 --> print_string 
  la $a0, RicA    # Stampa RicA 
  syscall 

Scelta:  
  li $v0, 4          # $v0 a 4 --> print_string 
  la $a0, RicB    # Stampa RicB 
  syscall 

  li $v0, 5       # $v0 a 5 --> read_int 
  syscall          # Chiamata di sistema per eseguire read_int 
  move $t0, $v0        # numero letto --> $t0 
  
  beq $t0, 1, Ricomincia  # Se = 1 --> nuova compurtazione 
  beq $t0, 2, Fine  # Se = 2 --> termina programma 
  j Scelta      # Se != 1 e != 2 --> scelta errata richiedi nuovamente di scegliere 



# PROCEDURA RICORSIVA DI CALCOLO 


# ALLOCAZIONE STACK 

Calcola: 

  subu $sp, $sp, 20    # Allocazione dello stack 
  sw $ra, 20($sp)    # Memorizza il return address 
  sw $s1, 4($sp)    # Alloca spazio per $s1 
  move $s1, $a1    # Memorizza n in $s1 
  sw $s2, 8($sp)    # Alloca spazio per $s2 
  sw $s3, 12($sp)    # Alloca spazio per $s3 
  sw $s0, 16($sp)    # Alloca spazio per $s3 



# CONTROLLO CASI PARTICOLARI 

#Il programma durante questa fase controlla se ci troviamo in uno dei casi particolari 
# 1) a(1) = 1 
# 2) a(2) = 2 
# 3) a(3) = 5 

#Se non ci troviamo in nessuno dei casi particolari il programma prosegue nella computazione di s(n,k) 
#sulla base della relazione di ricorenza 

  beq $s1, 1, Caso1 # se n = 0 --> caso 1 
  beq $s1, 2, Caso2 # se n = 2 --> caso 2 
  beq $s1, 3, Caso3 # se n = 3 --> caso 3 
  j NoCaso      # se n > 3 --> nessuno dei casi particolari 



# CASO BASE 1: a(1) = 1 

Caso1: 
  li $v0, 1 # $v0 --> 1 e prosegue con la fase finale della procedura 
  j FaseFinale 


# CASO BASE 2: a(2) = 2 

Caso2: 
   li $v0, 2 # $v0 --> 2 e prosegue con la fase finale della procedura 
   j FaseFinale 


# CASO BASE 3: a(3) = 5 

Caso3: 
   li $v0, 5 # $v0 --> 5 e prosegue con la fase finale della procedura 
   j FaseFinale 



# CASO PASSO : a(n) = a(n - 1) + (n - 1) * a(n - 2) + (((n - 1)*(n - 2))/2) * a(n - 3) con n > 3 

NoCaso: 

  addu $a1, $s1, -1    # Memorizzo n = n - 1 in $a1 
  jal Calcola      # Chiamata di procedura a(n - 1) 
  move $s2,$v0    # Memorizzo il risultato di a(n - 1) in $s2 

  addu $a1, $s1, -2    # Memorizzo n = n - 2 in $a1
  jal Calcola      # Chiamata di procedura a(n - 2) 
  move $s3,$v0 # Memorizza il risultato di a(n - 2) in $s3 

  addu $a1, $s1, -1    # Memorizzo n = n - 1 in $a1 
  mul $a3,$a1,$s3    # Eseguo la moltiplicazione (n - 1) * a(n - 2) e la memorizzo in $a3 
  addu $a2,$s2,$a3    # Memorizzo a(n - 1) + (n - 1) * a(n - 2) in $a2 

  addu $a1, $s1, -3    # Memorizzo n = n - 3 in $a1 non in $a3 <------
  jal Calcola # Chiamata di procedura a(n - 3) 
  move $s0,$v0 # Memorizzo il risultato di a(n - 3) in $s0 

  addu $a0, $s1, -2    # Memorizzo n = n - 2 in $a0 
  addu $a1, $s1, -1    # Memorizzo n = n - 1 in $a1 
  mul $a0,$a0,$a1 # Eseguo la moltiplicazione (n - 1) * (n - 2) e la memorizzo in $a0 
  divu $a0,$a0, 2 # Eseguo la divisione ((n - 1) * (n - 2))/2 e la memorizzo in $a0 
  mul $a0,$a0,$s0 # Eseguo la moltiplicazione (((n - 1) * (n - 2))/2) * a(n - 3) e la memorizzo in $a0 

  addu $v0, $a2, $a0 # Calcolo di a(n) con n > 3 memorizzato in $v0 


# RIPRISTINO STACK E RITORNO AL CHIAMANTE 

FaseFinale: 

  lw $ra, 20($sp)    # Risetto il registro $ra con il corretto valore di Return Address 
  lw $s1, 4($sp)    # Ripristino $s1 
  lw $s2, 8($sp)    # Ripristino $s2 
  lw $s3, 12($sp)    # Ripristino $s3 
  lw $s0, 16($sp)    # Ripristino $s0 
  addu $sp, $sp, 20    # Deallocazione dello stack 
  jr $ra      # Ritorno al chiamante 



# SE INPUT MINORE DI ZERO 

Errminzero: 
  
  li $v0, 4     # $v0 a 4 --> print_string 
  la $a0, MsgMinZero  # Stampa Messaggio di errore 
  syscall 
  j Ricomincia #ritorna all'inizio del preogramma 


Fine: 
  li $v0, 10      # $v0 a 10 --> exit 
  syscall      # Chiamata d sistema exit

ecco fatto, dando un'occhiata troverai sicuramente gli errori anche perché te li ho commentati
se stabilisci che in $a1 ci va la n prima della chiamata a funzione devi sempre usare $a1, non usare altri registri per memorizzare n - 2 e n - 3 poi fare la chiamata, venivano fuori dei valori sballatissimi

presumo funzioni ora, ma non l'ho testato. calcolando a "mano" ho visto che con n = 4 da 14 che dovrebbe essere giusto e con n = 5 da 46, poi non mi sono messo a fare altri trace a mente, mica sono matto

Sick Boy · 28-12-2006, 09:27

così va già meglio, ma ho notato che da valori maggiori o uguali a 7 i risultati sballano ancora!

ti lascio una lista di valori corretti:

a(4)=14
a(5)=46
a(6)=166
a(7)=652
a(8)=2780
a(9)=12644
a(10)=61136
a(11)=312676
a(12)=1680592
a(13)=9467680
a(14)=55704104
a(15)=341185496
a(16)=2170853456

27-12-2006, 14:48	#2
recoil Senior Member Iscritto dal: Jul 2002 Città: Milano Messaggi: 19138	hai dimenticato di specificare che si tratta di assembly del MIPS, a occhio mi pare di riconoscerlo io me lo ricordo ancora bene, se più tardi ho tempo do un'occhiata

27-12-2006, 14:59	#3
Sick Boy Senior Member Iscritto dal: Dec 2006 Città: Brescia Messaggi: 497	grazie mille! devo consegnarlo entro fine mese, quindi spero riuscirai ad aiutarmi, non dovrebbe essere un problema impossibile da risolvere

28-12-2006, 09:27	#5
Sick Boy Senior Member Iscritto dal: Dec 2006 Città: Brescia Messaggi: 497	così va già meglio, ma ho notato che da valori maggiori o uguali a 7 i risultati sballano ancora! ti lascio una lista di valori corretti: a(4)=14 a(5)=46 a(6)=166 a(7)=652 a(8)=2780 a(9)=12644 a(10)=61136 a(11)=312676 a(12)=1680592 a(13)=9467680 a(14)=55704104 a(15)=341185496 a(16)=2170853456

Strumenti
Mostra una versione stampabile Invia questa pagina per email