 (algorithm)

Definition: (no definition here, yet, but you can help.)

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.