Finding Greatest Common Divisor (GCD)

[unktehi]

For one of my assignments I'm supposed to take the following C++ code and write a small program in assembly language to accomplish the same thing.  From what I can gather we're suppoded to prompt the user for two integers and then plug those integers into the equation.  Unfortunately, I'm not that familiar with C++ code, so I'm not sure how we're expected to accomplish the assignment without an explanation of the code.

So first off, here is the C++ code that was given to us, with my comments of what I think it's doing:

int GCD(int x, int y)               
// there is an integer or function named GCD with the arguments of x and y

{
x = abs(x)
// Get absolute value of x and put it into x

y = abs(y)
// Get absolute value of y and put it into y

do {
int n = x % y;
// n is an integer and it equals the modulus of x divided by y
x = y;
// the value of y is given to x
y = n;
// the value of n is given to y

} while (y >0 )
//while y is greater than 0
return x;
//return the value of x
}


Now, assuming that I interpreted it correctly, I'm not very clear as to what the most efficient way is to write a program to do this. One thing that I have been able to do is to create a conditional statement and convert a negative number to a positive (for the absolute value).

This is what I'm doing:

MOV eax, someInputNumber
test eax, 10000000b           ; test to see if last bit is set   
JZ GiveMes
JMP EndMes

GiveMes PROC   
   mov  edx, OFFSET str1      ; "Number was positive"
   CALL Dumpregs
   call WriteString         ; displays string
   CALL Crlf
   ret
GiveMes ENDP   

EndMes PROC
   Neg eax
   mov  edx, OFFSET str2      ; "Number converted to positive"
   CALL Dumpregs
   call WriteString         ; displays string
   CALL Crlf
EndMes ENDP


So, in doing the rest of the assignment, I'm trying to determine if it would be best to prompt the user for integers and put them into an array, or stack, or separate variables - being there'd always only be two.

Any help would be appreciated...I feel totally lost on this one.

[BogdanOntanu]

you should not test for the last bit as if the number is always 8 bits. What it the imput number is bigger than 256?
Instead use the SIGN flag like this

Code Select Expand


mov eax,[my_input]
or eax,eax
js number_is_signed


; process unsigned number here
not_signed:


jmp_after

;process signed number here
number_is_signed:


; continue processing or other actions here
after:


Of course you could use an MASM HLL ".if .. ..else  .endif" construct if the teacher allows you to.

Then it is not a good idea to JUMP to a PROC. Usually a procedure is to be called and not to be jumped into.

As for the while loop you can do it like this:

Code Select Expand



do_again:
; process while body actions here

; check if y is zero
cmp [my_y],0
jnz do_again



Of course you will have to fill in the remaining "actions" and math operations if you want to solve the problem yourself.

[unktehi]

Thanks that helped a lot!! I was able to get that part of the program to work. Also, thank you for your advice on jumping to procedures.  I fixed that as well.

I just realized I think I interpreted x % y wrong from the given C++ code.  I interpreted it as the modulus of x and y. Do you know what that would mean?

[MichaelW]

Mod returns the remainder of a division. The DIV instruction performs a division, and for a 32-bit divisor it leaves the quotient in EAX and the remainder in EDX.

[unktehi]

Ok, so I think I'm starting to make sense of this all (even though I'm obviously struggling still).

So would it appear to you that the best way to capture the input integers is by storing them on the stack like so (this loops 2 times)?

.IF Sign?
      Neg eax
      mov  edx, OFFSET str2      ; "Number converted to positive"
      push eax
      CALL Dumpregs
      call WriteString         ; displays string
      CALL Crlf   
   .Else
      mov  edx, OFFSET str1      ; "Number was positive"
      push eax
      CALL Dumpregs
      Call WriteString         ; displays string
      CALL Crlf   
   .EndIf

Then, couldn't I just pull them from the stack later for the repeat/until loop?

Assuming that 'pushing' would work, here is what I've come up with so far to restore the values and accomplish the:

do {
int n = x % y;
x = y;
y = n;
}
while (y > 0);
return x;


   .Repeat
      POP eax               ; y being put into eax      
      POP ecx               ; x being put into ecx
      DIV ecx               ; finding x modulus y      
      MOV ebx, edx            ; x modulus y is put into ebx
      MOV ecx, eax                             ; setting x to y's value
      MOV eax, ebx                      ; setting y to modulus value
      CALL Dumpregs
   
   .Until (y < 0 )

[MichaelW]

I think if possible you should store everything in registers, and if there are not enough to do this, then you can reuse some by preserving their values on the stack temporarily. You can also augment the register set by using memory variables, but since most instructions do not allow more than one memory operand, you cannot use memory variables for everything. If the DumpRegs and WriteString in your code are from the Irvine32 library, then this will make it easier to keep everything in registers because these procedures preserve all registers.

