section .data ; put your data in this section using ; db , dw, dd directions num
ID: 3706848 • Letter: S
Question
section .data ; put your data in this section using ; db , dw, dd directions number db 5 answer db 1 ; 1 means number is prime, 0 means number is not prime section .bss ; put UNINITIALIZED data here using section .text global _start _start: mov esi, number ; get the offset of number into esi keith: mov eax, 0 ; clear the entire eax register mov al, [esi] ; get the number from memory into al mov dl, al ; put it inside dl as well mov bl, 2 ; bl holds each divisor starting from 2 loopy: div bl ; ax / bl with quot in al and rem in ah and ax, 1111111100000000b ; isolate the rem in ah with a AND mask ; to determine whether the remainder is 0 we need rewrite this part using Intel assembly language: (the purpose of this program to figure out if a number is positive or negative). In out case, we are trying it with 5.
prime = true ; divisor = 2 ; while ( divisor < number ) { if ( the remainder of number / divisor is 0 ) { prime = false ; // we found a divisor which evenly divides number } // so therefore number cannot be prime divisor = divisor + 1 ; // check the next divisor and keep looping }
Explanation / Answer
.... jz non_prime
.... inc bl
.... cmp bl, dl
.... jl loopy
[add code here to report a prime number]
non_prime:
[add code here to report a non-prime number]
Both the assembly code and the C pseudocode are pretty n00b-like.
1. There is no need to clear EAX if you are going to be doing all 8 and 16-bit arithmetic.
2. There's no point in AND AX, 0FF00h, when AND AH,AH does the same thing with a shorter instruction
3. There is no point in the pseudocode staying in the loop when a number is found to be non-prime. Assembly language is all goto-based, so you don't have to pretend that goto is evil and "avoid a break; statement".
4.One leading test for divisibility by 2 is the only even divisor you need to test. If a number isn't divisible by 2, it isn't going to have any other even divisors, either.
5. You can really take advantage of the fact that the DIV instruction gives you a quotient as well as a remainder. If the quotient is (strictly) less than the divisor, that means the divisor is greater than the square root of the original number. If you haven't seen a divisor yet, you aren't going to. You can stop after sqrt(n) tries and it doesn't cost a single machine cycle or a register to compare against.
Those last two This cuts the complexity for testing a prime number p down from p-2 divisions to approximately sqrt(p)/2 divisions. So, to find that 241 is prime will take 8 divisions instead of 239. I don't count division by 2 because that can be done simply by testing bit 0 of the number.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.