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.

New contributor
Elliott is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$

Your Answer

Elliott is a new contributor. Be nice, and check out our Code of Conduct.

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.