Sunday 30 June 2013

Prime factors

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?


.syntax unified

@ 600851475143 is 8BE589EAC7 in hex

.equ numhi,139        @ 0x8b
.equ numlo,3851020999 @ 0xe589eac7

num_hi  .req r4
num_lo  .req r5
maxdiv  .req r6
n       .req r7

.section .rodata
 .align 2
resstring:
 .asciz "%d\n"
.text
 .align 2
 .global main
 .type main, %function
main:
 stmfd sp!, {r4-r7, lr}

 mov maxdiv, 0
 mov n, 1
 ldr num_lo, =numlo
 ldr num_hi, =numhi
loop:
 add n, n, 2           @ start at 3 and increment by 2
loop1:
 mov r0, num_lo
 mov r1, num_hi
 mov r2, n
 mov r3, 0
 bl  long_divide
 teq r2, 0
 bne loop
 teq r3, 0
 bne loop
 mov num_lo, r0         @ only get here when we have no remainder
 mov num_hi, r1         @ save the divisor as the new number
 mov r0, n
 bl isprime
 teq r0, 1
 bne loop               @ increment n if n is non-prime
 cmp maxdiv, n
 movlt maxdiv, n        @ save n as the largest divisor if it is larger
 teq num_lo, 1          @ we know it has prime factors
 beq printme
 b loop1
printme:
 mov r1, maxdiv
 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

The ARM is a RISC microprocessor and does not provide a divide command in the instruction set. We use a division routine from libgcc.

Using the -S option to gcc when a c file is compiled will generate an assembly language file which can be read for enlightenment.

isprime.s

.syntax unified # this subroutine returns 1 if the passed number is prime; 0 if not # inputs # r0 - integer to test # outputs # r0 - prime boolean number .req r4 divisor .req r5 tmp .req r6 .global isprime .type isprime, %function .text .align 2 isprime: stmfd sp!, {r4-r6, lr} mov number, r0 ands tmp, number, 1 bne odd mov r0, 0 cmp number, 2 @ 2 is the only prime even number bne last mov r0, 1 b last odd: mov divisor, 3 cmp number, 8 bgt big mov r0, 1 cmp number, 1 @ 1 is the only odd number < 8 not prime bne last mov r0, 0 b last big: mov r0, number mov r1, divisor bl divide teq r1, 0 beq factor add divisor, divisor, 2 mul tmp, divisor, divisor subs tmp, tmp, number ble big mov r0, 1 b last factor: mov r0, 0 last: ldmfd sp!, {r4-r6, pc}

The isprime function uses a naive, yet straightforward, algorithm to determine whether a given number is prime.

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}

Our divide and long_divide routines are wrappers around the libgcc functions to allow comments.

long_divide.s

.syntax unified # long_divide takes low numerator in r0, high numerator in r1, low denominator in r2 and high denominator in r3 # returns low quotient in r0, high quotient in r1, low remainder in r2 and high remainder in r3 .global long_divide .type long_divide, %function long_divide: stmfd sp!, {lr} # see https://codereview.chromium.org/5302007/diff/12001/arch/arm/lib/_uldivmod.S bl __aeabi_uldivmod ldmfd sp!, {pc}

No comments:

Post a Comment