# Summing all primes below 2,000,000 - Project Euler #10 in Assembly

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

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

inc rcx

; 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.

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


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


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!

• Thank you for your answer! Totally forgot that shifting means multiplication/division by 2. Your tips really helped! Commented Aug 21, 2017 at 19:33