Author Topic: Find and display greatest common divisor from 2 input numbers  (Read 6105 times)

Offline jackstobbart

  • Jr. Member
  • *
  • Posts: 5
Find and display greatest common divisor from 2 input numbers
« on: September 22, 2014, 08:18:21 AM »
Good day,

I have been trying to write a program that does the following:

1. Accept two ASCII numbers from a user (I haven't bothered trying to check the values yet)
2. Convert those ASCII numbers to decimal values.
3. Find the greatest common divisor from those two numbers
4. Display the result

I feel as though I've successfully done steps 1-3, although I'm not entirely sure. Here is the code:

Code: [Select]
bits 16
org 0x100;
jmp main ;

number1_str: db 3,0,0,0,0,'$'
number2_str: db 3,0,0,0,0,'$'
num1_hex: dw 2
num2_hex: dw 2

prompt1: db 'Please enter first number (from 1 to 50): ','$'
prompt2: db 'Please enter second number (from 1 to 50): ','$'

cr_lf:
db 13,10,'$' ; carriage return and line feed

;
;Displays a string in dx
;
disp_str:
mov ah,09            ;
int 0x21            ;
ret            ;

;
; Converts an ASCII string of digits to a decimal number, and puts the result
; in ax, and passes the address to dx. If an error occurs, AL is set to 'E'.
;
str_to_num:
xor ax,ax            ; initial value of AX = 0
xor bh,bh            ;                  BH = 0
mov cx,10            ; To build integer in AX (multiply by 10)
mov si,dx            ; DX points to start of input buffer
call next_char         ; 
ret            ;
next_char:
mov bl,[si]            ; move contents of memory pointed to by SI to BL
cmp bl,0x0D    ; Is it a carriage return?
je finis            ; Yes, we are done
cmp bl,0x39            ; ASCII for the character '9' is 39h
jg  error            ; > '9', invalid character
sub bl,0x30            ; Convert to numeric value (ASCII '0' - 30h)
jl error            ; < 0, invalid character
imul cx    ; DX:AX = AX * 10 (32-bit result)
add ax,bx            ; add next digit
inc si            ; pointer to next char
jmp next_char    ; repeat for next character
ret            ;
error:
mov al,'E'            ; Flag an error
finis:
ret            ; return to calling program

;
;Calculates the greatest common divisor from the values in
;ax and bx. The GCD will be stored in ax.
;
GCD:
idiv bx     ; remainder (7) in DX, quotient (1) in ax
mov ax,bx             ; move bx into ax
mov bx,dx             ; move dx into bx
cmp bx, 0x0     ; Is y = 0?
jg yIsZero             ; Y is zero, return to call from main
call GCD             ; loop again if y isn't zero
;
; Displays result in ax and terminates program
;
yIsZero:
xor dx,dx            ; set dx to 0
add ax,0x30    ; convert remainder to ascii, store in ax
mov dx,ax            ;
int 0x21            ;
int 0x20            ; terminate program


main:
mov dx,prompt1    ; move prompt1 to dx
call disp_str            ; display prompt1

;get number1_str
xor dx,dx            ; set dx to 0
mov ah,0x0a    ; accept string from user
mov dx,number1_str; address for string
int 0x21            ;

call str_to_num    ;
mov [num1_hex],ax ; put value of ax into contents of memory address at
           ; num1_hex

mov ah,09            ; display string
mov dx,cr_lf    ; display carriage return and line feed
int 0x21            ;

mov dx,prompt2    ; move prompt2 to dx
call disp_str    ; display prompt2

;get number2
xor dx,dx            ; set dx to 0
mov ah,0x0a    ; accept string from user
mov dx,number2_str; address for string
int 0x21            ;

call str_to_num    ;
mov [num2_hex],ax ; put value of ax into contents of memory address at
           ; num2_hex

mov ah,09            ; display string
mov dx,cr_lf    ; display carriage return and line feed
int 0x21            ;

; Find the greatest common divisor
xor dx,dx            ; set dx to 0
mov ax,num1_hex   ; move value in num1_hex to ax
mov bx,num2_hex   ; move value in num2_hex to bx
call GCD            ; find greatest common divisor from values in ax and bx

I'm expecting y_is_zero to display a result, but all it does is wait for entry when I run the code above. If I press any key, the program just ends. I

Any help would be greatly appreciated.
- JS

Offline Frank Kotler

  • NASM Developer
  • Hero Member
  • *****
  • Posts: 2513
  • Country: us
Re: Find and display greatest common divisor from 2 input numbers
« Reply #1 on: September 22, 2014, 02:19:20 PM »
Looking just at the immediate problem:
Code: [Select]
;
; Displays result in ax and terminates program
;
yIsZero:
xor dx,dx            ; set dx to 0
add ax,0x30    ; convert remainder to ascii, store in ax
mov dx,ax            ;
int 0x21            ;
int 0x20            ; terminate program
int 0x21 performs various subfunctions depending on what's in ah. What's in ah here? Probably zero. This isn't going to display anything. (it's an obsolete way to terminate the program) You probably want subfunction 2 here - display the character in dl. So do "mov ah, 2" before the int 0x21. That will be limited to displaying one digit, which may not be enough, but it's a start.

