代码之家 › 专栏 › 技术社区 › KOB

访问变量索引处的数组

sieve mips32 sieve-of-eratosthenes mips arrays

KOB · 技术社区 · 8 年前

我是MIPS的新手,正在尝试编写上所述的Eratostenes筛选算法 Wikipedia 找到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 (非质数)。我怎么能用其他方法呢?如何在每次循环迭代时以不同的索引访问数组?

编辑

下面是我在审阅Craig的答案后得出的最终解决方案: (很抱歉缩进太差了,我的编辑写得不好)

    .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

1 回复 | 直到 8 年前

Craig Estey 8 年前

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

p ,将每个元素标记为非质数。 loop1 没有那样做。

看起来 回路1 正在执行步骤(4),然后 loop2 将执行步骤(3)。这实际上可以按相反的顺序进行。

为了简化操作,我维护了一个“数组结束”指针,而不是一个计数。并且,使用了 .byte 数组而不是 .word

以下是wiki版本:

    .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