And for the sort of thing you're coding you can also readily use ESI and EDI.

[unktehi]

Ok I'm still stuck.  I changed it so that the numbers are pushed into the stack and removed and placed into variables (I think).  Here is my code.  I'm not getting any errors in the build, and the .If/.Else loop works, but the .Repeat/.Until loop doesn't seem to do anything.  Am I totally on the wrong track here?

Here is my current code:

INCLUDE Irvine32.inc
INTEGER_COUNT = 2

.data
num1 DWORD -2
num2 DWORD 4
num3 DWORD 5
num4 DWORD -6
num5 DWORD 01010101b
someMod DWORD ?
varY DWORD ?
varX DWORD ?
str1 BYTE "Number was positive", 0
str2 BYTE "Number converted to positive", 0

mov ecx, INTEGER_COUNT
count DWORD ?
enterInt BYTE "Enter an integer: ", 0

.code
main PROC
   
   mov ecx, 2            ; Set overall loop number   

L1:      
   mov  edx, OFFSET enterInt   ; "Enter an integer:"
   call WriteString         ; displays string
   call ReadInt            ; read integer into EAX   
   ;MOV eax, num4            ; test conditional
   
   or eax,eax
   
   .IF Sign?
      Neg eax
      mov  edx, OFFSET str2      ; "Number converted to positive"
      push eax
      CALL Dumpregs
      call WriteString         ; displays string
      CALL Crlf   
   .Else
      mov  edx, OFFSET str1      ; "Number was positive"
      push eax
      CALL Dumpregs
      Call WriteString         ; displays string
      CALL Crlf   
   .EndIf
   
   Loop L1   
   
   .Repeat
      
      POP eax               ; y being put into eax
      mov varY, eax            ; put Y into varY      
      POP ecx               ; x being put into ecx
      mov varX, ecx            ; put X into varX      
      
      DIV ecx               ; finding x modulus y   
      ; edx is remainder
      mov varX, eax            ; mov y value into x var
      mov varY, edx            ; mov remainder into y var
         
   .Until (varY > 0)
   
   MOV eax, varX
   CALL WriteDec   
   
   
exit
main ENDP



END main

[BogdanOntanu]

Before using the stack you should first understand how it works. You are pushing the values twice in the input loop but in the while loop you will POP them an variable or unknown number of times and this will leave the stack non balanced and the values that you might POP will be "something else".

Normally you may not (or should not) POP more things than what you have pushed :D  Also keep in mind that the stack is also used by the PROC's for local labels / stack frames and return address and you must "walk" it carefully.

Hence I do I suggest that you use global variables for X and Y first and / or try to use the ESI/EDI registers as MichaelW so kindly suggested and later on you can also try to use the STACK.

Hint: Make a habit to do and try the most simple and most dummy solutions first and try the "more advanced" things at a later time. This will save you a lot of frustration in programming. The brain likes to have something working (candy first) and then keep on improving it in small incremental steeps.

No offense but I am often amazed on how beginners do insist on ignoring the advices they get and keep on going on the "wrong" path... Unless it is a request from you teacher I guess that there will be plenty of other chances to learn how to effectively use the stack.

[unktehi]

I understand that however, because the input from the user is gathered from a loop, how can I make the first value entered go into ESI and the second value entered go into EDI?

Would this work to do something like this?

.IF ecx == 2
MOV esi, eax
.ELSE
MOV edi, eax

And place that in between the

   .IF Sign?
      Neg eax
      mov  edx, OFFSET str2      ; "Number converted to positive"
      CALL Dumpregs
      call WriteString         ; displays string
      CALL Crlf   
   .Else
      mov  edx, OFFSET str1      ; "Number was positive"
      CALL Dumpregs
      Call WriteString         ; displays string
      CALL Crlf   
   .EndIf

and the  Loop L1 instruction?

[BogdanOntanu]

Yes something like that could also work...

Alternatively you could use EDI as a pointer to an "area" of input storage like this:

Code Select Expand


.data
my_input_01 dd 0
my_input_02 dd 0
...

.code
; init destination pointer
mov edi, offset my_input_01
...
; inside input loop
mov [edi],eax  ; store input number to current storage position
add edi,4 ; next storage position
...



This method would be easy to extend for a biger number of inputs.

BTW I am not found of the "LOOP" instruction  because it has a limited range for the back jump.
However this is not a problem for now.

[unktehi]

