27 Mar, 2016 @ 03:11

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!

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 Left9009 / 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.

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.

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

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!

Please sign in to post comments…