I am brand new to MIPS and am attempting to write the Sieve of Eratosthenes algorithm as described on Wikipedia to find all prime numbers from 1 to 1000. I am just following the steps outlined in 1-4, and not yet any of the refinements described.
Here is my code so far:
.data
array: .word 1:1000 # array[1000] = {1} (assume all are prime initially)
length: .word 1000
.text
.globl main
main: addi $t0, $zero, 1 # $t0 = 1 (counter)
la $s0, length # $s0 = &length
lw $s0, 0($s0) # $s0 = length
la $t1, array # $t1 = &array[0]
lw $t2, 0($t1) # $t2 = array[0]
addi $t2, $t2, -1 # $t2 = 0
sw $t2, 0($t1) # array[0] = $t2 = 0 (1 is not prime)
loop1: beq $t0, $s0, ToDo # if counter == length...
addi $t0, $t0, 1 # counter++
addi $t1, $t1, 4 # $t1 = &array[counter]
lw $t2, 0($t1) # $t2 = array[counter]
beq $t2, 0, loop1 # if $t2 is marked as not prime, move to next element
addi $t3, $zero, 1 # $t3 = 1 (multiplier)
addi $t4, $t0, 0 # $t4 = counter (p)
loop2: addi $t3, $t3, 1 # multiplier++
mul $t4, $t4, $t3 # $t4 = $t4 * multiplier (2p, 3p, 4p...)
bgt $t4, $s0, loop1 # if $t4 >= length, go to outer loop
la $t5, $t4($t1)
ToDo:
I know that my last line is not valid. I am attempting to access the array at each index of 2p, 3p, 4p, etc. and set their values to 0 (not prime). How can I do this some other way? How can I access the array at a different index at each iteration of the loop?
EDIT
Here is my final solution upon reviewing Craig's answer below: (apologies for the poor indenting - it doesn't copy well from my editor)
.data
array:
.word 1:1000 # array of 1000 '1's - 1 = prime, 0 = not prime
length:
.word 1000 # length of array
primeArray:
.word 0:200 # array of size 200 to store primes
.text
.globl main
main: addi $s0, $zero, 0 # counter = 0
la $s1, length # s1 = &length
lw $s1, 0($s1) # s1 = length
la $t0, array # t0 = &array[0]
sw $zero, 0($t0) # array[0] = 0 -> '1' is not prime
outerLoop:
beq $s0, $s1, gatherPrimes # if counter == length
addi $s0, $s0, 1 # counter++
addi $t0, $t0, 4 # t0 = &array[counter]
lw $t1, 0($t0) # t1 = array[counter]
beq $t1, $zero, outerLoop # if array[counter] is already not prime, continue
addi $t2, $s0, 1 # t2 = counter + 1
addi $t3, $t2, 0 # t3 = t2
innerLoop:
add $t3, $t3, $t2 # t3 = t3 + t2
bgt $t3, $s1, outerLoop # if t3 > length, break
addi $t4, $t3, -1 # t4 = t3 - 1
la $t5, array # t5 = &array[0]
sll $t6, $t4, 2 # t6 = t4 * 4 (offset)
add $t5, $t5, $t6 # t5 = &array[t3]
sw $zero, 0($t5) # array[t3] = 0 -> not prime
j innerLoop
gatherPrimes:
addi $s0, $zero, 0 # counter = 0
addi $s2, $zero, 0 # primeCounter = 0
la $t0, array # t0 = &array[0]
la $t2, primeArray # t2 = &primeArray[0]
loop:
beq $s0, $s1, exit # if counter == length, exit
lw $t1, 0($t0) # t1 = array[counter]
addi $s0, $s0, 1 # counter++
addi $t0, $t0, 4 # t0 = &array[counter]
beq $t1, $zero, loop # if array[i] is not prime, break
sw $s0, 0($t2) # primeArray[primeCounter] = counter
addi $s2, $s2, 1 # primeCounter++
addi $t2, $t2, 4 # t2 = &primeArray[primeCounter]
j loop
exit:
syscall
At first, I couldn't make sense of your program relative to the wiki linked algorithm.
In step (3) of the wiki, it indexes the array by multiples of p, marking each element as non-prime. loop1 didn't do that.
It seems loop1 was doing step (4) and then loop2 would be doing step (3). This is actually okay to do in reverse order.
I created two programs starting from yours. I tried to remain faithful, but had to refactor a fair bit. One that adheres to the order of steps in the wiki. And, a second one that reverses the order.
To simplify things, I maintained an "end-of-array" pointer rather than a count. And, used a .byte array instead of a .word to simplify the indexing as the array is only used as a boolean vector [for larger arrays, with some extra code, it could be converted to a bit vector].
Here's the wiki version:
.data
array: .byte 1:1000
earray:
# array[1000] = {1} (assume all are prime initially)
msg_nl: .asciiz "\n"
.text
.globl main
# registers:
# s0 -- address of array
# s1 -- address of end of array
#
# t0 -- value of array[current]
# t1 -- pointer to current array value being tested
# t2 -- current "p" value
main:
la $s0,array # get &array[0]
la $s1,earray # get pointer to end of array
sb $zero,0($s0) # 0 is not prime
sb $zero,1($s0) # 1 is not prime
li $t2,2 # p = 2
move $t1,$s0 # get &array[0]
addu $t1,$t1,$t2 # get &array[2]
addu $t1,$t1,$t2 # get &array[4]
j mark_start
# mark 2p, 3p, ... as not prime
mark_loop:
sb $zero,0($t1) # mark as not prime
addu $t1,$t1,$t2 # advance to next cell
mark_start:
blt $t1,$s1,mark_loop # done with this p? if no, loop
# find next higher prime than p
addu $t1,$s0,$t2 # get &array[p]
addiu $t1,$t1,1 # get &array[p + 1]
j find_start
find_loop:
lb $t0,0($t1) # is current number [still] prime?
bnez $t0,find_match # yes, fly
addiu $t1,$t1,1 # no, advance to next cell
find_start:
blt $t1,$s1,find_loop # over edge? if no, loop
j print_all # yes, sieve complete
# found new p value -- set up to restart marking loop
find_match:
sub $t2,$t1,$s0 # get the new p value
addu $t1,$t1,$t2 # get &array[2p]
j mark_start # restart the marking loop
# print all the primes
print_all:
move $t1,$s0 # get array start
li $t2,0 # get p value
print_loop:
bge $t1,$s1,main_exit # over edge? if yes, exit program
lb $t0,0($t1) # is current value prime?
bnez $t0,print_match # if yes, fly
print_next:
addi $t1,$t1,1 # advance to next array element
addiu $t2,$t2,1 # increment p
j print_loop
print_match:
li $v0,1
move $a0,$t2
syscall
li $v0,4
la $a0,msg_nl
syscall
j print_next
main_exit:
li $v0,10
syscall
Here's the one that reverses the steps:
.data
array: .byte 1:1000
earray:
# array[1000] = {1} (assume all are prime initially)
msg_nl: .asciiz "\n"
.text
.globl main
# registers:
# s0 -- address of array
# s1 -- address of end of array
#
# t0 -- value of array[current]
# t1 -- pointer to current array value being tested
# t2 -- current "p" value
main:
la $s0,array # get &array[0]
la $s1,earray # get pointer to end of array
sb $zero,0($s0) # 0 is not prime
sb $zero,1($s0) # 1 is not prime
li $t2,1 # p = 1
# find next higher prime than p
find_begin:
move $t1,$s0 # get &array[0]
addu $t1,$s0,$t2 # get &array[p]
addiu $t1,$t1,1 # get &array[p + 1]
j find_start
find_loop:
lb $t0,0($t1) # is current number [still] prime?
bnez $t0,find_match # yes, fly
addiu $t1,$t1,1 # no, advance to next cell
find_start:
blt $t1,$s1,find_loop # over edge? if no, loop
j print_all # yes, sieve complete
# found new p value -- set up to restart marking loop
find_match:
sub $t2,$t1,$s0 # get the new p value
addu $t1,$t1,$t2 # get &array[2p]
j mark_start # restart the marking loop
# mark 2p, 3p, ... as not prime
mark_loop:
sb $zero,0($t1) # mark as not prime
addu $t1,$t1,$t2 # advance to next cell (2p, 3p, 4p, ...)
mark_start:
blt $t1,$s1,mark_loop # done with this p? if no, loop
j find_begin
# print all the primes
print_all:
move $t1,$s0 # get array start
li $t2,0 # get p value
print_loop:
bge $t1,$s1,main_exit # over edge? if yes, exit program
lb $t0,0($t1) # is current value prime?
bnez $t0,print_match # if yes, fly
print_next:
addi $t1,$t1,1 # advance to next array element
addiu $t2,$t2,1 # increment p
j print_loop
print_match:
li $v0,1
move $a0,$t2
syscall
li $v0,4
la $a0,msg_nl
syscall
j print_next
main_exit:
li $v0,10
syscall