# Calculating the LCM in ASSEMBLY



## xMikex (Nov 8, 2005)

Hey all I am having trouble understanding how to calculate the LCM using assembly language. Any examples or pseudocode you guys could share? Or even if someone could explain how to find the LCM in assembly would be great. THanks!

Michael


----------



## -Fabez- (Jul 28, 2008)

Have you tried using the Euclidean algorithm to find the LCM ?


----------



## xMikex (Nov 8, 2005)

Thats very helpful thanks!

Question though:


.WHILE y != 0
mov t, b
mov b, a mod b
mov a, t

How do I do modulus in assembly?


----------



## -Fabez- (Jul 28, 2008)

No problems, if you are using 8086 Assembly then the remainder will either be in AH or DX.


----------



## xMikex (Nov 8, 2005)

-Fabez- said:


> No problems, if you are using 8086 Assembly then the remainder will either be in AH or DX.


Here is the pseudocode:

function gcd(a, b)
while b ≠ 0
t := b
b := a mod b
a := t
return a

Would this be the correct conversion to assembly:

.WHILE y != 0
mov t, b
mov eax,x
div y
mov y, dx ; or edx?
mov a, t

Does this make sense?


----------



## xMikex (Nov 8, 2005)

Any ideas as to why I am getting a " The tool returned an error code while assembling"?
It wont tell me what the error was just that there is an error.


```
INCLUDE Irvine32.inc
.data
ProblemPrompt BYTE "There is a problem",0
Prompt BYTE "Enter the first number: ",0
Prompt2 BYTE "Enter the second number: ",0
Xprompt BYTE " X: ",0
Yprompt BYTE " Y: ",0
LCMPrompt BYTE " LCM is: ",0
x DWORD ?
y DWORD ?
t DWORD ?
lcm DWORD ?

.code
main PROC

call Clrscr

mov edx,OFFSET Prompt
call WriteString
call ReadInt
mov x, eax

mov edx,OFFSET Prompt2
call WriteString
call ReadInt
mov y, eax

mov edx,OFFSET Xprompt
call WriteString
mov eax,x
call WriteInt

mov edx,OFFSET Yprompt
call WriteString
mov eax,y
call WriteInt


.WHILE y != 0
	mov t, y
	mov eax,x
	div y
	mov y, dx ; or edx?
	mov x, t
.ENDW

mov lcm,x
mov edx,OFFSET LCMPrompt
call WriteString
mov eax,lcm
call WriteInt
	exit
main ENDP

END main
```
im guessing something is wrong with the while loop but im not sure.


----------



## xMikex (Nov 8, 2005)

ok so I got my algorithm to find the LCM of only 5 and 10. Which is really weird.

.WHILE y != 0
mov eax,y
mov t,eax
mov edx,x
mov ebx,y
div ebx
mov y,edx
mov eax, t
mov x, eax
.ENDW


For some reason it can find the LCM of those two numbers but I get a crash whenever I try either 3 and 2 or 4 and 6


Any thoughts? Ideas? Suggestions?


----------



## -Fabez- (Jul 28, 2008)

Does the crash give you any error messages ?


----------



## IMM (Feb 1, 2002)

Using jmps instead of your .WHILE macro (for the gcd thingy above)
it 'could' look like
(you need a new dword for gcd)

```
loopstrt:
    cmp  y, 0
    je   done
    mov  eax, y
    mov  t, eax
    mov  eax, x
    xor  edx, edx
    div  y
    mov  y, edx
    mov  eax, t
    mov  x, eax
    jmp  loopstrt
done:
    mov  gcd, eax
```
Intel says of the DIV instruction: 

```
Operand Size                  Dividend  Divisor  Quotient Remainder  Maximum Quotient
Word/byte                      AX        r/m8      AL      AH                       255
Doubleword/word                DX:AX     r/m16     AX      DX                   65,53532
Quadword/doubleword            EDX:EAX   r/m32     EAX     EDX                4294967295
Doublequadword/quadword        RDX:RAX   r/m64     RAX     RDX      18446744073709551615
```
Because our divisor  is m32 we need the third line in this list.
I've used _xor edx,edx_ to zero edx which is the 'upper' half of the Dividend because it's faster (and more common) but you could also use _mov edx,0_
There are lot's of ways to optimize the above
The temp (t) mem variable doesn't have to be memory - it would be faster if you used ecx instead
The jumps can be specified as short.

The following code would be quicker:

```
push esi
    mov ebx, y  ; temp y in ebx
    mov esi, x  ; temp x in esi
whil:
    cmp  ebx,0
    je   short done
    mov  ecx,ebx
    mov  eax,esi
    xor  edx,edx
    div  ebx
    mov  ebx,edx
    mov  eax, ecx
    mov  esi, eax
    jmp  short whil
done:
    pop esi
    mov gcd, eax
```
I don't know whether you need to preseve the value in esi - if you don't - you can remove the push and pop

To get lcm from it the bottom part of the one above could read as 

```
done:
    pop esi
    mov gcd, eax
    mov ebx, eax
    xor edx, edx
    div gcd
    xor edx, edx     ;  not necessary
    mul x
       ; at this point you should probably check to see that you haven't exceeded max dword
    mov lcm, eax
```


----------

