# x64 Assembly - checking for largest prime factor

Using x64 assembly, I solved the Largest Prime Factor problem on Project Euler.

The problem is as follows:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

The answer is 6857.

I think I have a top notch algorithm to do the job (speed wise), which doesn't actually check if a number is prime. The algorithm just reduces the number they gave you instead.

p3 proc

mov rbx, 600851475143          ; The original number
mov rcx, 1                     ; The starting position of the counter
mov rdx, 0                     ; Just to clear garbage data

mainloop:

mov rax, rbx           ; rbx hold the number, and saves it, because the number in rax will change, and a backup needs to be stored

inc rcx                ; Increment counter
noinc:                 ; This is where the loop starts at each iteration that the previous division operation had no remainder
mov rbx, rax           ; At this instruction, we know that rax has been reduced, and save it into rbx

cmp rax, rcx           ; These two lines check if the counter rcx reached its maximum value, and if so, the program quits and returns the result in rax
je done
mov rdx, 0             ; makes sure there is no junk data in rdx

div rcx                ; Perform division to check for a remainder
cmp rdx, 0
jz noinc           ; If there is no remainder: Reduce the value and dont increment next iteration
jnz mainloop       ; If there is a remainder, jump back to the top of the loop, increment the value, and try the division again.

done:                      ; Exit
ret
p3 endp


I am a beginner in assembly, and this is one of my first x64 assembly programs. Are there any standard conventions that I am not following, or general things that could have been done better? Any advice? Is there a simpler way to do what I did?

Please be brutal and detailed in your response.

-
I would suggest you write your comments in pseudocode instead. As you describe WHAT the program does, do it in code instead of words. If you described WHY the program was written that way, words are fine. Also note that even if your assembly program is blazing fast, it will be beaten by slower programs using a sieve instead of checking all numbers. – Thorbjørn Ravn Andersen Jun 24 '14 at 7:56

## 2 Answers

One optimisation that would make your code run up to twice as fast, is to use the observation that a prime factor of n cannot be greater than n/2. So you can limit the number of times you iterate through your loop.

Additionally, you know that once you have tested for divisibility by 2, then subsequent trial divisions can skip all even numbers. If you continue down this road, you'll eventually implement a prime sieve using all the same tricks.

One thing I would suggest is to use jmp instead of jnz at the bottom of the loop. It might or might not make a performance difference, but you'll avoid the CPU (and your readers) from having to think about the condition.

It probably doesn't matter, but you could move the mov rdx, 0 up above the noinc label because whenever you jz noinc, you already know that rdx is zero. This sort of thing really needs to be clearly documented, of course.

-

# XOR versus MOV

A few times in your code you move the value 0 into a register.

A more efficient way to do this is to XOR the register with itself.

xor rdx, rdx

# Unnecessary CMP instruction

This MIGHT work; I didn't have the time to test it out

Instructions like JZ, JG, and JNZ don't have to be used after a CMP instruction; they can also be used after arithmetic is performed.

Instead of doing:

div rcx
cmp rdx, 0
jz noinc


You can just do:

div rcx
jz noinc


Which is more efficient.

# Labels

All the labels in your code are global labels, when most of them should be local labels.

Local labels are like sub routines for your sub routines.

The syntax of a local label is almost the same exact thing as a global label, only the first character must be a '.'

How your mainloop subroutine would look with local labels:

mainloop:

; code

.noinc:

; code

.done:

; code


Note: The indent before the local label is simply my preference; you might not like the indent. It doesn't matter

Be careful, now, when you are doing your jumps(JZ) to make sure to put the '.' before the label name.

-