Euclid-Wallis Algorithm
-----------------------

This algorithm computes gcd(m,n), solves the Diophantine equation
mx + ny = gcd(m,n), and yields the continued fraction for m/n.

Start with the two columns

    1   0
    0   1
    m   n

Above each successive column write down the floor of the quotient of the
base of the previous column divided into the base of the column before
that, then compute the new column by subtracting that number times the
previous column from the column before that.

The column preceding that with 0 at its base has gcd(m,n) at its base.
Also, m times the top row plus n times the middle row equals the bottom
row.  Thus, the column with gcd(m,n) at its base has the coefficients
for mx + ny = gcd(m,n) in the top two.

Also, the column with 0 at its base has the smallest non-zero solution
to mx + ny = 0.  Multiples of this solution can be added to a particular
solution of mx + ny = k to get all solutions.

The quotients above the columns yield the continued fraction for m/n.

Let us work an example; m = 17, n = 23:

             0   1   2   1   5   <-- continued fraction
           -------------------
     1   0   1  -1   3  -4  23   <-- m times this row
     0   1   0   1  -2   3 -17   <-- plus n times this row
    17  23  17   6   5   1   0   <-- equals this row
     |   |               |
     m   n            gcd(m,n)

Thus, gcd(17,23) = 1, (-4+23k)17 + (3-17k)23 = 1, and the continued
fraction for 17/23 is [0,1,2,1,5].

It has been brought to my attention that W. A. Blankinship published
the essence of this algorithm in 1963.  See Blankinship Algorithm at
MathWorld.

Rob Johnson