Joseph Mullins

Programmer | Security | Automation

joseph@ropeney.com

Project Euler 2

Back

After having so much fun with the last Euler Problem I have taken on the second one. I plan to do atleast 2 or 3 a week and try to get them submitted here for anyone to be able to see.

The Problem

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

 

This problem was good fun, but being new back at ASM it proved some fun challenges which got me using the DDD debugger frontend for GDB. Matching pop's with pushes turned out to be the problem and I focused alot on refactoring so not as many were required, with all the jmp you have to be very focused on the stack flow.

 

 

Me having fun debugging

DDD debugging my euler problem attempting to find the euler sums

 

 

And finally probably what everyone is waiting for, the code!

 

 

 

# https://projecteuler.net/problem=2
# Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1
# and 2, the first 10 terms will be:
#   1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
#
# By considering the terms in the Fibonacci sequence whose values do not exceed four million,
# find the sum of the even-valued terms.
#
# Solution by Joseph Mullins
# Answer: 4613732
#
# Compile with gcc euler_2.s

  .global main

  .text

main:
  mov $1, %rax        # The first number
  mov $1, %rbx        # The second number
  xor %rcx, %rcx      # The result
  xor %rdx, %rdx      # The total

loop:

  mov %rax, %rcx      # move first number into result
  add %rbx, %rcx      # add second number to the result

  push %rax           # Store everything
  push %rbx
  push %rdx

  mov $0, %rdx
  mov %rcx, %rax
  mov $2, %rbx        # set up to divide by 2 to see if even
  div %rbx

  cmp $0, %rdx        # if remainder is 0 then it was even so jump to add_to_total
  je add_to_total

  pop %rdx            # If wasnt even, repopulate the registers, remembering the ordering we stacked them
  pop %rbx
  pop %rax

  push %rcx           # we need rcx later to see if the term value is over 4,000,000
  mov %rbx, %rcx      # Store second number, add first number to it then put stored number into  first number
  add %rax, %rbx
  mov %rcx, %rax
  pop %rcx            # Retrieve rcx

  cmp $4000000, %rcx  # compare if terms are over 4,000,000, if so jmp to print or repeat
  jnb print
  jmp loop



add_to_total:
  pop %rdx            # restore total
  add %rcx, %rdx      # add to total

  pop %rbx            # restore old values
  pop %rax

  mov %rbx, %rcx      # Store second number, add first number to it then put into first number
  add %rax, %rbx
  mov %rcx, %rax

  jmp loop

print:
  mov $format, %rdi   # set first paramter of print f, formatting
  mov %rdx, %rsi      # set 2nd paramter (the result)
  xor %rax, %rax      # because printf is varargs

  call printf
  ret

format:
  .asciz "%200d\n"

 

Answer

Answer: 4613732

Comments