Euclidean Algorithm and Divide Overflow

[DViz]

Hey all, I've posted here before and had a lot of help from people, so I just wanted to say "thanks" to those involved.

I have an assignment where I am supposed to read in two decimal integers, and then figure out the greatest common divisor of the two, using the euclidean algorithm. I think what I have is supposed to work. In fact, it does, as long as the program only has to divide once... if the program has to divide more than once, I simply get a "Divide Overflow" error.

For example, if I input 10 and 5 as the integers, the program returns 5 as the gcd... which is correct.
If I input 15 and 10 as the integers, while the gcd is supposed to be 5, it would return "Divide Overflow."

I can't seem to find where exactly I messed up. All help greatly appreciated.

Code Select Expand


;Dan Visintainer - GCD
;Assembly - Project 2
INCLUDE Irvine16.inc
.data
prompt BYTE 'Please enter a number.',0dh,0ah, '$'
prompt1 BYTE 0ah, 0dh, 'Now, please enter another one.',0dh,0ah, '$'
prompt2 BYTE 0ah,0dh, 'The Greatest Common Divisor is: ','$'
prime1 BYTE 0ah,0dh, "Hey, this is a prime number!",0dh,0ah, '$'
error1 db 0ah, 0dh, "Letters? Ha. HA! Hexidecimals are SO last project. Try again.", "$"
error2 db 0ah, 0dh, "Uh-oh... Please use only decimal numbers here!", "$"
input byte 20 dup('$')
input2 byte 20 dup('$')
number1 dword 0
number2 dword 0
gcd word 0 dup('$')

.code

Isdigit PROC
cmp al,'0'
jb ID1
cmp al,'9'
ja ID1
test ax,0
ID1:ret
Isdigit ENDP

main PROC
mov eax,@data      ;begin input from keyboard.
mov ds,eax                      ;set DS to point to the data segment
xor edx,edx
xor esi,esi      ;initializing the index register here.

mov ah,9                       ;begins the DOS print string function.
mov edx,offset prompt      ;points to the input prompt...   
int 21h      ;prints the prompt.

;-----BEGIN INPUT OF FIRST NUMBER.

start:
   mov ah,1   
   xor ebx,ebx 
top: int 21h
   Mov input[ebx],al
   cmp al,0dh 
   Je alldone
   cmp al,0ah ; <<<<****I added these
   Je alldone ; <<<<****I added these (thanks dmh!)
   Inc ebx
   Jmp top
alldone:

redoloop: mov bl, input[esi];;;you need to use the ebx count value for input not his code
    mov al,bl
call Isdigit
inc esi  ;;;;you need to use the ebx count value for input not his code
    cmp bl,0dh  ;<<<<***won't be able to reuse this data space if you do it this way
    ;<<<<***because numbers could be different esizes and you need to input 2
    je loopfinished   
   
   
    sub bl, 48 ; <<==== Should this be ebx instead of BL? are the two linked?
    add number1, ebx ; <<<==== keep an eye on this... should this be "add" or "mov?"
    shl number1,4
    jmp redoloop
loopfinished:
;-----------PRIME NUMBER CHECK

xor ecx,ecx
xor eax,eax
xor edx,edx

mov ecx,number1
mov eax,number1
mov esi,number1
dec ecx
;primeloop:
; cdq
; div ecx
; cmp ecx,1
; je isprime
; cmp edx,0
; je isnotprime
; dec esi
; dec ecx
; jmp primeloop

;isprime:
; mov ah,9                       ;begins the DOS print string function.
; mov edx,offset prime1      ;points to the input prompt...   
; int 21h      ;prints the prompt.
;isnotprime:
; ------BEGIN INPUT OF SECOND NUMBER.
xor ah,ah
xor edx,edx

mov ah,9                       ;begins the DOS print string function.
mov edx,offset prompt1      ;points to the input prompt...   
int 21h     

xor ah,ah
xor esi,esi
xor edx,edx

start2:
   mov ah,1   
   xor ebx,ebx 
