GCD function in matlab

Question

hi, i am looking for a way to implement the "gcd" function used in matlab in another language but i really cant understand the way it functions.

it says in http://www.mathworks.com/access/helpdesk/help/techdoc/ref/gcd.html that:

"[G,C,D] = gcd(A,B) returns both the greatest common divisor array G, and the arrays C and D, which satisfy the equation: A(i).*C(i) + B(i).*D(i) = G(i)."

but it says nothing about how it calculates C and D.

i would be grateful if someone has a clearer idea about this subject! thanks:)

Answer 1

The Matlab documentation refers to

Knuth, Donald, The Art of Computer Programming, Vol. 2, Addison-Wesley: Reading MA, 1973. Section 4.5.2, Algorithm X.

I don't have the temerity to paraphrase that for you, but it is all there.

Answer 2

The extended Euclidean algorithm.

("Section 4.5.2 Algorithm X" being this can be shown in http://www.fitc.unc.edu.ar/javadev/math/previous/algorithms.html.)

Answer 3

Just have a look at the source by typing

edit gcd

which opens the function in the editor. Then you can look through the function line by line.

Together with the references in the other two posts, this should get you the answer.

Answer 4

It would use one of the basic schemes found in this link on The extended Euclidean algorithm.