(algorithm)
Definition: (no definition here, yet, but you can help.)
See also Euclid's algorithm, extended Euclid's algorithm.
Note:
Introduction. Given a pair (x, y) of positive real numbers, then one iteration of the Euclidean algorithm replaces the larger number by its least non-negative residue modulo the smaller number. If the two numbers are linearly dependent, the repetition of this process will eventually terminate with a pair in which one of the elements is zero. (If the original pair were integers, then the remaining non-zero element is their greatest common divisor.) Another property of the Euclidean algorithm, fundamental to the study of continued fractions, is that it produces increasingly good rational approximations to the original pair of real numbers. We will construct an iterative algorithm for n-tuples, generalizing both the terminating and approximating features of the Euclidean algorithm. Thus, if the original n-tuple of elements are Z-linearly dependent, the algorithm will necessarily terminate and discover the Z-relation among the elements of the original n-tuple. If the original n-tuple elements are not Z-linearly dependent, then the algorithm will "absolutely approximate" by producing lattice points arbitrarily close to the line generated by the original n-tuple. We emphasize that a major difficulty in the problem of constructing a generalization of the Euclidean algorithm is to give an iterative algorithm.
Helaman R. P. Ferguson and Rodney W. Forcade, Multidimensional Euclidean algorithms, Journal Fur Dir Reine Und Angewandte Mathematik 334:171-181, 1982. Walter de Gruyter & Co.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 17 December 2004.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
"Ferguson-Forcade algorithm", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 December 2004. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/fergusonForcade.html