FASM assembly: Write a program which checks if a number is a prime number

Question

Coming from high-level languages like PHP and JavaScript, I'm doing an Assembly course on Udemy.

Yesterday I tried to implement the following task:

Write a program that takes a number m as input, and prints back 1 to the console if m is a prime number. Otherwise, it prints 0.

Original text can be found here (Exercise 3.0).

format PE console
entry start
include 'win32a.inc' 
; ===============================================
section '.text' code readable executable
start:
 call read_hex
 mov esi, eax ; Store the provided number in esi.
 mov edi, 1
 cmp eax, 2 
 je finish
 mov ebx, 2 ; ebx stores the divisor.
 mov edx, 0 ; Will contain the remainder. Therefore: Make sure it's empty.
go_forward: 
 ; Divisor has reached the size of the number and it was still 
 ; not possible to divide the number without a rest : Got a prim number.
 cmp ebx, esi 
 je finish ; Jump out of the loop.
 div ebx
 cmp edx, 0 
 je no_prim
 ; Preparations for the next iteration.
 inc ebx ; Increase the divisor. 
 mov edx, 0 
 mov eax, esi ; Restore the user entered value.
 jmp go_forward ; Restart the loop.
no_prim: 
 mov edi, 0 ; No prim : Then set the result to 0 !
finish:
 mov eax, edi
 call print_eax ; Provided by teacher: Print content eax to stdout.
 push 0
 call [ExitProcess]
include 'training.inc'

I have tried to comment a lot. I hope that makes my thoughts understandable. I'm still very much a beginner and the program could (without doubt) be improved.

Answer 1

For one thing, you don't need to check up to the value. The highest you need to go is sqrt(input) (link)

You could do some micro optimizations like xor edi,edi (shorter opcode) instead of mov edi,0 but I think the biggest gain would be to actually limit the loop.

Answer 2

Overall your code is very reasonable for somebody learning Assembly, I would say quite nice work.

I can produce something what will look more advanced (I hope), but it's more like tiny details improved here and there, and some of them for the price of worse readability of source.

I mean on the syntax and low level. On the algorithmic level your code can be improved considerably, as Paweł already answered, but he missed another opportunity to halve number of divisions.

My variant of code, showing:

1. how to use the result of DIV ebx (which has to be done anyway to test remainder) as approximation of suggested sqrt(input) test, for earlier exit.

2. xor reg,reg used to set zero into register (shorter opcode than mov reg,0 plus modern CPU recognizes it as idiom of "set to zero" and optimizes for it)

3. test edx,edx to check if remainder is zero (shorter opcode than cmp edx,0 plus modern CPU will recognize it as idiom of "test for zero value" and optimizes for it)

4. resolving even numbers at the beginning (even numbers have zero in least significant bit: isOdd(n) == (n&1). And the only even number being prime is 2, no need to test other even numbers by DIV.

5. but that means only odd divisors have to be tested in the loop, because (odd_input % even_divisor) != 0 for sure. So my loop is testing divisors 3, 5, 7, 9, 11, 13, 15, ...

6. some non-trivial usage of arithmetic instructions and flags to check for input values [0, 1, 2, 3] ahead of loop, as those would break the loop logic and produce invalid result. It may be nice exercise for you to "decipher" how it works.

7. you should try to keep things "together" (if possible). For example you set up edx:eax for DIV at the end of your loop code block, so it's A) not together with DIV, interleaved by JMP (hard to read for human, no problem for CPU) B) you have code duplicity (mov edx,0), because you have to init the register values ahead of very first DIV separately. => So I do initialize edx:eax right ahead of DIV, only single time in code, and it's easier to read IMO.

format PE console
entry start
include 'win32a.inc' 
; ===============================================
section '.text' code readable executable
start:
 call read_hex
 xor ecx, ecx ; return value = 0 (0 = not prime, 1 = prime)
 mov esi, eax ; copy provided number in esi
 shr eax, 1 ; eax = eax div 2, remainder into CF
 jz finish ; 0 and 1 are not primes
 adc ecx,ecx ; temporarily ecx=1/0 for odd/even input
 dec eax
 jz input_was_prime ; 2 and 3 are primes, special test needed
 ; because they would break loop logic
 jecxz finish ; other even numbers (but not 2) are *not* primes
 ; input number was odd and above 3, test odd divisors in generic loop
 mov ebx,ecx ; start with divisor 3 (ebx=1, loop will +2 first)
 dec ecx ; result = 0 (not prime)
test_divisors_loop:
 add ebx,2 ; next odd divisor to test
 mov eax,esi
 xor edx,edx ; edx:eax = input number (zero extended to 64b)
 div ebx ; eax = quotient, edx = remainder
 test edx,edx
 jz finish ; no prime, when remainder is zero
 cmp eax,ebx
 ja test_divisors_loop ; quotient > divisor -> try next
 ; when quotient <= divisor, it's safe to end loop, esi is prime number
 ; it's basically cheap "sqrt" end condition, reusing DIV result
input_was_prime:
 mov cl,1 ; result = 1 (is prime) (ecx was 0 or 1 before)
finish:
 mov eax, ecx ; result was in ecx, print it
 call print_eax
 push 0
 call [ExitProcess]
include 'training.inc'

(I did debug it in NASM, so if I'm unlucky, something may fail in FASM due to syntax, but it should be easy to fix. But it's highly unlikely, they should have identical syntax for instructions and I don't use any macros/etc)

• michael.zech: Thanks a bunch. :) I have learned a lot from your answer.