[Assembly MIPS] Funzione calcolo n primi logica di implementazione

[gabriele86]

Ciao a tutti devo creare un programma in assembly MIPS per verificare se il numero inserito è un numero primo, la parte di codice per le syscall per la gestione dell input da tastiere e la stampa delle relative stringhe ascii le ho già implementate, ora mi manca la parte del' implementazione della funzione per la verifica del numero primo...
Secondo la regola matematica un numero primo è un numero divisibile per se stesso e per 1 quindi il risultato delle operazioni deve restituire zero, il problema e che non mi ricordo come se e possibile implemenatre una doppia divisione in assembly o se devo usare 2 condizioni per memorizzare i risultati e poi fare un confronto tra di loro e se entrambi restituiscono 0 allora il numero è primo...

In java farei una cosa del genere

if(numerodigitato%numerodigitato==0&&numerodigitato%1==0)
[I]           [SIZE=2][COLOR=#000000]System.out.println ("il numero è primo");[/COLOR][/SIZE]                  [SIZE=2][COLOR=#000000]else[/COLOR][/SIZE]                    [SIZE=2][COLOR=#000000]System.out.println("Il numero non è primo");[/COLOR][/SIZE]         [/I][LEFT][COLOR=#000000]
[/COLOR][/LEFT]

é possibile anche in assembly una cosa così o devo memorizzare il resto delle singole divisioni è poi compararle, so che ci sono anche metodi più complessi per il calcolo del numero primo ma l'esercizio richiede l'implementazione più semplice

 

[Mr Storm]

La logica che hai adottato per la risoluzione del tuo problema non è corretta: infatti tutti i numeri sono divisibili per 1 e per sè stessi, quindi il tuo programma ti direbbe che ogni numero è primo, seguendo il tuo metodo. Quello che devi fare, invece, è verificare che il numero inserito n non sia divisibile per nessun altro numero <= n eccetto 1 e sè stesso! Il codice potrebbe essere questo:

#lettura del numero, supponiamo di metterlo in $t1
beq $t1, 1, nonprimo   #1 non è considerato un numero primo
addi $t0, $zero, 2     #t0 sarà il divisore che incrementeremo ad ogni ciclo
loop: beq $t0, $t1, primo #t0 = t1? se siamo arrivati a questo punto, tutte le divisioni hanno dato resto diverso da 0, quindi il numero è primo
      div $t1, $t0
      mfhi $t2                 #il resto della divisione viene messo nel registro speciale Hi; dobbiamo spostarlo per poterlo usare
      beq $t2, 0, nonprimo     #resto = 0? il numero non è primo
      addi $t0, $t0, 1         #incremento del divisore
      j loop
primo: #stampa che il numero è primo
      j exit
nonprimo: #stampa che il numero non è primo
exit: #fine

Chiaramente il codice è ottimizzabile: si potrebbe terminare il ciclo una volta raggiunta la metà del numero in input, o addirittura la radice quadrata; inoltre, si potrebbe ottimizzare ulteriormente controllando prima se il numero è pari e diverso da 2, quindi non primo, ed entrare nel loop solo per i numeri dispari e usando soltanto divisori dispari. Una cosa del genere insomma:

1. Input = 1? Non primo
2. Input pari?
   
   • Input pari a 2? Primo
   • Altrimenti non primo
3. Nessuno dei casi precedenti? Entrare nel ciclo (inizializzare il divisore a 3 e incrementarlo di 2 e non di uno ad ogni loop)

Spero di esserti stato d'aiuto :)

 

[gabriele86]

Ecco la versione quasi funzionante del programma ho aggiunto anche l'opzione nel caso che il numero nn sia primo per decidere se richiamare il main del programma e digitare un nuovo numero o uscire dal programma

#  Scrivere una funzione che calcola se il numero inserito è primo,
#  $a0 contiene l''argomento, $v0 il risultato

.data
arg:     .asciiz "\Digita un numero per verificare se è primo = "
ris:     .asciiz "Primo = "
stringa_d: .asciiz "Il numero non è primo si  desidera digitare un'altro numero (1=yes 0=no)"
Nuovalinea: .asciiz  "\n" #(lascia una riga vuota)    
.text
__start:li $v0, 4
     la $a0, arg
    syscall        # stampa richiesta argomento
    li  $v0, 5
    syscall        # legge l''argomento
    move $a0, $v0
     jal numeriprimi    # chiama la funzione numeriprimi
    move $s0,  $v0   # salva il risulto nella variabile $s0
    li $v0, 4
    la  $a0, ris
    syscall        # stampa messaggio
    move $a0, $s0
     li $v0, 1
    syscall        # stampa risultato
    li $v0, 10
         syscall        # termina
#lettura del numero

numeriprimi:beq  $a0, 1, nonprimo   #1 non è considerato un numero primo
addi $t0,  $zero, 2     #t0 sarà il divisore che incrementeremo ad ogni ciclo
loop:  beq $t0, $t1, primo #t0 = t1? se siamo arrivati a questo punto, tutte  le divisioni hanno dato resto diverso da 0, quindi il numero è primo
       div $t1, $t0
      mfhi $t2                 #il resto della  divisione viene messo nel registro speciale Hi; dobbiamo spostarlo per  poterlo usare
      beq $t2, 0, nonprimo     #resto = 0? il numero  non è primo
      addi $t0, $t0, 1         #incremento del divisore
       b  loop
nonprimo: la $a0, stringa_d # Visualizzazione della stringa  "Vuoi continuare?"
li $v0, 4
syscall

li $v0, 5 # Leggi il  Valore e inserisce una nuova linea
syscall


beq $v0, 1,  Ricomincia # Se il valore è diverso da 0 esci dal programma

li  $v0, 10 # Uscita dal programma
syscall

Ricomincia:
la  $a0,Nuovalinea # Visualizzazione della stringa "\n" (lascia una riga  vuota)
li $v0, 4
syscall
jal  __start #Se il valore è uguale a 1  ricomincia dal main 

primo: b  exit   #stampa che il numero è  primo
   
exit:    jr $ra        # esce dalla chiamata #fine

Quasi funzionanate perchè anche se il numero è primo entra cmq in un loop e richiama l'etichetta Ricomincia, qualche idea del percè o controllato e ricontrollato ma nn trovo l'errore.

 

[Mr Storm]

Ok, vedo che giustamente inserisci il valore letto in $a0, come prevedono le convenzioni sulle chiamate di funzioni... però dovresti anche modificare le prime due istruzioni del loop (beq e div), sostituendo $a0 a $t1 ;)

 

