GCD help

[roki]

Hi!
I need to write program which contain main code and procedure GCD. The task is to compute a great common divider of four 16-bit unsigned numbers.
Which algorithm could I use there? I know for evaluating GCD of two numbers by Euclids algoritm but dont know how to put  it in solution of my problem? And what kind of procedure do I need, FAR or NEAR?
Can someone help me? 

[Evenbit]

Can't remember what site I ran into this, but it is from the "asm gem" package:

Code Select Expand


John Kirwan was asking for the smallest implementation of the "gcd" (greatest
common divisor of two numbers such gcd(0,0)==1 and gcd(x,0)==gcd(0,x)==x)
function by a C compiler.  There were a couple embarassing (for the C
compilers) responses.  For fun, I submitted the following hand optimized
solution:

neg eax
jz l3
l4:
neg eax
xchg edx,eax
l1:
sub eax,edx
jg l1
jnz l4
l3:
add eax,edx
jnz l2
inc eax
l2:

I suspect you could achieve a similarly small piece of code using div.

Nathan.

[roki]

Thanks Evenbit.
I understanded the code, I also noticed some good examples on net, but my problem still exist. I dont know how to do it with 4 numbers, how can I passed the right values in procedure and how procedure named GCD can pass a GCD value back. I dont know will I use Euclids algorithm or something else.
Maybe I should put it those 4 numbers in array, find a smallest number, which is a first candidate for GCD. Then I should  use DIV to see if other 3 nubers are dividable without rest with smallest one. If it is so, than the smallest is a GCD, if not than I should decrement a smallest, so SMALLEST=SMALLEST -1, and than do it all again. It will be then propably a recursive procedure. But still I dont know how to do it.
Thanks anyway.

[MichaelW]

The GCD is associative. You should be able to use this to implement a method of calculating the GCD of more than two numbers.

http://en.wikipedia.org/wiki/Greatest_common_divisor

[roki]

Thanks Michael,
so I am little bit closer to solution, I need to use recursive procedure.
gcd(a,b,c,d)=gcd[gcd(a,b,c),d]=gcd{[gcd(a,b),c],d}
Ok, so my problem now is how to do it with FAR procedure GCD. Procedure will give me a GCD of 2 numbers, which I have to back again into procedure and so on.

[MichaelW]

In a high-level language, if you had a gcd function that took two arguments, the call might look something like this:

Code Select Expand


gcd(gcd(gcd(a,b),c),d)

And you could use a similar syntax with MASM if you embedded the procedure call in a macro function.

A FAR procedure? If you are using a medium or large model then the distance attribute for the PROC directive, the distance attribute for the prototype, and the CALL and RET instructions will all default to FAR, so you should not have to use the FAR keyword anywhere. If you are using a small model then you will need to specify FAR for the distance attribute for the PROC directive and the distance attribute for the prototype, and MASM will correctly encode everything else.

On the page that I linked there is an Euclidean algorithm link. On that page there is a simple, short pseudo-code implementation of the algorithm (that will not correctly handle arguments with a value of zero).

[roki]

My basic problem is that I am not especially familiar with procedures in assembler. I found some good codes in Pascal but I cant convert it into assembly procedures because dont know how to deal with procedure parameters and stack.
So I need to study in some other problems which I have here and than will try to solve this problem.
If anyone could put some symilar codes here, I would be happy.
Thanks, anyway.