5
\$\begingroup\$

I am currently learning assembly for university, and I'd like to hear some feedback concerning what I've written. Currently I have implemented Problems 1, 2, 3 and 10 from ProjectEuler. The goal is to sum all primes ranging from 0 to 2,000,000.

For problem 10 I use the formula 6n +- 1 to check for primes. To actually check them, I test divisors 2, 3, 5, 7, ... I'm currently only using the general purpose registers of the x64 architecture.

Do you have any feedback concerning this code? Can I do something better? Optimize something?

I use NASM in x64 mode. This is my current implementation:

; CurrentPrime          Current prime to test
; Sum               Sum
; CurrentN              n of 6n +- 1
; PrimeMode             Wether we're doing + or - 1 (0 means -)
%define Sum r9
%define CurrentPrime r8
%define CurrentN r10
%define PrimeMode r12

section .text
global main
main:
    mov Sum, 5 ; 2+3 not included in 6n +- 1
    mov CurrentN, 0 ; This gets inc'ed below

loop:

    ; Increase n
    inc CurrentN

    ; Break every 10000 Ns for debugging reasons
    mov rax, CurrentN
    mov rbx, 10000
    mov rdx, 0
    div rbx
    cmp rdx, 0
    jne _debug_next
    nop ; Break here
_debug_next:

    ; multiply it by 6 and save it to CurrentPrime
    mov rax, CurrentN
    mov rbx, 6
    mul rbx
    mov CurrentPrime, rax

    ; Start with 6n-1
    dec CurrentPrime

    ; Reset registers for testing
    mov PrimeMode, 0
    ; This is our divisor
    mov rcx, 2

next_prime_test:

    ; When the number to test is >= 2000000, then exit
    cmp CurrentPrime, 2000000
    jge finish

    ; When divisor_to_test > (number_to_test/2), then this is prime
    mov rax, CurrentPrime
    mov rbx, 2
    mov rdx, 0
    div rbx
    cmp rax, rcx
    jl is_prime

    ; Test divisor for divisor
    mov rax, CurrentPrime
    mov rbx, rcx
    mov rdx, 0
    div rbx
    cmp rdx, 0
    je check_next_prime

    ; We only check odd numbers. 
    ; But to get from 2 to 3, we may not inc when we're at 2.
    cmp rcx, 2
    je skip_add

    inc rcx

skip_add:

    ; This divisor isn't a divisor of our number. Let's try with the next divisor.
    inc rcx
    jmp next_prime_test

is_prime:
    ; This number is prime, add it to our result.
    add Sum, CurrentPrime

check_next_prime:

    ; If we're doing 6n-1, increase by 2 to get 6n+1, then check again
    cmp PrimeMode, 0
    ; If we've done 6n+1, then go for the next n
    jne loop

    mov PrimeMode, 1 ; Set plus
    mov rcx, 2 ; Reset rcx to start over with a new prime
    add CurrentPrime, 2 ; 6n-1 +2 = 6n+1

    ; Check 6n+1
    jmp next_prime_test

finish:
    ; Result is in rax
    mov rax, Sum

    ret
\$\endgroup\$
2
\$\begingroup\$

Because all of your variables Sum, CurrentPrime, CurrentN, and PrimeMode reside in registers your code could/should benefit from this fact.

You've calculated CurrentPrime = CurrentN * 6 - 1 using:

mov rax, CurrentN     ; multiply it by 6 and save it to CurrentPrime
mov rbx, 6
mul rbx
mov CurrentPrime, rax
dec CurrentPrime    ; Start with 6n-1

Not only does this clobber the registers rax, rbx, and rdx, it also uses the mul instruction variant that produces an 128-bit result. Intel advices against this form when the upper 64-bits of the result are not needed which is the case in your program. A better multiplication then comes from using the 2 operand form of imul.

mov  CurrentPrime, CurrentN
imul CurrentPrime, 6
dec  CurrentPrime

This shorter and faster solution also doesn't use any additional registers!


When you reset your variables and registers you consistently use the mov instruction.

mov CurrentN, 0 ; This gets inc'ed below
mov PrimeMode, 0
mov rdx, 0

Because these variables really are registers too, and because the preferred way to zero a register is to xor it with itself, you should write instead:

xor  CurrentN, CurrentN
xor  PrimeMode, PrimeMode
xor  rdx, rdx

This produces much shorter code.


This is how you check if PrimeMode is zero.

cmp PrimeMode, 0
jne loop

Because this variable really is a register, and because the preferred way to find out if a register is zero is to test it with itself, you should write instead:

test PrimeMode, PrimeMode
jnz  loop

In next snippet you want to toggle PrimeMode when the prime at 6n-1 was found.

cmp PrimeMode, 0    ; If we've done 6n+1, then go for the next n
jne loop
mov PrimeMode, 1 ; Set plus

That's fine but you could use the fact that PrimeMode is equal to zero here and just have it incremented instead of using the space consuming immediate value:

test PrimeMode, PrimeMode
jnz  loop
inc  PrimeMode             ;Set plus

Divisions are costly.

In order to conclude that the current number is prime, you perform a division by 2.

; When divisor_to_test > (number_to_test/2), then this is prime
mov rax, CurrentPrime
mov rbx, 2
mov rdx, 0
div rbx
cmp rax, rcx
jl is_prime

You should replace this wasteful div by a simple shift to the right:

mov  rax, CurrentPrime
shr  rax, 1
cmp  rax, rcx
jl   is_prime

Why in next part of the code doesn't your division use the rcx register straight away? Why do you first move the divisor in rcx to rbx? That's just a superfluous instruction!

; Test divisor for divisor
mov rax, CurrentPrime
mov rbx, rcx
mov rdx, 0
div rbx
cmp rdx, 0
je check_next_prime

No longer clobbering the rbx register and applying many of the above tips gives:

mov  rax, CurrentPrime
xor  rdx, rdx
div  rcx
test rdx, rdx
jz   check_next_prime

Avoid redundant operations.

In your most inner loop you keep checking if CurrentPrime exceeds 2000000, but you forget that the value of CurrentPrime does not change within this inner loop. Best move the test above the next_prime_test label introducing an additional label MAYBE_next_prime_test.

    mov  PrimeMode, 0             ; Reset registers for testing
    ;;;mov  rcx, 2     <----- Remove this line
MAYBE_next_prime_test:
    cmp  CurrentPrime, 2000000    ; When the number to test is >= 2000000, then exit
    jge  finish
    mov  rcx, 2     <----- This line replaces both others
next_prime_test:

    ...

    inc rcx
    jmp next_prime_test

    ...

    ;;;mov  rcx, 2     <----- Remove this line 
    add  CurrentPrime, 2          ; 6n-1 +2 = 6n+1
    jmp  MAYBE_next_prime_test    ; Check 6n+1
finish:
    mov  rax, Sum                 ; Result is in rax

I've also avoided the duplication of the mov rcx, 2 instruction that you already had in the top part of the program. Shaves off some bytes!

\$\endgroup\$
1
  • \$\begingroup\$ Thank you for your answer! Totally forgot that shifting means multiplication/division by 2. Your tips really helped! \$\endgroup\$ – Stephan Aug 21 '17 at 19:33

Your Answer

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

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