Joseph Mullins

Programmer | Security | Automation

joseph@ropeney.com

Project Euler 4

Back

Its the super early hours of Easter, 4 day long weekend and nothing but free time to code to be had! I've put off this problem a few days, setting up my blog and working on a few side projects. I predicted this challenge would be a fun one, and it definitely proved me right.

In the interest of keeping this fun, I have implemented the solution to this problem using a mathematical approach. This was rather difficult, as first I had to make a algorithm that can read from left to right and right to left, comparing the numbers. This is a brute-force approach but I have dropped the interest in using only the 4 standard registers rax, rbx, rcx and rdx. So the way I solved this was on paper, drawing out an algorithm for proving if a number is a palindrome or not. Once I was confident in my method, I implemented just the checking of the palindrome. Testing a few cases with this, I moved to complete the solution. Exciting times!

The Mathematical Algorithm

Palindrome: 9009
We can look at this and tell it is a palindrome, but how can we do this mathematically.

We start with working out how we can get the numbers separately, right to left and left to right.

Right To Left
9009 / 10 == 900 R9 (Remainder 9)
900 / 10 == 90 R0
90 / 10 == 9 R0
9 / 10 == 0 R9

Each iteration, we have to check if the division results in 0. If it does, we stop.

So that was easy, but now to go left to right.

Left To Right
First, we must find the highest number the palindrome is divisible by, without resulting in 0.
9009 / 10 = 900 # Increase 10 x 10
9009 / 100 = 90 # increase 100 x 10
9009 / 1000 = 9 # increase 1000 x 10
9009 / 10000 = 0 # We have our number, 10,000

Now, we actually need to go back 1 step, dividing by 10 and getting a result of 1000. Because the first result needs to return the far left character. So now we continue.

9009 / 1000 = 9 # Stack 9
9009 - (9 * 1000) = 9 # now remove 9 * 100 from the total and reduce the power by 10 to 1000
9 / 100 = 0 # Stack 0
009 - (0 * 100) = 9
9 / 10 = 0 # Stack 0
9 - (0 * 10) = 9
9 / 1 = 9 # Stack 9

Each iteration, we have to check that the divider is not equal to 1 yet. So there we have it, a way to get each side. We simply traverse, pulling 1 off each and checking, failing as soon as 1 check is not the same.

Palindrome Check Code

This code checks with a number is a palindrome, 0 means no and 1 means yes.

# This is part of the way for project euler problem 4, and checks if a number is a palindrome
#
# 1 := Palindrome | 0 := Not Palindrome
#
# https://projecteuler.net/problem=4
# A palindromic number reads the same both ways. The largest palindrome made from the
# product of two 2-digit numbers is 9009 = 91 × 99.
# Find the largest palindrome made from the product of two 3-digit numbers.
#
# Solution by Joseph Mullins
#
# Compile with gcc check_palindrome.s

  .global main

  .text

main:
  mov $52311325, %r8        # Number to check if palindrome

  mov $1, %rcx            # %rcx will return with the highest devisor so start at 1

calculate_highest_division:  # Get the biggest power of 10 the number is divisible by
  mov %rcx, %rax
  mov $10, %rbx
  mul %rbx
  mov %rax, %rcx
  mov $0, %rdx
  mov %r8, %rax
  mov %rcx, %rbx
  div %rbx
  cmp $0, %rax
  jne calculate_highest_division  # If the divison wasn't 0, then we can go higher

  mov %rcx, %rax
  mov $10, %rbx
  mov $0, %rdx
  div %rbx
  mov %rax, %r9           # we actually want one less, so divide by 10 and use r9 to save it

  mov %r8, %rax
  mov $1, %r11

loop:
  mov $0, %rdx
  mov $10, %rbx
  div %rbx                # rax now holds the current value of the number % 10
  push %rax               # save rax
  push %rdx               # rdx will have the right most number, so save it

  mov %r8, %rax
  mov %r9, %rbx
  mov $0, %rdx
  div %rbx                # rax will now hold our the left most number

  pop %rdx
  cmp %rdx, %rax
  jne not_palindrome      # if rax and rdx aren't same, then not palindrome

  mov %r9, %rbx           # so far we on right track, so reduce the starting number by its left most number
  mul %rbx
  sub %rax, %r8

  mov %r9, %rax           # now we want to reduce r9 by 10, to get the next left most number
  mov $10, %rbx
  mov $0, %rdx
  div %rbx
  mov %rax, %r9           # save it for good record keeping

  pop %rax                # get back the value of rax from the start, the starting number / 10n
  cmp $1, %r9
  je is_palindrome
  jmp loop

