The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Let us list the factors of the first seven triangle numbers:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?
.syntax unified .align 2 .section .rodata resstring: .asciz "%d\n" .equ last, 250 @ we count up to the square root - so half of the divisors will @ be necessarily less than the square root and half above. icount .req r4 @ it is possible to write FORTRAN in any language :-) jcount .req r5 tmp .req r6 num .req r7 .text .align 2 .global get_num_divisors .type get_num_divisors, %function @ we use jcount to hold current divisor and icount to hold the number of divisors seen @ num is passed as r0 and the number of divisors is returned. get_num_divisors: stmfd sp!, {r4-r7, lr} mov num, r0 mov icount, 0 mov jcount, 1 jstart: mov r0, num mov r1, jcount bl divide teq r1, 0 beq factor b nextj factor: add icount, icount, 1 nextj: add jcount, jcount, 1 mul tmp, jcount, jcount cmp num, tmp bgt jstart mov r0, icount ldmfd sp!, {r4-r7, pc} .align 2 .global main .type main, %function main: stmfd sp!, {r4-r7, lr} mov num, 0 mov icount, 0 mov jcount, 1 loop: cmp num, #last bge printme add icount, icount, jcount mov r0, icount bl get_num_divisors mov num, r0 add jcount, jcount, 1 b loop printme: mov r1, icount ldr r0, =resstring @ store address of start of string to r0 bl printf mov r0, 0 ldmfd sp!, {r4-r7, pc} mov r7, 1 @ set r7 to 1 - the syscall for exit swi 0 @ then invoke the syscall from linux
divide.s
.syntax unified # divide takes value in r0, divisor in r1 and returns dividend in r0 and modulus in r1 .global divide .type divide, %function divide: stmfd sp!, {lr} # see http://infocenter.arm.com/help/topic/com.arm.doc.ihi0043d/IHI0043D_rtabi.pdf bl __aeabi_uidivmod ldmfd sp!, {pc}
No comments:
Post a Comment