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.

.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 buffer_address .req r7 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 ldr buffer_address, =buffer 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 ldr buffer_address, =buffer gd_loop: subs running, running, 1 bl divide_by_10_remainder strb r1, [buffer_address], #datum_size bgt gd_loop gd_last: ldmfd sp!, {r7-r8, pc}

ispalindromic.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}

divide_by_10.s

## No comments:

## Post a Comment