.text
.globl isPrime
.type isPrime,@function
isPrime:
pushq %rbx
pushq %r12
pushq %r13
pushq %r14
pushq %r15
movl %edi,%ebx # ebx = n
cmpl $2,%ebx # n < 2
jl finif # return 0
movl %ebx,%eax # temp = 2
andl $1,%eax # temp&= 1
cmpl $0,%eax # n % 2 == 0
je finic # return n == 2
movl $3,%r12d # i = 3
loop:
movq $0,%rdx # clear rdx for mul
movl %r12d,%eax # put i in eax for mul
imull %r12d # eax = i * i
cmpl %ebx,%eax # i * i <= n
jg overloop
movq $0,%rdx # clear rdx for div
movl %ebx,%eax # put n in eax for div
idivl %r12d # edx = n % i
cmpl $0,%edx # n % i == 0
je finif # return 0
addl $2,%r12d # i+=2
jmp loop
overloop:
movq $1,%rax # return 1
jmp fini
finif:
movq $0,%rax # return 0
jmp fini
finic:
cmpl $2,%ebx # n == 2
jne finif
movq $1,%rax # return 1
fini:
popq %r15
popq %r14
popq %r13
popq %r12
popq %rbx
ret
.size isPrime,.-isPrime
.text
.globl pfc
.type pfc,@function
pfc:
pushq %rbx
pushq %r12
pushq %r13
pushq %r14
pushq %r15
movl %edi,%ebx # ebx = n
movl $0,%r13d # fc = 0
movl $2,%r12d # i = 2
loop2:
movl %ebx,%edi # n is param 1
call isPrime # isPrime(n)
cmpl $1,%eax # if true
je finish
cmpl $3,%r13d # if fc is 3 and not prime, return false
je finishFalse
movq $0,%rdx # clear rdx for div
movl %ebx,%eax # put n in eax for div
idivl %r12d # eax: n%i, edx: n/i
cmpl $0,%edx # n%i == 0
jne overif
movl %eax,%ebx # n /= i
incl %r13d # fc++
divloop: # perform extra divisions of the factor
movq $0,%rdx # clear rdx for division
movl %ebx,%eax # put n in eax for div
idivl %r12d # compute division again
cmpl $0,%edx # n%i == 0
jne overdivloop
movl %eax,%ebx # n /= i
movl %ebx,%edi # n is param 1
call isPrime # we must recheck primality here
cmpl $1,%eax # if isPrime
je finish
cmpl $1,%ebx # if 1
je finish
jmp divloop
overdivloop:
overif:
incl %r12d # i++
jmp loop2
overloop2:
finish:
cmpl $3,%r13d # fc == 3
je finishTrue
finishFalse:
movq $0,%rax
jmp veryend
finishTrue:
movq $1,%rax
veryend:
popq %r15
popq %r14
popq %r13
popq %r12
popq %rbx
ret
.size pfc,.-pfc
.text
.globl e47
.type e47,@function
e47:
pushq %rbx
pushq %r12
pushq %r13
pushq %r14
pushq %r15
movl $210,%ebx # N = 210 (lowest possible num)
movl $0,%r12d # count = 0
loop3:
movl %ebx,%edi # N is param 1
call pfc
cmpl $1,%eax # pfc(N) == 1
jne elsepart
incl %r12d # count++
cmpl $1,%r12d # count == 1
jne overif2
movl %ebx,%r13d # r13d = first in seq
overif2:
cmpl $4,%r12d # count == 4
je thefinish # we are done
jmp overif3
elsepart:
movl $0,%r12d # clear the count
overif3:
incl %ebx
jmp loop3
thefinish:
movl %r13d,%eax
popq %r15
popq %r14
popq %r13
popq %r12
popq %rbx
ret
.size e47,.-e47
Wednesday, September 25, 2013
Problem 47 - x86 assembly
Yesterday I wrote my first x86 assembly code for one of my cs classes, and after finishing the assignment, rather than being exhausted from the effort or frustration or anything else, I had a feeling of satisfaction, having found working in assembly somewhat fun (at least at the relatively small scales I am still working at). So, as not to let that fun end, I decided to use x86 assembly on a Project Euler problem, and, as luck would have it, the problem I was up to, problem 47, was one that was not particular hard (for me, at least) to write in assembly - no need for copious variables, arrays, or any other sort of high-level language features that I would not be able to deal with. I am starting to think that all the drudgery with esoteric and otherwise dumb languages that I have had to put up with in the last month has made me immune to frustrations with programming languages or having too many difficulties switching between modes of computation - after learning how to write whitespace well, assembly is hardly a challenge, even if imul is implemented in a really stupid manner. Anyway, without further ado, here is my code, which runs in about .6s (to see the answer, I call e47 and use printf from a C program - the extra linking, etc that would be required to do this without touching C seemed unnecessary).
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment