## Wednesday, November 19, 2014

### The GREAT,the common,and the divi/sor.......

On this post I'm going to talk about how to get the greatest common divisor between 2 numbers. The greatest common divisor is the largest number they can each be divided by,for example the greatest common divisor between 2,and 3 is 1 because the numbers aren't related,on the other hand the greatest common divisor between 2 and 4 is 2 because the numbers are both even and multiples of 2. I know you're probably thinking " this isn't going to be too hard but too bad for you the numbers we're using are 31415,and 14142,dun dun dun!!!! You might still be thinking that because one is odd and one is even,but what if I told you that you had to show me the step-by-step work to get the greatest common divisor of those 2 numbers? Well that's what we're going to do,but luckily there's a mathematical equation we can use. gcd(31415,14142) = gcd(14142,31415 mod 14142): gcd means "the greatest common divisor of" and mod means you divide 31415 by 14142 and then replace 31415 with the remainder of that division problem so the problem would become (14142,3131) = (3131,14142 mod 3131) and then you'd keep going etc.etc. until your problem would look something like this:

Luckily I have a program that can do this,and here it is:

.586
.model flat, c
.stack 100h
.data

left dword 31415
right dword 14142

.code

doit proc
xor ecx,ecx ; zero out ecx to count our loop
again:
mov eax,left    ; move the larger number of the first division problem into eax
mov edx,right   ; moving the larger number of the next division problem into a position where we can move it into left
mov left,edx    ; executing the previous comment
xor edx,edx     ; zeroing out edx to prevent Integer overflow
div right       ; performing the division problem
mov right,edx   ; preparing the numbers for the next time around
inc ecx         ; noting that we have gone around so we can add it to how many times we have already gone around
cmp ecx,10      ; comparing ecx to ten because we stop at 10
jne again       ; if ecx isn't ten we jump back to the beginning

ret

doit endp

end

As you can see I have the code commented and ready to go,so I'll explain how it works: So the first thing I did was grab two pieces of memory,I named one left,and the other right,and the reason I did that is because I needed two places to store the numbers that wouldn't get erased every frame. Then we xor ecx because we need it to be our counter because we need to go around 10 times. Then we move left into eax because eax represents the larger number of the division problem,and then we move right into edx because right contains the larger number of the next problem which needs to be placed in left and you can't move memory into memory,only memory into register or register into memory. Then we move edx into right,and after that we xor edx to prevent Integer overflow. And after that we do the division problem,take the remainder,and move it into right. Afterwards we inc ecx to keep track of how many times we have gone through the loop and eventually we stop at 10,and jne back to again.

Well there's an itty bitty problem with this,our chart is in decimal,but when we run the code the numbers are shown in hex,so it's pretty hard to keep track of where you're at in the program
or if the numbers are right,well I've got a solution:

I made you a hex chart,ta da! This chart will help you keep track of what line you're at and if you have the right numbers.

WELL TTFN,TA TA FOR NOW!!!!!!!!!!!!!!!!!!!!