NASM - The Netwide Assembler
NASM Forum => Using NASM => Topic started by: dstudentx on March 05, 2010, 10:34:30 PM
-
How could I modify this code to instead of finding a sum. To taking a single input in and finding its factors
;
; file: sub3.asm
; Subprogram example program
;
; To create executable:
; Using djgpp:
; nasm -f coff sub3.asm
; gcc -o sub1 sub3.o driver.c asm_io.o
;
; Using Borland C/C++
; nasm -f obj sub3.asm
; bcc32 sub3.obj driver.c asm_io.obj
%include "asm_io.inc"
segment .data
sum dd 0
segment .bss
input resd 1
;
; psuedo-code algorithm
; i = 1;
; sum = 0;
; while( get_int(i, &input), input != 0 ) {
; sum += input;
; i++;
; }
; print_sum(num);
segment .text
global asm_main
asm_main:
enter 0,0 ; setup routine
pusha
mov edx, 1 ; edx is 'i' in pseudo-code
while_loop:
push edx ; save i on stack
push dword input ; push address on input on stack
call get_int
add esp, 8 ; remove i and &input from stack
mov eax, [input]
cmp eax, 0
je end_while
add [sum], eax ; sum += input
inc edx
jmp short while_loop
end_while:
push dword [sum] ; push value of sum onto stack
call print_sum
pop ecx ; remove [sum] from stack
popa
leave
ret
;
; subprogram get_int
; Parameters (in order pushed on stack)
; number of input (at [ebp + 12])
; address of word to store input into (at [ebp + 8])
; Notes:
; values of eax and ebx are destroyed
segment .data
prompt db ") Enter an integer number (0 to quit): ", 0
segment .text
get_int:
push ebp
mov ebp, esp
mov eax, [ebp + 12]
call print_int
mov eax, prompt
call print_string
call read_int
mov ebx, [ebp + 8]
mov [ebx], eax ; store input into memory
pop ebp
ret ; jump back to caller
; subprogram print_sum
; prints out the sum
; Parameter:
; sum to print out (at [ebp+8])
; Note: destroys value of eax
;
segment .data
result db "The sum is ", 0
segment .text
print_sum:
push ebp
mov ebp, esp
mov eax, result
call print_string
mov eax, [ebp+8]
call print_int
call print_nl
pop ebp
ret
-
Throw it out and start over. Not that there's anything wrong with your "sum" program, but you'll be doing something almost completely different. You'll still be using "read_int" (yuck!!!) and "print_int"... probably a variable to hold a result, but that's about all they have in common.
One thing you should "keep" is the commented section that describes the general algorithm. Different algorithm, but the idea is good - probably even more important for this one! Do you have an algorithm for finding factors in mind? Or are you going to have to figure that out?
The naive approach is "divide by everything in sight". The "div" instruction divides edx:eax by... a register or memory... leaving the quotient in eax, and the remainder in edx. You might want to read what I had to say the other day in the "get two numbers from the keyboard" thread about "div" and its "gotcha". In that case, we were interested in the remainder in edx. In this case, we only care if there is one. If edx is zero, we've found a factor. Print it, I suppose. Or save it for later? And continue trying to find factors of the quotient (in eax still?), I guess. If there's a remainder, try dividing by the "next number". (in this case, we'll need to reload eax!)
Start dividing by 1? No, anything's evenly divisible by 1, and it isn't considered a "factor" usually. Start dividing by 2? Well, yeah, but we can determine divisibility by 2 by just checking the first (zeroth) bit...
test eax, 1
jz divisible_by_two
It may be worth "special casing" 2. Start dividing by 3? Okay...
mov ebx, 3
top:
mov eax, [input_number]
xor edx, edx
div ebx
test edx, edx ; or "cmp edx, 0"
jz found_factor
inc ebx
jmp top:
Wait a minute! No point in trying to divide by 4... or any even number. Make that "add ebx, 2". Now we'll divide by 3, 5, 7, 9... wait a minute, no point in dividing by 9 - we only want primes, really. Maybe, in the interest of getting it done this century, we better live with that inefficiency and just divide by odd numbers.
Okay, when do we end, and decide there aren't any factors? No point in trying anything bigger than the square root of N. It is fairly easy to calculate the square root, using the FPU, but I doubt if you're "expected to know" that, at this point. Stopping at N/2 would be better than running all the way up to N, I suppose. Obviously, you want to stop someplace!
As you probably know, factoring of very large numbers - hundreds of digits - is of interest to the crypto community. A lot of work has been done on designing efficient algorithms. I don't imagine you're expected to turn one in as homework. I think you're going to have to treat this as a "time management" problem. How much time can you afford to spend makin' it go faster, before the due date? Much as I hate to say it, a slow but simple algorithm may be your best bet!
I say "throw out" your "sum" program. There isn't much of it you'll be using. Start with a "skeleton"...
; whatever "header" your instructor likes
; purpose of program
; build instructions?
; includes, etc.
;
; print a prompt of some kind
; get a number with read_int
; find factors
;
;
; (this space intentionally left blank)
;
;
; print factors using print_int
; query "do another?" ?
; exit cleanly
I suppose "find_factors" will be a subroutine, since you know how to do 'em. To begin with, just "print_int" what you got, to make sure everything is "as expected" so far. Then start dividin'. Probably using print_int temporarily to "see how you're doing" will be helpful. (maybe "dump_regs" would be better?)
If, while you're thinking about it, you come up with a really fast way to factor really big numbers... "keep it to yourself" might be your best bet. :)
Best,
Frank