5
\$\begingroup\$

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.

\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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)

\$\endgroup\$
1
  • \$\begingroup\$ Thanks a bunch. :) I have learned a lot from your answer. \$\endgroup\$ Dec 26, 2016 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.