Speaking of which, here's the program:

.586

.model flat, c

.stack 100h

.data

; gcd(10, 4), gcd(28, 21), gcd(12, 8),

left dword 11, 28, 12

right dword 4, 21, 8

.code

doit proc

push eax

push ebx

push ecx

xor eax,eax

xor ecx,ecx

doagain:

sub esp,4

push left[ecx]

push right[ecx]

call gcd

pop ebx

add eax,ebx

add ecx,4

cmp ecx,12

jl doagain

pop ecx

pop ebx

pop eax

ret

doit endp

gcd proc

push eax

push ebx

push edx

mov eax,[esp + 20] ; eax is left

mov ebx,[esp + 16] ; ebx is right

cmp ebx, 0 ; We are done when right is zero

je weAreDone

xor edx,edx

div ebx

mov eax,ebx

mov ebx,edx

sub esp,4

push eax

push ebx

call gcd

pop eax

weAreDone:

; eax has the greatest common divisor

mov [esp + 24],eax

pop edx

pop ebx

pop eax

ret 8

gcd endp

end

We don't change anything in doit so let's just talk about gcd and what we change in there. Once we get to gcd our stack will look like this:

I'll explain the stack from top to bottom: At the bottom of the stack we have the return address that takes us back to main because that's the very first thing we do when we go into our program,next we have the 3 saved registers for our no trace coding,but just because I called them rand doesn't mean they're just a bunch of random numbers,they are those numbers for a reason,I just called them rand because they're always going to be a different number so I can't confirm them with a fixed value. Next we have our little slot for our return value,and our inputs left and right,and at the top we have the return address back from gcd to doit.

The first time through gcd we have our saves which still aren't a fixed value for our procedure,our return value slot,our inputs,and our return address:

The second time we have our saves which are procedure values this time around,our slot,inputs,and address:

The third time we have our saves,slot,inputs,and address:

The fourth time we only have our saves because we're at the base case which is when right is 0 and since we do the compare right after the saves we jump down to where we unwind the stack:

The first thing we change in gcd is we get rid of our jump address,because we don't need it anymore,and the next thing we change is before gcd calls itself we do the same thing that we do in doit just before we call gcd,we subtract 4 from the esp to make a slot for our return value,and push the inputs onto the stack so that we can access them through the esp. Another thing I'd like to point out is that since we call gcd from inside itself when we hit the return we return to the instruction right after the call so then we hit the return again and again,meanwhile we're popping a ton of values off the stack. You might be thinking: "Wait a minute,if we do that aren't we going to get a ton of random values?" well the answer is no because since we do the same thing that we do in doit before the call and since gcd calls itself and we go back to the beginning we do all those pushes,while doing these instructions we are doing something called unwinding the stack and eventually we get to the return that takes us back to doit and then we switch to the next set of numbers and call gcd. Well ya that's all cool,but the true beauty of recursion is that (especially with gcd) when you go back to the beginning if you've set up the code right the inputs are ready,the stack's ready,everything's ready to go around again,take the gcd of 11,and 4 for instance,which is the one I'm showing you in the pictures.

I'll explain the stack from top to bottom: At the bottom of the stack we have the return address that takes us back to main because that's the very first thing we do when we go into our program,next we have the 3 saved registers for our no trace coding,but just because I called them rand doesn't mean they're just a bunch of random numbers,they are those numbers for a reason,I just called them rand because they're always going to be a different number so I can't confirm them with a fixed value. Next we have our little slot for our return value,and our inputs left and right,and at the top we have the return address back from gcd to doit.

The first time through gcd we have our saves which still aren't a fixed value for our procedure,our return value slot,our inputs,and our return address:

The second time we have our saves which are procedure values this time around,our slot,inputs,and address:

The third time we have our saves,slot,inputs,and address:

The fourth time we only have our saves because we're at the base case which is when right is 0 and since we do the compare right after the saves we jump down to where we unwind the stack:

The first thing we change in gcd is we get rid of our jump address,because we don't need it anymore,and the next thing we change is before gcd calls itself we do the same thing that we do in doit just before we call gcd,we subtract 4 from the esp to make a slot for our return value,and push the inputs onto the stack so that we can access them through the esp. Another thing I'd like to point out is that since we call gcd from inside itself when we hit the return we return to the instruction right after the call so then we hit the return again and again,meanwhile we're popping a ton of values off the stack. You might be thinking: "Wait a minute,if we do that aren't we going to get a ton of random values?" well the answer is no because since we do the same thing that we do in doit before the call and since gcd calls itself and we go back to the beginning we do all those pushes,while doing these instructions we are doing something called unwinding the stack and eventually we get to the return that takes us back to doit and then we switch to the next set of numbers and call gcd. Well ya that's all cool,but the true beauty of recursion is that (especially with gcd) when you go back to the beginning if you've set up the code right the inputs are ready,the stack's ready,everything's ready to go around again,take the gcd of 11,and 4 for instance,which is the one I'm showing you in the pictures.

1st time gcd(11,4) = gcd(4,11 % 4) = gcd(4,3)

2nd time gcd(4,3) = gcd(3,4 % 3) = gcd(3,1)

3rd time gcd(3,1) = gcd(1,3 % 1) = gcd(1,0)

4th time gcd(1,0) = 1

The first time around 11,and 4 are on the stack,so we take them and mod them together which turns the 11 into a 3,then we push our numbers onto the stack again and go to the second time and keep changing the inputs on the stack etc.etc.etc.,and that's the beauty of it: we have our inputs,mod them together,switch them go again.

The first time around 11,and 4 are on the stack,so we take them and mod them together which turns the 11 into a 3,then we push our numbers onto the stack again and go to the second time and keep changing the inputs on the stack etc.etc.etc.,and that's the beauty of it: we have our inputs,mod them together,switch them go again.

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

## No comments:

## Post a Comment