Backing up a bit, how did we get here?
Code: [Select]
;
;Calculates the greatest common divisor from the values in
;ax and bx. The GCD will be stored in ax.
;
GCD:
idiv bx     ; remainder (7) in DX, quotient (1) in ax
mov ax,bx             ; move bx into ax
mov bx,dx             ; move dx into bx
cmp bx, 0x0     ; Is y = 0?
jg yIsZero             ; Y is zero, return to call from main
call GCD             ; loop again if y isn't zero

"jg" is going to jump if bx is "greater than" zero. This doesn't match the comment. You probably meant "je" or "jz" (they are the exact same opcode). This may still not do what you want - I'm going to have to refresh my memory about GCD.

Could bx be "less than" zero? Yes, it could if we use "jg". "jg" (and "jl") apply to signed values - negative if the high bit is set.  "ja" (and "jb") apply to unsigned values. You may not want to get into that quite yet, but you should be aware that there's a difference.

"call"ing GCD may not be the way you want to "loop" through the routine. Recursion is sometimes useful ("recursion error: see recursion error") but you've gotta "ret" sometime! I'll look more at this...

If this exits as soon as you enter anything, there's more wrong with it than I've spotted. I'll look more, but I wanted to mention the fundamental problem of why it doesn't display anything... More after more coffee...

Best,
Frank


Offline Frank Kotler

  • NASM Developer
  • Hero Member
  • *****
  • Posts: 2513
  • Country: us
Re: Find and display greatest common divisor from 2 input numbers
« Reply #2 on: September 22, 2014, 02:45:09 PM »
Ah! You call str_to_num with the address of your input buffer still in dx (which you move to si, as you need to). But the actual text - our number string - doesn't start until dx + 2, so str_to_num always ends with an error. You'll probably see this as soon as you get it to display something...

Best,
Frank


Offline Frank Kotler

  • NASM Developer
  • Hero Member
  • *****
  • Posts: 2513
  • Country: us
Re: Find and display greatest common divisor from 2 input numbers
« Reply #3 on: September 22, 2014, 03:19:03 PM »
Here's the GCD code I had in mind...

http://www.df.lth.se/~john_e/fr_gems.html

And while I'm thinking of it, here's an online version of Ralf Brown's Interrupt List...

http://www.ctyme.com/rbrown.htm

If you're going to mess with DOS interrupts, Ralf is your new best friend. It may be worth your while to download the whole thing. The search engines know what "RBIL" is. Besides interrup.lst, there's ports.lst and memory.lst and other goodies - some of which is useful even if you're not doing DOS.

Best,
Frank


Offline jackstobbart

  • Jr. Member
  • *
  • Posts: 5
Re: Find and display greatest common divisor from 2 input numbers
« Reply #4 on: September 22, 2014, 03:41:17 PM »
Looking just at the immediate problem:
Code: [Select]
;
; Displays result in ax and terminates program
;
yIsZero:
xor dx,dx            ; set dx to 0
add ax,0x30    ; convert remainder to ascii, store in ax
mov dx,ax            ;
int 0x21            ;
int 0x20            ; terminate program
int 0x21 performs various subfunctions depending on what's in ah. What's in ah here? Probably zero. This isn't going to display anything. (it's an obsolete way to terminate the program) You probably want subfunction 2 here - display the character in dl. So do "mov ah, 2" before the int 0x21. That will be limited to displaying one digit, which may not be enough, but it's a start.

Backing up a bit, how did we get here?
Code: [Select]
;
;Calculates the greatest common divisor from the values in
;ax and bx. The GCD will be stored in ax.
;
GCD:
idiv bx     ; remainder (7) in DX, quotient (1) in ax
mov ax,bx             ; move bx into ax
mov bx,dx             ; move dx into bx
cmp bx, 0x0     ; Is y = 0?
jg yIsZero             ; Y is zero, return to call from main
call GCD             ; loop again if y isn't zero

