linguistic:voice_change
Rational and real numbers

Euclid's algorithm can be applied to real numbers, as described by Euclid in Book 10 of his Elements. The goal of the algorithm is to identify a real number g such that two given real numbers, a and b, are integer multiples of it: a = mg and b = ng, where m and n are integers. This identification is equivalent to finding an integer relation among the real numbers a and b; that is, it determines integers s and t such that sa + tb = 0. If such an equation is possible, a and b are called commensurable lengths, otherwise they are incommensurable lengths.

The real-number Euclidean algorithm differs from its integer counterpart in two respects. First, the remainders r are real numbers, although the quotients q are integers as before. Second, the algorithm is not guaranteed to end in a finite number N of steps. If it does, the fraction a / b is a rational number, i.e., the ratio of two integers

and can be written as a finite continued fraction. If the algorithm does not stop, the fraction a / b is an irrational number and can be described by an infinite continued fraction. Examples of infinite continued fractions are the golden ratio φ = and the square root of two, √ 2 =. The algorithm is unlikely to stop, since almost all ratios a / b of two real numbers are irrational.

An infinite continued fraction may be truncated at a step k to yield an approximation to a / b that improves as k is increased. The approximation is described by convergents m / n; the numerator and denominators are coprime and obey the recurrence relation

where m = n = 1 and m = n = 0 are the initial values of the recursion. The convergent m / n is the best rational number approximation to a / b with denominator n: