Euclidean algorithm

The Euclidean algorithm is an algorithm from the mathematical branch of number theory. It can be used to the greatest common divisor of two integers calculate. The method is named after the Greek mathematician Euclid, who described it in his book " The Elements".

The greatest common divisor of two numbers can also be determined from their prime factorizations. But if neither of the two numbers the prime factorization known as the Euclidean algorithm is the fastest method for computing the greatest common divisor.

The Euclidean algorithm can be applied not only to natural numbers. Rather, the list may be the greatest common divisor of two elements of each ring are calculated Euclidean. These include, for example, polynomials over a field.

• 2.1 Example
• 2.2 Description of Pseudocode 2.2.1 Recursive variant
• 2.2.2 Iterative variant

• 6.1 Rational and real numbers
• 6.2 polynomials 6.2.1 polynomials with coefficients from a factorial ring

The classical algorithm

Euclid computed the greatest common divisor, by looking for a common " measure " for the lengths of two lines. To this end, he moved repeatedly from the smaller of the two lengths of the larger ones. He utilizes the fact that the greatest common divisor of two numbers (or lengths) does not change when you subtract the smaller from the larger.

If the difference of and very large, possibly many Subtraktionsschritte are necessary. Hippasos of Metapontum used before Euclid this so-called exchange removal geometrically for the proof of the incommensurability in certain regular n - corners: In the square or in the regular pentagon as there is no common factor (dimension ) of a page with the diagonal.

Nowadays, in general, the division algorithm described below is used in the steps 2 and 3 are replaced in that, taking the place of the difference and, for the remainder of the division by. Another advantage of this variant is that you can (for example, polynomial rings over a field ) transferred to any Euclidean rings in which the classical algorithm does not work.

Description by pseudocode

The classic algorithm here shown in pseudo-code for non-negative integers a and b:

EUCLID_OLD (a, b ) 1 if a = 0 2 then return b 3 else as long as b ≠ 0 4 if a> b 5 then a a - b 6 b else b - a 7 return a This algorithm can also be specified in a recursive version:

EUCLID_OLD_RECURSIVE (a, b ) 1 if b = 0 2 then return a 3 else if a = 0 4 then return b 5 else if a> b 6 then return EUCLID_OLD_RECURSIVE (a - b, b ) 7 else return EUCLID_OLD_RECURSIVE (a, b - a ) Modern Euclidean algorithm

Nowadays, occurring in the classical algorithm repeated subtraction of a value is replaced by a single division with remainder Modern Euclidean algorithm performs well in each step such a division with remainder. It begins with the two figures and whose greatest common divisor is to be determined.

In each further step, a further division is carried out with radical having the divisor and the remainder of the previous step. Namely until a division rises, that is, the remainder is zero.

The divisor of the last division is then the greatest common divisor.

As the numbers in each step at least halved, the procedure is extremely fast, even with large numbers.

Example

The greatest common divisor of 1071 and 1029 is calculated using the Euclidean algorithm as follows:

The greatest common divisor of 1071 and 1029 is therefore 21

Description by pseudocode

Below the modern Euclidean algorithm is described both in a recursive, as well as an iterative version. Here, and in each case the two numbers whose greatest common divisor is to be calculated.

Recursive variant

EUCLID (a, b ) 1 if b = 0 2 then return a 3 else return EUCLID (b, a mod b ) Iterative variant

EUCLID (a, b ) 1 while b ≠ 0 2 hours a mod b 3 a b 4 b h 5 return a Correctness of the algorithm

In each step of the algorithm, a division with remainder is executed.

Division with remainder has the property that

Applies.

In the last step of the algorithm

Is and it is therefore

As the first step, and has been, is

Historical development

The Euclidean algorithm is the oldest known non-trivial algorithm. The process was described by Euclid around 300 BC in his work Elements. In Book VII ( Proposition 1 and 2) he formulated the algorithm for integers and in Book X ( Proposition 2 and 3) for real numbers. The latter version is a geometric algorithm and Euclid called him antepheiresis ( AC removal ). He was looking for a biggest joint " degree " of two routes: a third route, so that the length of the two original routes are multiples of the length of the third track.

