Joseph Mullins

Programmer | Security | Automation

joseph@ropeney.com

# Project Euler 4

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
#
# 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"
```