top2: int 21h
   Mov input2[ebx],al
   cmp al,0dh 
   Je alldone2
   cmp al,0ah ; <<<<****I added these
   Je alldone2 ; <<<<****I added these (thanks dmh!)
   Inc ebx
   Jmp top2
alldone2:

redoloop2: mov bl, input2[esi];;;you need to use the ebx count value for input not his code
    inc esi  ;;;;you need to use the ebx count value for input not his code
    cmp bl,0dh  ;<<<<***won't be able to reuse this data space if you do it this way
    ;<<<<***because numbers could be different esizes and you need to input 2
    je loopfinished2   
   
   
    sub bl, 48 ; <<==== Should this be ebx instead of BL? are the two linked?
    add number2, ebx ; <<<==== keep an eye on this... should this be "add" or "mov?"
    shl number2,4
    jmp redoloop2
loopfinished2:

;<<<<<<<<<<<<<<<<<<<<<<<<
; ------DONE WITH INPUTS!!!!!!!!!!!!!!!!!!!!!!!!!
;<<<<<<<<<<<<<<<<<<<<<<<<

mov ah,9                       ;begins the DOS print string function.
mov edx,offset prompt2      ;points to the input prompt...   
int 21h      ;prints the prompt.


xor esi,esi
xor eax,eax
xor bl,bl
xor edx,edx

mov eax,number1 ;<<<<------euclid algorithm starts here
mov ecx,number2
cdq

euclidloop:
cdq
div ecx
cmp edx,0
je eucliddone
mov eax,ecx
mov ecx,edx
cdq
jmp euclidloop

eucliddone:
;mov edx,ecx
;add edx,48
;mov ah,2
;int 21h

xor esi,esi

;mov ecx,edx
xor edx,edx
printloop:     
  inc esi
  mov edx, ecx
  shr edx, 12
  shl ecx, 4
  add edx, 48
 
  mov ah, 2
  int 21h
  cmp esi, 3
   jge nothingwentwrong
  jmp printloop

;xor ebx,ebx


;------------------THIS IS THE END OF THE MAIN PROGRAM. JUMP PROMPTS WILL GO HERE.-----------------
jmp nothingwentwrong
lettererror:
  mov ah,9                       ;begins the DOS print string function.
  mov edx,offset error1      ;points to the input prompt...   
  int 21h      ;prints the prompt.
  jmp nothingwentwrong
 
invaliderror:
  mov ah,9                       ;begins the DOS print string function.
  mov edx,offset error2      ;points to the input prompt...   
  int 21h      ;prints the prompt.
 
nothingwentwrong:
.EXIT
main ENDP
END main


[dedndave]

xor esi,esi
xor eax,eax       ;eax need not be 0'ed
xor bl,bl           ;smaller code to 0 the whole ebx register
xor edx,edx      ;put this one inside the loop

mov eax,number1 ;<<<<------euclid algorithm starts here
mov ecx,number2
cdq                          ;don't need this one

euclidloop:
xor edx,edx   ;use xor edx,edx instead of cdq - allows larger values
div ecx
cmp edx,0           ;or edx,edx
je eucliddone
mov eax,ecx
mov ecx,edx
cdq                    ;don't need this one, either
jmp euclidloop

lol - sure got that sucker cdq'ed, eh ? - you only need the one
cmp edx, 0 --> or edx,edx is faster and smaller

xor esi,esi
mov ebx,esi

mov eax,number1 ;<<<<------euclid algorithm starts here
mov ecx,number2

euclidloop:
xor edx,edx
div ecx
or edx,edx
jz eucliddone

xchg eax,edx      ;xchg eax,reg32 is a single byte
xchg eax,ecx
jmp euclidloop

eucliddone:

BUT !!!!!
that isn't the reason for overflow, in this case - lol
your routine to convert values into binary is messed up
get that working - print out number1 and number2 before trying the Euclid loop
i ran this code with 15 as number1 and 10 as number2 and it ran fine