not_palindrome:
  pop %rax
  mov $0, %rax
  jmp print

is_palindrome:
  mov $1, %rax
  jmp print

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

  call printf
  ret

format:
  .asciz "%200d\n"

As you can see, this is quite a substantial piece of coding implementing this algorithm, but was good fun. I'd like to point out how helpful comments are when writing ASM code, they really make it easier to debug and read through your logic. Since your logic is not abstracted, your comments can help you mind map it and make sure its correct; the more the better.

So after having the solution to check if a number is a palindrome, we next just need to modify it to check if a number is a palindrome and then see if we can find two 3 digits divisible for it. Starting from the highest, 999999, we start checking down.

Final Implementation

# https://projecteuler.net/problem=4
# A palindromic number reads the same both ways. The largest palindrome made from the
# product of two 2-digit numbers is 9009 = 91 × 99.
# Find the largest palindrome made from the product of two 3-digit numbers.
#
# I decided to tackle the checking of the palindrome in a pure mathematical way instead of
# turning to a string and checking
#
# Solution by Joseph Mullins
# Answer: 906609
#
# Compile with gcc euler_4.s

  .global main

  .text

main:
  mov $1000000, %r15        #  r15 will hold our counter

find_next_palindrome:
  dec %r15                  # count down, to find the highest palindrome
  mov %r15, %r8             # Check palindrome function uses r8 for checking
  jmp palindrome_check      # Initiate check if its palindrome

see_if_divisible:
  mov $1000, %rbx

count_down_rbx:
  dec %rbx
  cmp $99, %rbx
  je find_next_palindrome
  mov %r15, %rax
  mov $0, %rdx
  div %rbx
  cmp $0, %rdx
  jne count_down_rbx
  cmp $100, %rax
  jl find_next_palindrome
  cmp $999, %rax
  jg find_next_palindrome
  jmp print



palindrome_check:
  mov $1, %rcx            # %rcx will return with the highest devisor so start at 1

calculate_highest_division:  # Get the biggest power of 10 the number is divisible by
  mov %rcx, %rax
  mov $10, %rbx
  mul %rbx
  mov %rax, %rcx
  mov $0, %rdx
  mov %r8, %rax
  mov %rcx, %rbx
  div %rbx
  cmp $0, %rax
  jne calculate_highest_division  # If the divison wasn't 0, then we can go higher

  mov %rcx, %rax
  mov $10, %rbx
  mov $0, %rdx
  div %rbx
  mov %rax, %r9           # we actually want one less, so divide by 10 and use r9 to save it

  mov %r8, %rax
  mov $1, %r11

loop:
  mov $0, %rdx
  mov $10, %rbx
  div %rbx                # rax now holds the current value of the number % 10
  push %rax               # save rax
  push %rdx               # rdx will have the right most number, so save it

  mov %r8, %rax
  mov %r9, %rbx
  mov $0, %rdx
  div %rbx                # rax will now hold our the left most number

  pop %rdx
  cmp %rdx, %rax
  jne not_palindrome      # if rax and rdx aren't same, then not palindrome

  mov %r9, %rbx           # so far we on right track, so reduce the starting number by its left most number
  mul %rbx
  sub %rax, %r8

  mov %r9, %rax           # now we want to reduce r9 by 10, to get the next left most number
  mov $10, %rbx
  mov $0, %rdx
  div %rbx
  mov %rax, %r9           # save it for good record keeping

  pop %rax                # get back the value of rax from the start, the starting number / 10n
  cmp $1, %r9
  je is_palindrome
  jmp loop

not_palindrome:
  pop %rax
  jmp find_next_palindrome

is_palindrome:
  jmp see_if_divisible

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

  call printf
  ret

format:
  .asciz "%200d\n"

Answer

906609

Hopefully you've found use out of these, even though they are not the most elegent solutions they definitely show some Assembly principles and help me becoming a master in the language! Hopefully it does the same for you. Until next time, thank you!

Comments