## Monday, 1 July 2013

### Palindromic numbers

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.

```.syntax unified

.equ max3,999
.equ min3,100
.equ maxdigits,6

i       .req r4
j       .req r5
product .req r6
maxp    .req r7
mini    .req r8
minj    .req r9
maxj    .req r10

.section .rodata
.align 2
sumstring:
.asciz "%d\n"

.text
.align 2
.global main
.type main, %function
main:
stmfd sp!, {r4-r10, lr}
ldr i, =max3
ldr mini, =min3
ldr maxj, =max3
ldr minj, =min3
iloop:
mov j, maxj
jloop:
mul product, i, j

mov r0, product
bl is_palindromic
cmp r0, #1
bne next
cmp product, maxp
ble next
mov maxp, product
mov r0, product
bl divide_by_10         @ divides r0 by 10
bl divide_by_10         @ so 3 consecutive calls
bl divide_by_10         @ will divide by 1000
mov minj, r0
mov minj, r0

next:
subs j, j, 1
cmp j, minj
bgt jloop

subs i, i, 1
mov maxj, i
cmp i, mini
bgt iloop

last:
mov r1, maxp
ldr r0, =sumstring      @ store address of start of string to r0
bl printf

mov r0, 0
ldmfd sp!, {r4-r10, pc}
mov r7, 1               @ set r7 to 1 - the syscall for exit
swi 0                   @ then invoke the syscall from linux
```

A division of the found product by 1000 to reset the minima is an optimisation to speed termination.

We divide by 10 three times in succession - we could write a routine to divide by 1000, but one to divide by 10 is much more useful.

```ispalindromic.s
.syntax unified

.equ datum_size, 1
.equ digits, 6

# this subroutine returns 1 if the passed 6-digit number is palindromic; 0 if not
# the number is a product of 2 3-digit numbers so we assume the product has 6 digits
#
# inputs
#   r0 - integer to test
#
# outputs
#   r0 - palindromic boolean
#
# local
#
left           .req r4
right          .req r5
counter        .req r6
running        .req r8
tmp            .req r9
#
.section .bss
.lcomm buffer, 6                  @ use digits here?
#
.global is_palindromic
.type is_palindromic, %function
.global get_digits
.type get_digits, %function
.text
.align 2
#
is_palindromic:
stmfd sp!, {r4-r9, lr}
bl get_digits
mov counter, 3                      @ digits >> 1
ip_last:                             @ the next few lines are the nub of the problem
sub left, buffer_address, counter   @ on the first pass we compare x[0] and x[5]
ldrb tmp, [left, 3]                 @ if they are equal we compare x[1] and x[4]
add right, buffer_address, counter  @ if they are equal we compare x[2] and x[3]
ldrb running, [right, 2]
teq tmp, running
bne no                              @ mismatch between tested digits
subs counter, counter, 1
bgt ip_last                         @ test next pair for equality
mov r0, 1
b  last
no:
mov r0, 0
last:
ldmfd sp!, {r4-r9, pc}
#
get_digits:                             @ this routine writes a number into a string
stmfd sp!, {r7-r8, lr}
ldr running, =digits
gd_loop:
subs running, running, 1
bl divide_by_10_remainder
bgt gd_loop

gd_last:
ldmfd sp!, {r7-r8, pc}
```
```divide_by_10.s
.syntax unified

# this subroutine divides the passed number by 10 and
# returns the dividend and remainder
#
# The const -0x33333333 is 0xccccccd (2s complement)
# 0xcccccccc is 12/15th (0.8) of 0xffffffff and we use this as
# a multiplier, then shift right by 3 bits (divide by 8) to
# effect a multiplication by 0.1
#
# We multiply this number by 10 (multiply by 4, add 1 then multiply by 2)
# and subtract from the original number to give the remainder on division
# by 10.
#
# inputs
#   r0 - integer to divide
#
# outputs
#   r0 - the dividend
#   r1 - the remainder

.equ const,-0x33333333
#.equ const,0xcccccccd
.text
.align 2
.global divide_by_10_remainder
.type divide_by_10_remainder, %function
divide_by_10_remainder:
stmfd sp!, {lr}
cmp r0, 10
blt rsmall
ldr r1, =const
umull r2, r3, r1, r0
mov r2, r3, lsr #3              @ r2 = r3 / 8 == r0 / 10
mov r3, r2                      @ r3 = r2
mov r3, r3, asl #2              @ r3 = 4 * r3
add r3, r3, r2                  @ r3 = r3 + r2
mov r3, r3, asl #1              @ r3 = 2 * r3
rsb r3, r3, r0                  @ r3 = r0 - r3 = r0 - 10*int(r0/10)
mov r1, r3                      @ the remainder
mov r0, r2                      @ the dividend
b rlast
rsmall:
mov r1, r0
mov r0, 0
rlast:
ldmfd sp!, {pc}

# this subroutine divides the passed number by 10
# returns the dividend
#
# The const -0x33333333 is 0xccccccd (2s complement)
# 0xcccccccc is 12/15th (0.8) of 0xffffffff and we use this as
# a multiplier, then shift right by 3 bits (divide by 8) to
# effect a multiplication by 0.1
#
# We multiply this number by 10 (multiply by 4, add 1 then multiply by 2)
#
# inputs
#   r0 - integer to divide
#
# outputs
#   r0 - the dividend

.align 2
.global divide_by_10
.type divide_by_10, %function
divide_by_10:
stmfd sp!, {lr}
cmp r0, 10
blt small
ldr r1, =const
umull r2, r3, r1, r0
mov r2, r3, lsr #3              @ r2 = r3 / 8 == r0 / 10
mov r0, r2                      @ the dividend
b last
small:
mov r0, 0
last:
ldmfd sp!, {pc}
```