The process was probably not invented by Euclid because he the findings of earlier mathematicians summarized in the elements. The mathematician and historian Bartel Leendert van der Waerden believed that Book VII is already used by the Pythagoreans textbook of number theory. Hippasos of Metapontum led about 500 BC probably his proof of the incommensurability of certain lines and diagonals on the basis of the Euclidean algorithm by Eudoxus of Cnidus and also (around 375 BC) knew well the procedure. Aristotle ( 330 BC ) had this procedure in his work Topik ( 158b 29-35 ) back.

Centuries later, the Euclidean algorithm was discovered independently of one another in India and China, mainly in order to solve Diophantine equations in astronomy and to create accurate calendar. In the fifth century, the Indian mathematician and astronomer Aryabhata described the algorithm as the " pulverizer ", probably due to its effectiveness in solving Diophantine equations. Although already the Chinese mathematician and astronomer Sun Tzu has described a special case of the Chinese remainder theorem, the general solution, however, was of Qin Jiushao 1247 in his book Shushu Jiuzhang (Chinese数 书 九章/数 书 九章, Mathematical Treatise in Nine Chapters ') published. In modern Europe, the Euclidean algorithm was first described back in the second edition of Bachets Problèmes plaisants et delectables qui se font par les nombres. The algorithm has been used in Europe for releasing Diophantine equations and the calculation of the continued fraction expansion. Nicholas Saunderson published the extended Euclidean algorithm and wrote him Roger Cotes to as a method for efficient calculation of continued fractions.

In the 19th century, the Euclidean algorithm gave impetus to the development of new number systems such as the Gaussian numbers and the Eisenstein numbers. 1815 Carl Friedrich Gauss used the Euclidean algorithm to show the unique factorization of Gaussian numbers. His work was not published until the year 1832. Gauss mentioned the algorithm also in his 1801 published work Disquisitiones Arithmeticae, but only as a method for the computation of continued fractions. Peter Gustav Lejeune Dirichlet appears to be the first to have the Euclidean algorithm described as the basis of a large part of number theory. He noted that many results in number theory, such as the unique factorization also apply to other number systems, in which the Euclidean algorithm can be applied. Dirichlet's lectures on number theory were edited by Richard Dedekind and extended, who used the Euclidean algorithm for the study of algebraic numbers, a new general Zahlenart. Dedekind example, was the first who proved Pierre de Fermat's two- square theorem with the unique factorization of Gaussian numbers. Dedekind introduced the concept of Euclidean ring, a number system in which a generalized version of the Euclidean algorithm can be applied. In the last decades of the 19th century, the Euclidean algorithm gradually stepped behind Dedekind's general theory of ideals back.

Jacques Charles François Sturm 1829, the storm developed between chains to calculate the number of zeros of a polynomial in a given interval. In this case, a variation of Euclid's algorithm is used to determine the individual links of a chain.

In the past there have been numerous attempts to generalize the Euclidean algorithm to more than two natural numbers in order to, for example, find out their greatest common divisor also optimal (about the smallest possible ) multipliers that deliver in the linear combination with the numbers this divider. The modern state of research on this has been shown by Havas, Majewski and Matthews.

The Euclidean algorithm was the first algorithm for the computation of integer relations commensurable real numbers. In recent years, other algorithms have been developed for this task, such as the Ferguson - Forcade algorithm of 1979 and related algorithms, the LLL algorithm, which HJLS algorithm ( according to the authors Håstad, Just, Lagarias and Schnorr ) and the PSLQ algorithm (after partial sum of squares plus LQ matrix decomposition). In 2001 it was shown that the reported by some authors instability of HJLS algorithm only based on an improper implementation and that this algorithm is equivalent to PSLQ algorithm. Passenger are based on the actual Euclidean algorithm its multidimensional generalizations of George Szekeres (1970), Helaman Ferguson and Rodney Forcade (1981 ), Just ( 1992), by Rössner and Schnorr (1996) and the very general approach of Lagarias (1994).

Developed in 1969 Cole and Davie the two-player game " Euclid ", which is based on the Euclidean algorithm. In this game, there is an optimal strategy. The two players start with two piles of stones and. In each turn, a player takes as many times stones from the larger pile, as the smaller stack is large. In this way, the next player can reduce the larger stack of stones on stones, the size of the smaller stack. The winner is the player who removes completely a stack.

Runtime Analysis

The Euclidean algorithm can be the gcd with relatively little effort (compared to calculate the prime factorization of the numbers a and b ) calculate. The runtime analysis, it turns out that the worst case input are two consecutive Fibonacci numbers. In successive Fibonacci numbers always arises as a residual the next smaller Fibonacci number. The number of required divisions is in the worst case, Θ (log (ab) ), where log (ab) is proportional to the number of digits in the input (see Landau symbols).

Since the time required for the division of two numbers in turn depends on the number of digits of the numbers to an actual running time of O (log (ab) ^ 3 ) results in a naive implementation of the division. Due to the complete transfer of the actual calculation in the frequency domain by means of a special fast Fourier transform as in Schönhage - Strassen algorithm is used, fast Reziprokwertberechnung with the Newton method ( in the frequency domain ) for the division and subsequent back-transformation by inverse fast Fourier transformation can thus comes to a theoretical lower limit of O (n ⋅ log (n) ²) where n is the maximum number of digits of a and b.

Developed by Schönhage variant of the Euclidean algorithm could be further accelerated by parallelization on a multi -processor system.

Euclidean algorithm and continued fraction

The quotients that occur in the Euclidean algorithm are exactly the partial denominators that occur in the continued fraction expansion of. Here for the above example with highlighted paragraphs:

From this it can develop the continued fraction:

This method can also be applied for any real number. Is not rational, then the algorithm simply never ends. The thus obtained result to the quotient then provides the infinite continued fraction expansion of dar.

Other number systems

The Euclidean algorithm for calculating the greatest common divisor of two integers is used as described above. The algorithm can, however, generalize to real numbers and more exotic number systems such as polynomials, quadratic numbers and the non-commutative Hurwitzquaternionen. In the latter case, the Euclidean algorithm is used to demonstrate the important property of a unique factorization. That is, such a number unique to irreducible elements of the generalization of primes can be disassembled. The unique factorization is fundamental to many proofs of number theory.

Rational and real numbers

As already described by Euclid in Book 10 of his work " The Elements", the Euclidean algorithm can be applied to real numbers. The goal of the algorithm is then to find a real number so that the two numbers and integer multiples of this number. This task is equivalent to finding an integer relationship between the two real numbers, and so the calculation of two whole numbers and, applies. Euclid used this algorithm when considering the incommensurability of routes.

The Euclidean algorithm for real numbers differs in two respects from its counterpart for integers. First, the rest is a real number although the ratios are still integers. Secondly, the algorithm does not always ends after a finite number of steps. However, when he does this, the breakage is a rational number; so there are two integers and with

And can be written as a continued fraction. If the algorithm does not end, then the break is an irrational number, and is identical with the endless chain breakage. Examples of infinite continued fractions, the golden number and the square root of second In general, it is unlikely that the algorithm stops, since almost all ratios of two real numbers are irrational numbers.

Polynomials

Polynomials in one variable over a field form a Euclidean ring. The polynomial for these polynomials thus a division with remainder of the Euclidean algorithm, and can equally be carried out as in the whole numbers. The calculation of the greatest common divisor of the polynomials, and is as follows, for example:

Thus the greatest common divisor of and is.

Polynomials with coefficients from a factorial ring

We consider a factorial ring ( ie a ring with up to units unique prime factorization ) and shall consider polynomials in the polynomial ring, ie polynomials in one variable with coefficients in. In the special case in which a body is, so we get the ring of polynomials over in two variables.

In Division is not generally feasible with rest. Be, for example, and in. Polynomial in returns the quotient, which is not located in. We can, however, a pseudo division defined as follows: Let and be polynomials of degree or, is the leading coefficient of the polynomial, and. Then there are polynomials, so that

Again being of a lesser degree than. By repeatedly performing the pseudo division, the gcd of and can determine, however, the method in practice is inefficient, since the factors can be the coefficients of the intermediate results grow exponentially. In order to avoid the after each step, the content of the residue to be removed, but this in turn requires gcd calculations. Efficient can be the gcd with the Subresultantenverfahren calculate.

Variants

By Josef stone comes the named after him, Einstein's algorithm which does not require the elaborate divisions. He used only divisions by two, to be carried out very quickly by a computer. Therefore, this algorithm is called algorithm and binary Euclidian. However, the performance advantage on real computers can only be seen if the integer type exceeds the width of the processor registers.

If one notices the Euclidean algorithm, the quotient of the intermediate steps, then can be thus a representation

With whole numbers and find. This is called the extended Euclidean algorithm. Thus, the inverse can be calculated in residue class rings.

Another extension is the algorithm behind the quadratic reciprocity law. This can be the Jacobi symbol efficiently compute.