可変インデックスで配列にアクセスする

Question

私はMIPSの新版です。Wikipediaに記載されているように、Saper of Eratosthenesアルゴリズムを記述して、1から1000の素数をすべて見つけようとしています。 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（プライムではない）に設定しようとしています。どうすればいいですか？ループの各繰り返しで異なるインデックスで配列にアクセスするにはどうすればよいですか？

EDIT

ここでは、以下のクレイグの答えの見直し時に、私の最終的な解決策である：（貧しいインデントのために謝罪 - それは私の編集者からもコピーされません） を最初に

.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

は、ウィキリンクアルゴリズムと比べてプログラムの意味を理解できませんでした。

wikiのステップ（3）では、配列をpの倍数でインデックス付けし、各要素を非プライムとしてマークします。 loop1それをしなかった。

loop1はステップ（4）を実行していて、次にloop2がステップ（3）を実行しているようです。これは実際に逆の順序で行うのは大丈夫です。

私はあなたから2つのプログラムを作成しました。私は忠実にしようとしましたが、公正なビットをリファクタリングしなければなりませんでした。 wikiのステップの順序に従うもの。そして、順序を逆転させる第2のもの。

単純化するために、私は数ではなく「配列の終わり」ポインタを維持しました。また、配列がブール値ベクトルとしてのみ使用されるためインデックス作成を簡略化するために.wordの代わりに.byte配列を使用しました[大きな配列では、いくつかの余分なコードで、ビットベクトルに変換できる]。

---

ここウィキバージョンです：

.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