Euclidean Algorithm

Here are three Matlab scripts for looking at the Euclidean algorithm:

• Euclid1.m expects to find two integers, a and b, and it returns the gcd(a,b) (now called "a", by the end of the algorithm) and "count", the number of steps needed to find it.
• Euclid2.m. This one generates M random pairs of integers (a,b) between 1 and N inclusive, and reports statistics on the distribution of gcd's and numbers of steps required.
• dio.m solves the linear Diophantine equation by using the Euclidean algorithm, representing a, b, and all subsequent remainders as "vectors," i.e., as linear combinations of a and b, x*a+y*b. That is, all quantities are represented in the form [x,y].

Euclid's version of the algorithm is in the first few propositions of Book VII of the Elements.