1
\$\begingroup\$

I'm new to assembly and I'm learning on my own, so I'd appreciate the feedback. My priorities are correctness (on all MIPS-32 with sllv) > speed > readability (including following idioms).

I've only "manually" tested the code, but it seems correct for numbers 0-40, and on/around a selection of larger primes (including on/around the largest prime, 2147483647). I'm using QtSpim, but I'd prefer my code to work on any MIPS machine.

My comments are quite inconsistent. I'm trying to find a better style.

Making sense of the algorithm

I must search through all potential divisors, but I want two things to speed this up:

  • I want to skip the even numbers (so I must handle even numbers first)
  • I don't want to check beyond sqrt(n)

To find sqrt(n) I do a binary search, upperbound can be n, and lowerbound can be 0, and I'll have to square (upperbound+lowerbound)/2 to check if I've reached sqrt(n). However, I want to reduce the mult instructions, so I first find tighter bounds by determining the log of n.

# inputs:
# $2 = n
#
# outputs:
# $10 = is_prime(n)

# solve for n in {{1,3} U {2k: k in N0}}:

    # $4 = (n < 2)
    slti    $4,$2,2
    
    # $5 = (2 divides n)
    andi    $5,$2,1 # (n % 2) == 1
    slti    $5,$5,1 # (n % 2) == 0
    
    # $6 = (n < 4)
    slti    $6,$2,4
    
    # result = $10 = ((n == 2) || (n == 3))
    slt     $10,$4,$6 # ((n < 2) < (n < 4)) => ((n == 2) || (n == 3))
    
    # end if (n < 4) || (2 divides n)
    or      $7,$6,$5
    bne     $7,$0,end
    
    # (otherwise outside of range, so discard result)

# floor(log2(n)):
# result in $5

    lui     $3,0xffff
    ori     $3,$3,0xfff8 # mask to find msb
    
    # we know that (n > 4):
    ori     $4,$0,2 # min possible for floor(log2(n))
    
loop_log:
    and     $5,$3,$2
    
    beq     $5,$0,sqrt
    sll     $3,$3,1
    j       loop_log
    addu    $4,$4,1
    
sqrt:
    srl     $4,$4,1 # floor(log2(n))/2
    
    ori     $3,$0,1
    sllv    $3,$3,$4 # lowerbound: >= sqrt(n)
    sll     $4,$3,1 # upperbound: < sqrt(n)
    
    addu    $5,$4,$3
    
loop_sqrt:
    srl     $5,$5,1 # mid
    beq     $5,$3,is_prime # implies that upperbound = 1 + lowerbound
    
    multu   $5,$5
    mflo    $6 # mid^2
    
    slt     $6,$2,$6 # n < mid^2
    bne     $6,$0,new_upper
    
    # nop
    sll     $0,$0,0
    
# new_lower:
    or      $3,$0,$5
    j       loop_sqrt
    addu    $5,$4,$3
    
new_upper:
    or      $4,$0,$5
    j       loop_sqrt
    addu    $5,$4,$3

is_prime:
    # $1 = memory location
    # $2 = n
    # $5 = floor(sqrt(n))
    
    # we have already checked: 2 does not divide n
    # $3 = k (the divisor)
    ori     $3,$0,3
    
    divu    $2,$3
    
prime_loop:
    # for (k = 3; k <= sqrt(n); k += 2)
    #     if (n % k) continue;
    #     break;

    # $10 = maybe_prime
    mfhi    $10 # (n % k)
    slt     $10,$0,$10 # ((n % k) > 0)
    
    # k += 2
    addiu   $3,$3,2
    
    # $4 = certain_prime
    slt     $4,$5,$3 # (sqrt(n) < k)
    
    # continue if ((certain_prime == 0) && (maybe_prime == 1))
    # $6 = (certain_prime < maybe_prime)
    slt     $6,$4,$10
    
    bne     $6,$0,prime_loop
    divu    $2,$3
end:

For efficiency: The bottleneck is prime_loop. Currently the bne has two instructions to prepare for it, totalling 3 instructions. This is equivalent to checking (a == 0) && (b > 0), for a in {0,1}, b in {1, 2, ...}. I think there's some trick that I'm not realising to reduce an instruction for this.

\$\endgroup\$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.