"jg" is going to jump if bx is "greater than" zero. This doesn't match the comment. You probably meant "je" or "jz" (they are the exact same opcode). This may still not do what you want - I'm going to have to refresh my memory about GCD.

Could bx be "less than" zero? Yes, it could if we use "jg". "jg" (and "jl") apply to signed values - negative if the high bit is set.  "ja" (and "jb") apply to unsigned values. You may not want to get into that quite yet, but you should be aware that there's a difference.

"call"ing GCD may not be the way you want to "loop" through the routine. Recursion is sometimes useful ("recursion error: see recursion error") but you've gotta "ret" sometime! I'll look more at this...

If this exits as soon as you enter anything, there's more wrong with it than I've spotted. I'll look more, but I wanted to mention the fundamental problem of why it doesn't display anything... More after more coffee...

Best,
Frank

Firstly, thanks for the reply.

Secondly, I changed a few things around:

Code: [Select]
;
;Calculates the greatest common divisor from the values in
;ax and bx. The GCD will be stored in ax.
;
GCD:
    ; idiv divides ax by dl, which resulted in a divide overflow with the old code as I was using bx.
    ; This happened after I changed jg to je below (which is noted).

    idiv dl ; remainder (7) in DX, quotient (1) in ax
    xor cx,cx ; set cx to 0 for temporary storage
    mov cl,al         ; put value of al into cl
    xor ax,ax ; set ax to 0
    mov al,dl ; put the value of dl into al
    mov dl,cl         ; put the value of cl into dl

    cmp dl, 0x0 ; Is dl = 0?
    je is_zero ; dl is zero, go to function is_zero, changed to je
    call GCD         ; loop again if dl isn't zero

is_zero:
xor dx,dx ; set dx to 0
add al,0x30 ; convert remainder to ascii, store in ax
mov dl,al ; move value of dl into al
        mov ah,02  ; adding this seems to display '?', which must be in al
                        ; if left out, there is not output at all and the program just ends
  int 0x21 ;


int 0x20 ; terminate program

In main:

Code: [Select]
        ; ...
        mov dx,number1_str; address for string
int 0x21 ;

mov dx,number1_str+2; added in the correct address for number 1
call str_to_num       ;
mov [num1_hex],ax    ; put value of ax into contents of memory address at
              ; num1_hex
        ; ...

        mov dx,number2_str    ; address for string
  int 0x21                ;

mov dx,number2_str+2; added in the correct address for number 2
call str_to_num       ;
mov [num2_hex],ax    ; put value of ax into contents of memory address at
              ; num2_hex

Now, with all these changes, I manage to get a response, which is '?'.

I'm going to end up checking the values when I get this code working to ensure that values are valid, larger than 0, and less than 50.

I tried that code for a GCD on the assembly gems page, and I get garbage results, with the first number I entered right at the end.

Code: [Select]
GCD:
neg ax ;
je l3 ;
l1: neg ax       ;
xchg ax,dx ;
l2: sub ax,dx ;
jg l2 ;
jne l1 ;
l3: add ax,dx ;
jne l4 ;
inc ax ;
l4:
        mov ah,09 ; forgot these two lines before edit, oops
int 0x21 ; forgot these two lines before edit, oops
        int 0x20 ;

The problem must be with how the numbers are stored, or do I have to compare the values before jne, jg, etc above? Hmm.
If I use 'mov ah,02' above instead of 'mov ah,09', I get a smiley face. I think the computer is laughing at my attempts, he he.
The interrupt lists from Ralf Brown is awesome. I'll be using it more in the future instead of the limited one I have at the moment.
« Last Edit: September 22, 2014, 03:46:08 PM by jackstobbart »

Offline avcaballero

  • Full Member
  • **
  • Posts: 132
  • Country: es
    • Abre los Ojos al Ensamblador
Re: Find and display greatest common divisor from 2 input numbers
« Reply #5 on: September 22, 2014, 03:42:44 PM »
I did something similar some years ago :). The objective was dealing with rational numbers in the quotient way. No english version available, though, sorry.

Regards.

Offline jackstobbart

  • Jr. Member
  • *
  • Posts: 5
Re: Find and display greatest common divisor from 2 input numbers
« Reply #6 on: September 22, 2014, 03:56:35 PM »
I did something similar some years ago :). The objective was dealing with rational numbers in the quotient way. No english version available, though, sorry.

Regards.

Hmmm. Thanks for the link. It seems that it will take me forever to understand that all, even if it had English comments.