[gabriele86]

Sistematot grazie non mi ero accorto di non aver cambiato il registro nella divisione e nell uguaglianza o controllato e ricontrollato ma non lo vedevo

 

[Mr Storm]

Ora funziona tutto senza problemi?

 

[gabriele86]

Si si non esegue più un loop continuo

#  Scrivere una funzione che calcola se il numero inserito è primo,
#  $a0 contiene l''argomento, $v0 il risultato

.data
arg:     .asciiz "\Digita un numero per verificare se è primo = "
ris:     .asciiz "Primo = "
stringa_d: .asciiz "Il numero non è primo si  desidera digitare un'altro numero (1=yes 0=no)"
Nuovalinea: .asciiz  "\n" #(lascia una riga vuota)    
.text
__start:li $v0, 4
     la $a0, arg
    syscall        # stampa richiesta argomento
    li  $v0, 5
    syscall        # legge l''argomento
    move $a0, $v0
     jal numeriprimi    # chiama la funzione numeriprimi
    move $s0,  $v0   # salva il risulto nella variabile $s0
    li $v0, 4
    la  $a0, ris
    syscall        # stampa messaggio
    move $a0, $s0
     li $v0, 1
    syscall        # stampa risultato
    li $v0, 10
         syscall        # termina
#lettura del numero

numeriprimi:beq  $a0, 1, nonprimo   #1 non è considerato un numero primo
addi $t0,  $zero, 2     #t0 sarà il divisore che incrementeremo ad ogni ciclo
loop:  beq $t0, $a0, primo #t0 = t1? se siamo arrivati a questo punto, tutte  le divisioni hanno dato resto diverso da 0, quindi il numero è primo
       div $a0, $t0
      mfhi $t2                 #il resto della  divisione viene messo nel registro speciale Hi; dobbiamo spostarlo per  poterlo usare
      beq $t2, 0, nonprimo     #resto = 0? il numero  non è primo
      addi $t0, $t0, 1         #incremento del divisore
       b  loop
nonprimo: la $a0, stringa_d # Visualizzazione della stringa  "Vuoi continuare?"
li $v0, 4
syscall

li $v0, 5 # Leggi il  Valore e inserisce una nuova linea
syscall


beq $v0, 1,  Ricomincia # Se il valore è diverso da 0 esci dal programma

li  $v0, 10 # Uscita dal programma
syscall

Ricomincia:
la  $a0,Nuovalinea # Visualizzazione della stringa "\n" (lascia una riga  vuota)
li $v0, 4
syscall
jal  __start #Se il valore è uguale a 1  ricomincia dal main 

primo: b  exit   #Se il numero è primo salta  ad exit ed esce dall programma   
exit:    jr $ra        # esce dalla chiamata #fine

Prova a testarlo anche tu incaso, una cosa nel loop io ho usato b loop per far ripetere il ciclo e corretta come soluzione usare il b (brench) o ere più corretto usare un salto incondizionato j ? se anche nell'ultima istruzione nel del etichetta primo e corretto l'uso del b o è meglio usare il j ?

 

[Mr Storm]

Non avevo mai usato l'istruzione "b" prima d'ora per i salti incondizionati, ma sempre la "j" (non sapevo neanche esistesse, tra l'altro): visto che il programma funziona, ho provato a testarlo anch'io, suppongo vada bene :)