Witam, mam do napisania tym razem program który realizuje test millera-rabina dla argumentów podanych przez użytkownika. Oczywiście mój prowadzący, żeby nas rozpieścić kazał nam to napisać na symulatorze procesora MIPS R2000, PC-SPIM. Link do algorytmu http://www.algorytm.org/algorytmy-arytmetyczne/test-pierwszosci-test-millera-rabina.html
Nie wiem dlaczego program zawsze zwraca że liczba jest złożona. Jakieś pomysły?
Mój Kod
.text
main:
la $a0, powitanie #ładuje adres powitania do $a0
li $v0, 4 #zaladowanie 4, ktora odpowiada za wyswietlanie string
syscall
li $v0, 5 #funkcja do pobierania int pobieramy nasz n
syscall
move $s0, $v0 #skopiowanie n do $s0
la $a0, liczbak #ładuje adres liczbak do $a0
li $v0, 4 #zaladowanie 4, ktora odpowiada za wyswietlanie string
syscall
li $v0, 5 #pobieramy k
syscall
move $s1, $v0
sub $s2, $s0, 1 #n-1 w $s2
add $t0, 0 # S Obliczamy maksymalna potege 2 dzileca n-1
add $t1, 2 # liczba 2
j A
A:
add $t0, 1 #przechowuje s +1
move $t3, $zero
move $t2, $zero
add $t2, 1 # liczba 2
add $t3, 0 # ileosc petli B
j B
B:
mul $t2,$t2,$t1 #
add $t3, 1 #
blt $t3, $t0, B
rem $t4,$s2,$t2 # (n-1)mod 2^s do $t4
beq $t4, $zero, A
sub $t0, 1 # po ostatniej petli trzeba odjac od s
sub $t0,$t0, 1 # s-1 koniec przydzialu dla r
div $t2,$t2, 2 # dzielimy 2^s przez 2 po ostatniej petli+
#move $a0, $t2 #druk test
#li $v0,1
#syscall
div $s3,$s0,$t2 #d=n/(2^s)
move $t3, $zero
add $t3, 0 # licznink prob maksymlnie k prob
j D
D:
add $t3, 1
bgt $t3, $s1, K #jesli wokorzystano wszystkie probny n jest prawdopodobnie pierwsza
la $a0, pobranier #ładuje adres pobranier do $a0
li $v0, 4 #zaladowanie 4, ktora odpowiada za wyswietlanie string
syscall
li $v0, 5 #pobieramy r
syscall
move $s4, $v0
move $t4, $zero #do petli
add $t5, 1 #a^0
j C
C:
add $t4, 1
mul $t5,$t5,$s4 # a^0 * a potegowanie
blt $t4, $s3, C # d petli
rem $t6, $t5, $s0 # a^d mod n w $t6
bne $t6, 1, Z # przerwanie testku == liczba parzysta
j L
Z:
la $a0, test2 #ładuje adres koniecp do $a0
li $v0, 4 #zaladowanie 4, ktora odpowiada za wyswietlanie string
syscall
add $t7, 0 # r z przedialu <0,s-1>
add $t8, 1 # 2^r pierwsze r =0
j E
E:
beq $t8, 1, G # jesli 2^r rowne r pomijami d*(2^r)=d
mul $s5, $s3, $t8 # d*(2^r)
sub $s6, $s5, $s3 # d*(2^r)-d ilosc petli by uzystkac z a^d ,a^(d*(2^r))
add $t9, 0
#move $s7, $t6
j H
H:
mul $t6, $t6, $s4 # a^(d*(2^r)) bedzie w $t6
la $a0, test1 #ładuje adres koniecp do $a0
li $v0, 4 #zaladowanie 4, ktora odpowiada za wyswietlanie string
syscall
add $t9, 1
blt $t9, $s6, H
j G
G:
rem $s7,$t6,$s0 # a^(d*(2^r)) mod n
add $t3,$t3, 1 # wykorzystana +1 proba
mul $t8,$t8, 2 # kolejnka 2^r czyli to co bylo razy 2
add $t7, $t7, 1 # bierzemy kolejne r
beq $s7, $s2, D # jesli a^(d*(2^r)) mod n==(n-1) kontynujemy test
bgt $t7, $t0, L
j E
li $v0, 10 #przerwanie programu
syscall
K:
la $a0, koniecp #ładuje adres koniecp do $a0
li $v0, 4 #zaladowanie 4, ktora odpowiada za wyswietlanie string
syscall
li $v0, 10 #przerwanie programu
syscall
L:
la $a0, koniecn #ładuje adres koniecn do $a0
li $v0, 4 #zaladowanie 4, ktora odpowiada za wyswietlanie string
syscall
li $v0, 10 #przerwanie programu
syscall
.data
powitanie: .asciiz "\nWitaj w Tescie Millera-Rabina\nWpisz liczbe niepażysta z przedzialu <2,n>\n"
liczbak: .asciiz"Podaj liczbe k\n"
koniecn: .asciiz"Liczba jest złożona\n"
koniecp: .asciiz"Liczba jest prawdopodobnie pierwsza"
pobranier: .asciiz"\nprosze podac r z zakresu (1,n)"
test1: .asciiz"test 1\n"
test2: .asciiz"test 2\n"
test3: .asciiz"test 3\n"
test4: .asciiz"test 4\n"
test5: .asciiz"test 5\n"