This post originated from an RSS feed registered with Agile Buzz
by Oliver Steele.
Original Post: Division-free LCM
Feed Title: Oliver Steele on Software
Feed URL: http://feeds.feedburner.com/osteele
Feed Description: Languages of the real and artificial.
A few years ago I described an algorithm for computing the greatest common denominator without division. (Euclid’s algorithm requires division, in order to compute the remainder.) Although less efficient than the standard algorithm, I found it easier to teach to my children when they were learning to add fractions.
Yesterday Paula Feynman asked me if there was a similar algorithm for finding the least common multiple. I came up with this one on the drive home. It can be used at grade school level — my children learned it in about half an hour — and I used their help (and the influence of Edwin Hutchins) to figure out the most teachable presentation.
Steps Towards Linear Algebra, or, Gauss Meets Euclid
Although the notation obscures it, this is a great warm-up for teaching Gaussian elimination. The numbers in the second and third columns are the factors of the two inputs that sum to the number in the first column. (This is why the first two rows are filled with the identity.) From here on out, it’s Gaussian elimination: replace a row by a linear combination of rows, until the leading term in one of them has been annihilated. Since there are only two rows, we can work in place (by extending one table), instead of copying the matrices to a new location each time.
The difference from standard Gaussian elimination is in the set of row coefficients. Since the algorithm doesn’t allow you to divide a row by a scalar (or multiply by non-integer) in order to produce unity, you’re limited to operations within the ring of integers. This ensures that the operations preserve the number-theoretic properties of the inputs, which is what lets you recover the GCD and its co-factors at the end.
Sure enough, after I showed my son how the algorithm worked, I was able to easily show him how to invert a matrix in order to solve a family of systems of equations. (He had already worked with systems of equations in school, and I had shown him how to represent a system as a matrix last week.)
Nothing New Under the Sun
While writing this posting, I discovered that the division-free technique for computing the GCD was actually Euclid’s original algorithm.
Similarly, I belatedly found that most of the technique for computing the LCM of two numbers was also previously known (probably as of a century ago?). It’s the “table method” of the “extended Euclidean algorithm”. However, that method, at least as described at Wikipedia, stops short of actually computing the LCM: it terminates with the co-factors of the inputs. So maybe I’m bringing something to the table, so to speak.
Previous Topic
