Algorithm for Computing the LCM
The applet below illustrates an algorithm for finding the Least Common Multiple (LCM) of a number of integers.
Let there be a finite sequence of positive integers
xk(m+1) = xk(m), k ≠ k0
xk0(m+1) = xk0(m) + xk0.
In other words, the least element is increased by the corresponding x whereas the rest of the elements pass from X(m) to X(m+1) unchanged.
The algorithm stops when all elements in sequence X(m) are equal. Their common value L is exactly LCM(X).
(In the applet the numbers x1, x2, ..., xn that appear at the top row are modifiable by clicking left or right off their vertical center line. Press button Compute to see the algorithm running. The blue numbers the ones that have been modified at one of the steps.)
|What if applet does not run?|
Copyright © 1996-2018 Alexander Bogomolny
Let Mk = max xi(k). There are only finitely many k such that
Indeed, by a suitable re-numbering, we will then have
|X(m)||= (r·x1, x2(m), ..., xn(m)) and|
|X(m+1)||= ((r+1)·x1, x2(m), ..., xn(m)),|
with r a positive integer and
L ≠ r·x1 ≤ x2(m) ≤ ... ≤ xn(m) = Mm ≤ L
Now (r+l)·x1 ≤ L would imply that
r·x1 < L < (r+1)·x1.
But this contradicts the fact that L is a multiple of x1. Hence the assumption that m is not the last step is false and
But then Mm is a common multiple of all the xi, i = 1, 2, ..., n, and
L = Mm
This algorithm could be used to simulate a multitasking environment. In fact it was so used in the early days of computing. Assume, for example, you write a program which shows several balls bouncing up and down and off the walls. A task is associated with each ball that regularly updates its position and velocity. All balls must be continuously controlled, i.e. all the associated tasks need to be executed on a rotating basis. In addition, some balls may have to be updated more frequently than others.
The solution is this: each task k is assigned the (reversed) relative frequency xk and the LCM algorithm is run. One step of task k is executed whenever xk(m) is updated. The above discussion shows that all tasks will be updated with the required frequencies.
It's not hard to imagine why the algorithm is thought to resemble a patch of growing onions which are cut individually when they reach a prescribed height. Indeed in networking there is an important Onion Routing algorithm. In computational geometry, a similar idea led to the Onion Peeling Algorithm.
- A. J. Goldman; N. J. Fine, El655, The American Mathematical Monthly, Vol. 71, No. 9. (Nov., 1964), pp. 1045-1046.
Copyright © 1996-2018 Alexander Bogomolny[an error occurred while processing this directive]