help changing code from finding sum to finding factors

[dstudentx]

How could I modify this code to instead of finding a sum.  To taking a single input in and finding its factors

Code: [Select]

;
; 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


[Frank Kotler]

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...

Code: [Select]

test eax, 1
jz divisible_by_two

It may be worth "special casing" 2. Start dividing by 3? Okay...

Code: [Select]

    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"...

Code: [Select]

; 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