在變量索引處訪問數組

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