# MIPS-32 assembly: Determine if n is prime

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.