Joseph Mullins

Programmer | Security | Automation

joseph@ropeney.com

Project Euler 3

Back

While still trying to keep using the standard 4 registers, rax, rbx, rcx, rdx this problem was fairly fun on the brute-force approach. Reducing the number to 29 made for easy debugging. Doing some research into finding prime numbers and seeing solutions people have done for this problem, I reverse engineered there solution and made it into Assembly.

The problem: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

Brute-force Approach

This approach is the first solution people do to most problems, work out how to get there with a smaller number, then repeat until you are there. Optimising first is the root of all evil, so we implement this solution then let the numbers get big and see if its still quick enough. This seems a bit counter productive in Assembly, as why would we write assembly if we weren't aiming for speed! (Yes I know specific control might be a thing too). Well, I didn't envision such a large number taking so long, 29 was almost instant!

The Code

# https://projecteuler.net/problem=3
# The prime factors of 13195 are 5, 7, 13 and 29.
# What is the largest prime factor of the number 600851475143 ?
#
# Solution by Joseph Mullins
#
# Compile with gcc euler_3.s

  .global main

  .text

main:
  mov $600851475143, %rcx         # The number
  mov $0, %rdx
  mov %rcx, %rax
  mov $2, %rbx
  div %rbx                        # Half is the max the prime factor can be
  cmp $0, %rdx                    # If it was divisible by 2 then we need to subtract 1
  jne setup
  dec %rax

setup:
  mov %rax, %rbx                  # rbx will hold our current count
  push %rcx

loop:
  pop %rcx
  sub $2, %rbx                       # Start the countdown to find highest factor
  mov %rcx, %rax                  # set up to see if starting number is divisible by rdx
  mov $0, %rdx
  div %rbx
  cmp $0, %rdx                    # Check if remainder is 0, if so then check if its a prime
  je check_if_prime
  push %rcx
  jmp loop

check_if_prime:
  push %rcx                       # Save our prime master number
  mov $2, %rcx                    # Start our checking if prime number at 2

prime_loop:
  cmp %rcx, %rbx                  # if rcx got high enough to only be divisible by itself, its prime
  je print
  mov %rbx, %rax                  # divide the current number, by 2..n
  mov $0, %rdx
  div %rcx
  cmp $0, %rdx                    # if remainder is 0, it was divisible by something other then itself
  je loop
  inc %rcx                        # increment and keep going
  jmp prime_loop

print:
  pop %rdx                        # So everythings off the stack
  mov $format, %rdi
  mov %rbx, %rsi
  xor %rax, %rax

  call printf
  ret

format:
  .asciz "%200d\n"

A Better Algorithm

Well trying to find the largest prime factor with this approach for 29 was quick! But finding it for 600851475143 was no small task. ./a.out 1086.47s user 0.03s system 99% cpu 18:06.58 (18 minutes) on my computer. So researching a better method was required. I looked at how other people were solving this problem in other languages and came across Jason B. Hill, in his solution at http://code.jasonbhill.com/c/project-euler-problem-3/, he implemented a smarter algorithm. A simple overview of the algorithm, is it works by dividing itself by a counter starting at 1. Once it finds a counter that is a prime, it divides itself by that prime. The result is then stored in a variable and the counter increases. The result is then divided by the next prime, repeating until the result / counter = 1. We then have our prime number.

The Better Algorithm

# https://projecteuler.net/problem=3
# The prime factors of 13195 are 5, 7, 13 and 29.
# What is the largest prime factor of the number 600851475143 ?
#
# Using algorithm taken from:
# http://code.jasonbhill.com/c/project-euler-problem-3/
# Works by dividing itself by a counter, untill it / counter can't be divided by anything
# other then 1 and itself
#
# Solution by Joseph Mullins
#
# Compile with gcc euler_3.s

  .global main

  .text

main:
  mov $600851475143, %rcx     # The number
  mov $1, %rbx                # rbx will hold our current count

loop:
  add $2, %rbx                # count in 2's as even numbers can't be a prime factorial
  mov %rcx, %rax              # setup for divison
  mov $0, %rdx
  div %rbx
  cmp $0, %rdx                # Check if remainder is 0, if so then set into rdx
  je  set_rcx
  cmp $1, %rax                # if the division was equal to one, we have our largest prime
  je print                    # so print it if that was the case
  jmp loop                    # repeat if it wasnt

set_rcx:
  mov %rax, %rcx              # store the result of the divison into rcx
  jmp loop

print:
  mov $format, %rdi
  mov %rcx, %rsi
  xor %rax, %rax

  call printf
  ret

format:
  .asciz "%200d\n"

Answer

Answer: 6857

Comments