Ok, I FINALLY have it mostly working.  The only problem is now it's throwing a generic 'project.exe has a problem and needs to close.  We are sorry for the inconvenience.' error anytime I run it.  It doesn't seem to be going on to L3:

INCLUDE Irvine32.inc
INTEGER_COUNT = 2

.data
someMod DWORD ?
varY DWORD ?
varX DWORD ?
str1 BYTE "Number was positive", 0
str2 BYTE "Number converted to positive", 0
str3 BYTE "The GCD is: ", 0

mov ecx, INTEGER_COUNT
count DWORD ?
enterInt BYTE "Enter an integer: ", 0

.code
main PROC
   
   mov ecx, 2            ; Set overall loop number   

L1:      
   mov  edx, OFFSET enterInt   ; "Enter an integer:"
   call WriteString         ; displays string
   call ReadInt            ; read integer into EAX   
   
   or eax,eax
   
   .IF Sign?
      Neg eax
      mov  edx, OFFSET str2      ; "Number converted to positive"
      ;CALL Dumpregs
      ;CALL WriteString         ; displays string
      ;CALL Crlf   
   .Else
      mov  edx, OFFSET str1      ; "Number was positive"
      ;CALL Dumpregs
      ;CALL WriteString         ; displays string
      ;CALL Crlf   
   .EndIf
   
   .IF ecx == 2
   MOV esi, eax               ; Assigning X to esi
   .ELSE
   MOV edi, eax               ; Assigning Y to edi
   .ENDIF
   
   jmp L1   
   
   ;CALL Dumpregs
   
L2:   mov   eax, esi
   mov   ebx, edi
   div ebx                  ;EAX/EBX quotient is in eax, remainder in edx
   mov esi, edi
   mov edi, edx
   .if edi > 0
   jmp L2      
   .endif
   

L3:   ;CALL Dumpregs
   mov  edx, OFFSET str3         ; "The GCD is: "
   call WriteString            ; displays string
   MOV eax, esi               ; Return X
   CALL WriteInt               ;
   
   
exit
main ENDP

END main


Any ideas?

[sinsi]

Code Select Expand

    div ebx                  ;EAX/EBX quotient is in eax, remainder in edx
That instruction divides the 64-bit number in EDX:EAX by EBX, so always do a "sub edx,edx" if you are only dividing EAX.

[unktehi]

Ok, so it appears to me I don't understand how the DIV works.

I only have one example  to go off of and I'm honestly not sure what it's doing.

But from what I understood:

mov   eax, esi
; moving the value of esi into eax
mov   ebx, edi
; moving the value of edi into ebx
div ebx                 
; Shouldn't this divide eax by ebx? (eax/ebx)

If I'm only using eax and not edx, and need to use this: sub edx,edx - where would that go? after the div line?

[Mark Jones]

Hello unktehi, you have an explicit JMP back to L1 instead of the LOOP L1? If so, it will never get to L2. :wink

Personally, I'm with Bogdan about using LOOP... it might be clearer and easier just to do something like this:

Code Select Expand


L1:     
   mov edx, OFFSET enterInt   ; "Enter an integer:"
   call WriteString         ; displays string
   call ReadInt            ; read integer into EAX   
   
   or eax,eax
   .IF Sign?
      Neg eax
   .EndIf
   
   mov esi,eax               ; Assign X to esi

; repeat of the above but for edi
   mov edx, OFFSET enterInt   ; "Enter an integer:"
   call WriteString         ; displays string
   call ReadInt            ; read integer into EAX   
   
   or eax,eax
   .IF Sign?
      Neg eax
   .EndIf
   
   mov edi,eax               ; Assign Y to edi

L2:


Always try the simplest approach first. After the code is working, then it can be made more complex. Often, it is too difficult to start complex and try to "iron out all the bugs."

As for DIV, yes that's a tricky one. What Sinsi is saying, is that EDX must be zero before you do the DIV, because DIV treats EDX:EAX as a 64-bit number. "SUB edx,edx" will make EDX zero, as will "MOV edx,0" or "XOR edx,edx", etc.

You've almost got this one. :U

[sinsi]

div bl - divides the 16-bit number in AX by the 8-bit number in BL, AL=quotient, AH=remainder
div bx - divides the 32-bit number in DX:AX by the 16-bit number in BX, AX=quotient, DX=remainder
div ebx - divides the 64-bit number in EDX:EAX by the 32-bit number in EBX, EAX=quotient, EDX=remainder

So it doesn't matter that you are only using EAX - the processor will always use EDX:EAX

Code Select Expand


    sub edx,edx
    div ebx

This is for unsigned division, signed division uses "cdq" instead of "sub edx,edx" (I think, I never use signed numbers).