在变量索引处访问数组

Question

我是MIPS的新品牌，正在尝试编写Wikipedia中所述的Eratosthenes算法筛选，以查找1到1000中的所有素数。我只是按照1- 4，还没有任何描述的改进。

这是到目前为止我的代码：

 .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: 

我知道，我的最后一行是无效的。我试图访问2p，3p，4p等每个索引处的数组，并将其值设置为0（不是素数）。我怎样才能以其他方式做到这一点？我如何在循环的每次迭代中访问不同索引处的数组？

编辑

这是我在阅读下面克雷格的回答最终的解决方案： （道歉为穷人缩进 - 它不能很好地从我的编辑复制）

.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 

Answer 1

起初，我无法理解你的程序相对于维基链接算法。

在维基的步骤（3）中，它将数组索引为p的倍数，将每个元素标记为非素数。 loop1没有这样做。

看起来loop1正在执行步骤（4），然后loop2将执行步骤（3）。这实际上可以按照相反的顺序进行。

我创建了两个程序从你的开始。我试图保持忠诚，但不得不重构一点点。一个遵守wiki中步骤的顺序。而第二个颠倒了秩序。

为了简化，我维护了一个“结束数组”指针而不是一个数。并且，使用.byte而不是.word来简化索引，因为该数组仅用作布尔向量[对于较大的数组，可以将其转换为位向量]。

---

这里的维基版本：

.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 

---

下面是一个反转的步骤之一：

.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