Euclidean algorithm: Difference between revisions
Jump to navigation
Jump to search
imported>Jacobolus m →Rational and real numbers: clarify |
imported>T. Cadwallader Phloog →Historical development: Replaced jury-rigged quote box (unreadable in dark mode, among other problems) with a standard quote box |
||
| Line 40: | Line 40: | ||
Thus, Euclid's algorithm, which computes the GCD of two integers, suffices to calculate the GCD of arbitrarily many integers. | Thus, Euclid's algorithm, which computes the GCD of two integers, suffices to calculate the GCD of arbitrarily many integers. | ||
== Description == | |||
=== Procedure === | === Procedure === | ||
{{Euclidean algorithm steps}} | {{Euclidean algorithm steps}} | ||
The Euclidean algorithm can be thought of as constructing a sequence of non-negative integers that begins with the two given integers <math>r_{-2} = a</math> and <math>r_{-1} = b</math> and will eventually terminate with the integer zero: <math>\{ r_{-2} = a,\ r_{-1} = b,\ r_0,\ r_1,\ \cdots,\ r_{n-1},\ r_n = 0 \}</math> with <math>r_{k+1} < r_k</math> | The Euclidean algorithm can be thought of as constructing a sequence of non-negative integers that begins with the two given integers <math>r_{-2} = a</math> and <math>r_{-1} = b</math> and will eventually terminate with the integer zero: <math>\{ r_{-2} = a,\ r_{-1} = b,\ r_0,\ r_1,\ \cdots,\ r_{n-1},\ r_n = 0 \}</math> with <math>r_{k+1} < r_k.</math> The integer <math>r_{n-1}</math> will then be the GCD and we can state <math>\text{gcd}(a,b) = r_{n-1}.</math> The algorithm indicates how to construct the intermediate remainders <math>r_k</math> via [[Euclidean division|division-with-remainder]] on the preceding pair <math>(r_{k-2},\ r_{k-1})</math> by finding an integer quotient <math>q_k</math> so that: | ||
: <math>r_{k-2} = q_k \cdot r_{k-1} + r_k \text{, with } \ r_{k-1} > r_k \geq 0.</math> | : <math>r_{k-2} = q_k \cdot r_{k-1} + r_k \text{, with } \ r_{k-1} > r_k \geq 0.</math> | ||
Because the sequence of non-negative integers <math>\{ r_k \}</math> is strictly decreasing, it eventually [[Well-ordering principle|must terminate]]. In other words, since <math>r_k \ge 0</math> for every <math>k</math> | Because the sequence of non-negative integers <math>\{ r_k \}</math> is strictly decreasing, it eventually [[Well-ordering principle|must terminate]]. In other words, since <math>r_k \ge 0</math> for every <math>k,</math> and each <math>r_k</math> is an integer that is strictly smaller than the preceding <math>r_{k-1},</math> there eventually cannot be a non-negative integer smaller than zero, and hence the algorithm must terminate. In fact, the algorithm will always terminate at the {{math|''n''}}th step with <math>r_n</math> equal to zero.<ref>{{Harvnb|Stark|1978|p=18}}</ref> | ||
To illustrate, suppose the GCD of 1071 and 462 is requested. The sequence is initially <math>\{r_{-2} = 1071,\ r_{-1} = 462 \}</math> and in order to find <math>r_0</math> | To illustrate, suppose the GCD of 1071 and 462 is requested. The sequence is initially <math>\{r_{-2} = 1071,\ r_{-1} = 462 \}</math> and in order to find <math>r_0,</math> we need to find integers <math>q_0</math> and <math>r_0 < r_{-1}</math> such that: | ||
: <math>1071 = q_0 \cdot 462 + r_0</math> | : <math>1071 = q_0 \cdot 462 + r_0.</math> | ||
This is the quotient <math>q_0 = 2</math> since <math>1071 = 2 \cdot 462 + 147</math> | This is the quotient <math>q_0 = 2</math> since <math>1071 = 2 \cdot 462 + 147.</math> This determines <math>r_0 = 147</math> and so the sequence is now <math>\{1071,\ 462,\ r_0 = 147 \}.</math> The next step is to continue the sequence to find <math>r_1</math> by finding integers <math>q_1</math> and <math>r_1 < r_0</math> such that: | ||
: <math>462 = q_1 \cdot 147 + r_1</math> | : <math>462 = q_1 \cdot 147 + r_1.</math> | ||
This is the quotient <math>q_1 = 3</math> since <math>462 = 3 \cdot 147 + 21</math> | This is the quotient <math>q_1 = 3</math> since <math>462 = 3 \cdot 147 + 21.</math> This determines <math>r_1 = 21</math> and so the sequence is now <math>\{1071,\ 462,\ 147,\ r_1 = 21 \}.</math> The next step is to continue the sequence to find <math>r_2</math> by finding integers <math>q_2</math> and <math>r_2 < r_1</math> such that: | ||
: <math>147 = q_2 \cdot 21 + r_2</math> | : <math>147 = q_2 \cdot 21 + r_2.</math> | ||
This is the quotient <math>q_2 = 7</math> since <math>147 = 7 \cdot 21 + 0</math> | This is the quotient <math>q_2 = 7</math> since <math>147 = 7 \cdot 21 + 0.</math> This determines <math>r_2 = 0</math> and so the sequence is completed as <math>\{1071,\ 462,\ 147,\ 21,\ r_2 = 0 \}</math> as no further non-negative integer smaller than <math>0</math> can be found. The penultimate remainder <math>21</math> is therefore the requested GCD: | ||
: <math>\text{gcd}(1071,\ 462) = 21.</math> | : <math>\text{gcd}(1071,\ 462) = 21.</math> | ||
We can generalize slightly by dropping any ordering requirement on the initial two values <math>a</math> and <math>b</math> | We can generalize slightly by dropping any ordering requirement on the initial two values <math>a</math> and <math>b.</math> If <math>a = b,</math> the algorithm may continue and trivially find that <math>\text{gcd}(a,\ a) = a</math> as the sequence of remainders will be <math>\{a,\ a,\ 0\}.</math> If <math>a < b,</math> then we can also continue since <math>a \equiv 0 \cdot b + a,</math> suggesting the next remainder should be <math>a</math> itself, and the sequence is <math>\{a,\ b,\ a,\ \cdots \}.</math> Normally, this would be invalid because it breaks the requirement <math>r_0 < r_{-1}</math> but now we have <math>a < b</math> by construction, so the requirement is automatically satisfied and the Euclidean algorithm can continue as normal. Therefore, dropping any ordering between the first two integers does not affect the conclusion that the sequence must eventually terminate because the next remainder will always satisfy <math>r_0 < b</math> and everything continues as above. The only modifications that need to be made are that <math>r_{k} < r_{k-1}</math> only for <math>k \ge 0,</math> and that the sub-sequence of non-negative integers <math>\{ r_{k-1} \}</math> for <math>k \ge 0</math> is strictly decreasing, therefore excluding <math>a = r_{-2}</math> from both statements. | ||
=== Proof of validity === | === Proof of validity === | ||
The existence of a step <math>N</math> such that <math>r_N=0</math> follows from the condition <math>|r_i|<|r_{i-1}|</math>, for <math>i\geq1</math>. This ensures that the algorithm terminates. | |||
The last non-zero remainder <math>r_{N-1}</math> being equal to <math>\gcd(a,b)</math> follows from the following properties of <math>\gcd</math> | |||
1. <math>\gcd(x,0)=x</math>, for all <math>x\neq0</math>. | |||
:In fact, the common divisors of <math>x</math> and <math>0</math> are exactly all the divisors of <math>x</math>, of which <math>x</math> itself is the largest. | |||
2. <math>\gcd(x,y)=\gcd(y,x-zy)</math> | |||
:In fact, the sets of common divisors of the pairs <math>(x,y)</math> and <math>(y, x-zy)</math> are the same. In particular, the largest of their common divisors are the same. | |||
:To see this, assume that <math>d</math> is a common divisor of <math>x</math> and <math>y</math>. This means that there are integers <math>X,Y</math> such that <math>x=dX</math> and <math>y=dY</math>. It follows that <math>x-zy=dX-zdY=d(X-zY)</math>, where <math>X-zY</math> is an integer. Therefore, <math>d</math> is also a divisor of <math>x-zy</math>. | |||
:Conversely, if <math>d</math> is a common divisor of <math>x-zy</math> and <math>y</math>, then there are integers <math>Z</math> and <math>Y</math> such that <math>x-zy=dZ</math> and <math>y=dY</math>. From this <math>x=(x-zy)+zy=dZ+zdY=d(Z+zY)</math>, where <math>Z+zY</math> is an integer. Therefore, <math>d</math> is also a common divisor of <math>x</math> and <math>y</math>. | |||
Now, the Euclidean algorithm starts with the pair <math>(r_{-2},r_{-1})=(a,b)</math> and at each step, the pair of remainders <math>(r_{k-2},r_{k-1})</math> is replaced by <math>(r_{k-1},r_{k-2}-q_kr_{k-1})=(r_{k-1},r_{k})</math>. Property 2 shows that the <math>\gcd</math> of the pairs remains invariant. In particular, the <math>\gcd</math> of the first pair <math>(a,b)</math> and the last pair <math>(r_{N-1},0)</math> are the same. Applying Property 1, <math>\gcd(a,b)=\gcd(r_{N-1},0)=r_{N-1}</math>. | |||
=== Worked example === | === Worked example === | ||
| Line 186: | Line 195: | ||
In the 19th century, the Euclidean algorithm led to the development of new number systems, such as [[Gaussian integer]]s and [[Eisenstein integer]]s. In 1815, [[Carl Friedrich Gauss|Carl Gauss]] used the Euclidean algorithm to demonstrate unique factorization of [[Gaussian integer]]s, although his work was first published in 1832.<ref name="Gauss_1832" /> Gauss mentioned the algorithm in his ''[[Disquisitiones Arithmeticae]]'' (published 1801), but only as a method for [[continued fraction]]s.<ref name="Stillwell, p. 31"/> [[Peter Gustav Lejeune Dirichlet]] seems to have been the first to describe the Euclidean algorithm as the basis for much of number theory.<ref>{{Harvnb|Stillwell|1997|pp=31–32}}</ref> Lejeune Dirichlet noted that many results of number theory, such as unique factorization, would hold true for any other system of numbers to which the Euclidean algorithm could be applied.<ref>{{Harvnb|Lejeune Dirichlet|1894|pp=29–31}}</ref> Lejeune Dirichlet's lectures on number theory were edited and extended by [[Richard Dedekind]], who used Euclid's algorithm to study [[algebraic integer]]s, a new general type of number. For example, Dedekind was the first to prove [[Fermat's theorem on sums of two squares|Fermat's two-square theorem]] using the unique factorization of Gaussian integers.<ref>[[Richard Dedekind]] in {{Harvnb|Lejeune Dirichlet|1894|loc=Supplement XI}}</ref> Dedekind also defined the concept of a [[Euclidean domain]], a number system in which a generalized version of the Euclidean algorithm can be defined (as described [[#Euclidean domains|below]]). In the closing decades of the 19th century, the Euclidean algorithm gradually became eclipsed by Dedekind's more general theory of [[ideal (ring theory)|ideals]].<ref>{{Harvnb|Stillwell|2003|pp=41–42}}</ref> | In the 19th century, the Euclidean algorithm led to the development of new number systems, such as [[Gaussian integer]]s and [[Eisenstein integer]]s. In 1815, [[Carl Friedrich Gauss|Carl Gauss]] used the Euclidean algorithm to demonstrate unique factorization of [[Gaussian integer]]s, although his work was first published in 1832.<ref name="Gauss_1832" /> Gauss mentioned the algorithm in his ''[[Disquisitiones Arithmeticae]]'' (published 1801), but only as a method for [[continued fraction]]s.<ref name="Stillwell, p. 31"/> [[Peter Gustav Lejeune Dirichlet]] seems to have been the first to describe the Euclidean algorithm as the basis for much of number theory.<ref>{{Harvnb|Stillwell|1997|pp=31–32}}</ref> Lejeune Dirichlet noted that many results of number theory, such as unique factorization, would hold true for any other system of numbers to which the Euclidean algorithm could be applied.<ref>{{Harvnb|Lejeune Dirichlet|1894|pp=29–31}}</ref> Lejeune Dirichlet's lectures on number theory were edited and extended by [[Richard Dedekind]], who used Euclid's algorithm to study [[algebraic integer]]s, a new general type of number. For example, Dedekind was the first to prove [[Fermat's theorem on sums of two squares|Fermat's two-square theorem]] using the unique factorization of Gaussian integers.<ref>[[Richard Dedekind]] in {{Harvnb|Lejeune Dirichlet|1894|loc=Supplement XI}}</ref> Dedekind also defined the concept of a [[Euclidean domain]], a number system in which a generalized version of the Euclidean algorithm can be defined (as described [[#Euclidean domains|below]]). In the closing decades of the 19th century, the Euclidean algorithm gradually became eclipsed by Dedekind's more general theory of [[ideal (ring theory)|ideals]].<ref>{{Harvnb|Stillwell|2003|pp=41–42}}</ref> | ||
{| | {{Quote box|"[The Euclidean algorithm] is the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present day."|author=[[Donald Knuth]]|source=''The Art of Computer Programming, Vol. 2: Seminumerical Algorithms'', 2nd edition (1981), p. 318|align=left |width=25em |fontsize=85% |style=max-width:27%}} | ||
"[The Euclidean algorithm] is the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present day." | |||
| | |||
|} | |||
Other applications of Euclid's algorithm were developed in the 19th century. In 1829, [[Jacques Charles François Sturm|Charles Sturm]] showed that the algorithm was useful in the [[Sturm's theorem|Sturm chain]] method for counting the real roots of polynomials in any given interval.<ref>{{cite journal | last = Sturm |first = C. | author-link = Jacques Charles François Sturm | year = 1829 | title = Mémoire sur la résolution des équations numériques |language=fr | journal = Bull. Des sciences de Férussac | volume = 11 | pages = 419–422}}</ref> | Other applications of Euclid's algorithm were developed in the 19th century. In 1829, [[Jacques Charles François Sturm|Charles Sturm]] showed that the algorithm was useful in the [[Sturm's theorem|Sturm chain]] method for counting the real roots of polynomials in any given interval.<ref>{{cite journal | last = Sturm |first = C. | author-link = Jacques Charles François Sturm | year = 1829 | title = Mémoire sur la résolution des équations numériques |language=fr | journal = Bull. Des sciences de Férussac | volume = 11 | pages = 419–422}}</ref> | ||
| Line 208: | Line 212: | ||
| volume = 1 | | volume = 1 | ||
| year = 1979| doi-access = free | | year = 1979| doi-access = free | ||
}}</ref> and the [[Lenstra–Lenstra–Lovász lattice basis reduction algorithm|LLL algorithm]].<ref>{{cite journal | last = Peterson |first = I. | date = 12 August 2002 | title = Jazzing Up Euclid's Algorithm | journal = ScienceNews | url=http://www.sciencenews.org/view/generic/id/172/title/Math_Trek__Jazzing_Up_Euclids_Algorithm}}</ref><ref>{{cite journal | last = Cipra | first = Barry Arthur |author-link=Barry Arthur Cipra | title = The Best of the 20th Century: Editors Name Top 10 Algorithms | journal = SIAM News | volume = 33 | date = 16 May 2000 | publisher = [[Society for Industrial and Applied Mathematics]] | issue = 4 | url = https://www.siam.org/pdf/news/637.pdf | access-date = 19 July 2016 | archive-url = https://web.archive.org/web/20160922144038/https://www.siam.org/pdf/news/637.pdf | archive-date = 22 September 2016 | url-status = dead | df = dmy-all }}</ref> | }}</ref> and the [[Lenstra–Lenstra–Lovász lattice basis reduction algorithm|LLL algorithm]].<ref>{{cite journal | last = Peterson | first = I. | date = 12 August 2002 | title = Jazzing Up Euclid's Algorithm | journal = ScienceNews | url = http://www.sciencenews.org/view/generic/id/172/title/Math_Trek__Jazzing_Up_Euclids_Algorithm | archive-date = 16 April 2009 | access-date = 7 April 2009 | archive-url = https://web.archive.org/web/20090416090019/http://www.sciencenews.org/view/generic/id/172/title/Math_Trek__Jazzing_Up_Euclids_Algorithm | url-status = live }}</ref><ref>{{cite journal | last = Cipra | first = Barry Arthur |author-link=Barry Arthur Cipra | title = The Best of the 20th Century: Editors Name Top 10 Algorithms | journal = SIAM News | volume = 33 | date = 16 May 2000 | publisher = [[Society for Industrial and Applied Mathematics]] | issue = 4 | url = https://www.siam.org/pdf/news/637.pdf | access-date = 19 July 2016 | archive-url = https://web.archive.org/web/20160922144038/https://www.siam.org/pdf/news/637.pdf | archive-date = 22 September 2016 | url-status = dead | df = dmy-all }}</ref> | ||
In 1969, Cole and Davie developed a two-player game based on the Euclidean algorithm, called ''The Game of Euclid'',<ref>{{cite journal | last1 = Cole | first1 = A. J. | last2 = Davie | first2 = A. J. T. | year = 1969 | title = A game based on the Euclidean algorithm and a winning strategy for it | journal = Math. Gaz. | volume = 53 | pages = 354–357 | doi = 10.2307/3612461 | jstor = 3612461 | issue = 386| s2cid = 125164797 }}</ref> which has an optimal strategy.<ref>{{cite journal | doi = 10.2307/2689037 | last = Spitznagel | first = E. L. | year = 1973 | title = Properties of a game based on Euclid's algorithm | jstor = 2689037 | journal = Math. Mag. | volume = 46 | issue = 2 | pages = 87–92}}</ref> The players begin with two piles of {{math|''a''}} and {{math|''b''}} stones. The players take turns removing {{math|''m''}} multiples of the smaller pile from the larger. Thus, if the two piles consist of {{math|''x''}} and {{math|''y''}} stones, where {{math|''x''}} is larger than {{math|''y''}}, the next player can reduce the larger pile from {{math|''x''}} stones to {{math|''x'' − ''my''}} stones, as long as the latter is a nonnegative integer. The winner is the first player to reduce one pile to zero stones.<ref>{{Harvnb|Rosen|2000|p=95}}</ref><ref>{{cite book | last = Roberts | first = J. | year = 1977 | title = Elementary Number Theory: A Problem Oriented Approach | publisher = [[MIT Press]] | location = Cambridge, MA | isbn = 0-262-68028-9 | pages = [https://archive.org/details/Elementary_00_Robe/page/1 1–8] | url = https://archive.org/details/Elementary_00_Robe/page/1 }}</ref> | In 1969, Cole and Davie developed a two-player game based on the Euclidean algorithm, called ''The Game of Euclid'',<ref>{{cite journal | last1 = Cole | first1 = A. J. | last2 = Davie | first2 = A. J. T. | year = 1969 | title = A game based on the Euclidean algorithm and a winning strategy for it | journal = Math. Gaz. | volume = 53 | pages = 354–357 | doi = 10.2307/3612461 | jstor = 3612461 | issue = 386| s2cid = 125164797 }}</ref> which has an optimal strategy.<ref>{{cite journal | doi = 10.2307/2689037 | last = Spitznagel | first = E. L. | year = 1973 | title = Properties of a game based on Euclid's algorithm | jstor = 2689037 | journal = Math. Mag. | volume = 46 | issue = 2 | pages = 87–92}}</ref> The players begin with two piles of {{math|''a''}} and {{math|''b''}} stones. The players take turns removing {{math|''m''}} multiples of the smaller pile from the larger. Thus, if the two piles consist of {{math|''x''}} and {{math|''y''}} stones, where {{math|''x''}} is larger than {{math|''y''}}, the next player can reduce the larger pile from {{math|''x''}} stones to {{math|''x'' − ''my''}} stones, as long as the latter is a nonnegative integer. The winner is the first player to reduce one pile to zero stones.<ref>{{Harvnb|Rosen|2000|p=95}}</ref><ref>{{cite book | last = Roberts | first = J. | year = 1977 | title = Elementary Number Theory: A Problem Oriented Approach | publisher = [[MIT Press]] | location = Cambridge, MA | isbn = 0-262-68028-9 | pages = [https://archive.org/details/Elementary_00_Robe/page/1 1–8] | url = https://archive.org/details/Elementary_00_Robe/page/1 }}</ref> | ||
| Line 544: | Line 548: | ||
The [[binary GCD algorithm]] is an efficient alternative that substitutes division with faster operations by exploiting the [[binary numeral system|binary]] representation used by computers.<ref>{{harvnb|Knuth|1997}}, pp. 321–323</ref><ref>{{cite journal | last = Stein | first = J. | year = 1967 | title = Computational problems associated with Racah algebra | journal = Journal of Computational Physics | volume = 1 | pages = 397–405 | doi = 10.1016/0021-9991(67)90047-2 | issue = 3| bibcode = 1967JCoPh...1..397S }}</ref> However, this alternative also scales like [[big-O notation|''O''(''h''²)]]. It is generally faster than the Euclidean algorithm on real computers, even though it scales in the same way.<ref name="Crandall_2001">{{harvnb|Crandall|Pomerance|2001}}, pp. 77–79, 81–85, 425–431</ref> Additional efficiency can be gleaned by examining only the leading digits of the two numbers ''a'' and ''b''.<ref>{{harvnb|Knuth|1997}}, p. 328</ref><ref>{{cite journal | last = Lehmer|first = D. H.|author-link=Derrick Henry Lehmer | year = 1938 | title = Euclid's Algorithm for Large Numbers | journal = The American Mathematical Monthly | volume = 45 | pages = 227–233 | doi = 10.2307/2302607 | jstor = 2302607 | issue = 4}}</ref> The binary algorithm can be extended to other bases (''k''-ary algorithms),<ref>{{cite journal | last = Sorenson |first=J. | year = 1994 | title = Two fast GCD algorithms | journal = J. Algorithms | volume = 16 |issue=1 | pages = 110–144 | doi = 10.1006/jagm.1994.1006}}</ref> with up to fivefold increases in speed.<ref>{{cite journal | last = Weber |first=K. | year = 1995 | title = The accelerated GCD algorithm | journal = ACM Trans. Math. Softw. | volume = 21 |issue=1 | pages = 111–122 | doi = 10.1145/200979.201042|s2cid=14934919 | doi-access = free }}</ref> [[Lehmer's GCD algorithm]] uses the same general principle as the binary algorithm to speed up GCD computations in arbitrary bases. | The [[binary GCD algorithm]] is an efficient alternative that substitutes division with faster operations by exploiting the [[binary numeral system|binary]] representation used by computers.<ref>{{harvnb|Knuth|1997}}, pp. 321–323</ref><ref>{{cite journal | last = Stein | first = J. | year = 1967 | title = Computational problems associated with Racah algebra | journal = Journal of Computational Physics | volume = 1 | pages = 397–405 | doi = 10.1016/0021-9991(67)90047-2 | issue = 3| bibcode = 1967JCoPh...1..397S }}</ref> However, this alternative also scales like [[big-O notation|''O''(''h''²)]]. It is generally faster than the Euclidean algorithm on real computers, even though it scales in the same way.<ref name="Crandall_2001">{{harvnb|Crandall|Pomerance|2001}}, pp. 77–79, 81–85, 425–431</ref> Additional efficiency can be gleaned by examining only the leading digits of the two numbers ''a'' and ''b''.<ref>{{harvnb|Knuth|1997}}, p. 328</ref><ref>{{cite journal | last = Lehmer|first = D. H.|author-link=Derrick Henry Lehmer | year = 1938 | title = Euclid's Algorithm for Large Numbers | journal = The American Mathematical Monthly | volume = 45 | pages = 227–233 | doi = 10.2307/2302607 | jstor = 2302607 | issue = 4}}</ref> The binary algorithm can be extended to other bases (''k''-ary algorithms),<ref>{{cite journal | last = Sorenson |first=J. | year = 1994 | title = Two fast GCD algorithms | journal = J. Algorithms | volume = 16 |issue=1 | pages = 110–144 | doi = 10.1006/jagm.1994.1006}}</ref> with up to fivefold increases in speed.<ref>{{cite journal | last = Weber |first=K. | year = 1995 | title = The accelerated GCD algorithm | journal = ACM Trans. Math. Softw. | volume = 21 |issue=1 | pages = 111–122 | doi = 10.1145/200979.201042|s2cid=14934919 | doi-access = free }}</ref> [[Lehmer's GCD algorithm]] uses the same general principle as the binary algorithm to speed up GCD computations in arbitrary bases. | ||
A recursive approach for very large integers (with more than 25,000 digits) leads to [[quasilinear time|quasilinear]] integer GCD algorithms,<ref>{{cite book | last1 = Aho | first1 = A. | author1-link = Alfred Aho | last2 = Hopcroft | first2 = J. | author2-link = John Hopcroft | last3 = Ullman | first3 = J. | author3-link = Jeffrey Ullman | year = 1974 | title = The Design and Analysis of Computer Algorithms | publisher = Addison–Wesley | location = New York | pages = [https://archive.org/details/designanalysisof00ahoarich/page/300 300–310] | isbn = 0-201-00029-6 | url = https://archive.org/details/designanalysisof00ahoarich/page/300 }}</ref> such as those of Schönhage,<ref>{{cite journal | last = Schönhage|first= A. |author-link=Arnold Schönhage| title = Schnelle Berechnung von Kettenbruchentwicklungen |language=de | journal = Acta Informatica | volume = 1 | pages = 139–144 | doi = 10.1007/BF00289520 | year = 1971 | issue = 2|s2cid= 34561609 }}</ref><ref>{{cite book | last = Cesari|first= G. | year = 1998 | chapter = Parallel implementation of Schönhage's integer GCD algorithm | title = Algorithmic Number Theory: Proc. ANTS-III, Portland, OR | editor = G. Buhler | publisher = Springer-Verlag | location = New York | pages = 64–76|volume=1423|series=Lecture Notes in Computer Science}}</ref> and Stehlé and Zimmermann.<ref>{{cite book | last1 = Stehlé|first1=D.|last2=Zimmermann|first2=P. | year = 2005 | chapter = [[Gal's accurate tables]] method revisited | title = Proceedings of the 17th IEEE Symposium on Computer Arithmetic (ARITH-17) | publisher = [[IEEE Computer Society Press]] | location = Los Alamitos, CA}}</ref> These algorithms exploit the 2×2 matrix form of the Euclidean algorithm given [[#Matrix method|above]]. These quasilinear methods generally scale as {{math|''O''(''h'' log ''h''{{sup|2}} log log ''h'').}}<ref name="Crandall_2001" /><ref name="Moller08">{{cite journal | last = Möller|first= N. | title = On Schönhage's algorithm and subquadratic integer gcd computation | journal = Mathematics of Computation | volume = 77 | pages = 589–607 | doi = 10.1090/S0025-5718-07-02017-0 | year = 2008 | url=http://www.lysator.liu.se/~nisse/archive/sgcd.pdf | issue = 261| bibcode = 2008MaCom..77..589M | doi-access = free }}</ref> | A recursive approach for very large integers (with more than 25,000 digits) leads to [[quasilinear time|quasilinear]] integer GCD algorithms,<ref>{{cite book | last1 = Aho | first1 = A. | author1-link = Alfred Aho | last2 = Hopcroft | first2 = J. | author2-link = John Hopcroft | last3 = Ullman | first3 = J. | author3-link = Jeffrey Ullman | year = 1974 | title = The Design and Analysis of Computer Algorithms | publisher = Addison–Wesley | location = New York | pages = [https://archive.org/details/designanalysisof00ahoarich/page/300 300–310] | isbn = 0-201-00029-6 | url = https://archive.org/details/designanalysisof00ahoarich/page/300 }}</ref> such as those of Schönhage,<ref>{{cite journal | last = Schönhage|first= A. |author-link=Arnold Schönhage| title = Schnelle Berechnung von Kettenbruchentwicklungen |language=de | journal = Acta Informatica | volume = 1 | pages = 139–144 | doi = 10.1007/BF00289520 | year = 1971 | issue = 2|s2cid= 34561609 }}</ref><ref>{{cite book | last = Cesari|first= G. | year = 1998 | chapter = Parallel implementation of Schönhage's integer GCD algorithm | title = Algorithmic Number Theory: Proc. ANTS-III, Portland, OR | editor = G. Buhler | publisher = Springer-Verlag | location = New York | pages = 64–76|volume=1423|series=Lecture Notes in Computer Science}}</ref> and Stehlé and Zimmermann.<ref>{{cite book | last1 = Stehlé|first1=D.|last2=Zimmermann|first2=P. | year = 2005 | chapter = [[Gal's accurate tables]] method revisited | title = Proceedings of the 17th IEEE Symposium on Computer Arithmetic (ARITH-17) | publisher = [[IEEE Computer Society Press]] | location = Los Alamitos, CA}}</ref> These algorithms exploit the 2×2 matrix form of the Euclidean algorithm given [[#Matrix method|above]]. These quasilinear methods generally scale as {{math|''O''(''h'' log ''h''{{sup|2}} log log ''h'').}}<ref name="Crandall_2001" /><ref name="Moller08">{{cite journal | last = Möller | first = N. | title = On Schönhage's algorithm and subquadratic integer gcd computation | journal = Mathematics of Computation | volume = 77 | pages = 589–607 | doi = 10.1090/S0025-5718-07-02017-0 | year = 2008 | url = http://www.lysator.liu.se/~nisse/archive/sgcd.pdf | issue = 261 | bibcode = 2008MaCom..77..589M | doi-access = free | archive-date = 2010-08-21 | access-date = 2009-03-24 | archive-url = https://web.archive.org/web/20100821073716/http://www.lysator.liu.se/~nisse/archive/sgcd.pdf | url-status = live }}</ref> | ||
== Generalizations == | == Generalizations == | ||
| Line 638: | Line 642: | ||
* [[Euclidean rhythm]], a method for using the Euclidean algorithm to generate musical rhythms | * [[Euclidean rhythm]], a method for using the Euclidean algorithm to generate musical rhythms | ||
* [[Jacobi–Perron algorithm]], a generalization to ''n'' dimensions | |||
{{clear}} | {{clear}} | ||
| Line 683: | Line 688: | ||
* [http://www.mathpages.com/home/kmath384.htm The Euclidean Algorithm] at MathPages | * [http://www.mathpages.com/home/kmath384.htm The Euclidean Algorithm] at MathPages | ||
* [http://www.cut-the-knot.org/blue/EuclidAlg.shtml Euclid's Game] at [[cut-the-knot]] | * [http://www.cut-the-knot.org/blue/EuclidAlg.shtml Euclid's Game] at [[cut-the-knot]] | ||
* [http://plus.maths.org/issue40/features/wardhaugh/index.html Music and Euclid's algorithm] | * [http://plus.maths.org/issue40/features/wardhaugh/index.html Music and Euclid's algorithm] {{Webarchive|url=https://web.archive.org/web/20070809225041/http://www.plus.maths.org/issue40/features/wardhaugh/index.html |date=2007-08-09 }} | ||
{{Number theoretic algorithms}} | {{Number theoretic algorithms}} | ||