Editing Euclidean algorithm (section)

=== Alternative methods ===
Euclid's algorithm is widely used in practice, especially for small numbers, due to its simplicity.<ref>
{{cite book
 | last = Sorenson | first = Jonathan P.
 | contribution = An analysis of the generalized binary GCD algorithm
 | mr = 2076257
 | pages = 327–340
 | publisher = American Mathematical Society | location = Providence, RI
 | series = Fields Institute Communications
 | title = High primes and misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams
 | volume = 41
 | year = 2004
 | url = https://books.google.com/books?id=udr3tHHwBl0C&pg=PA327
 | quote = The algorithms that are used the most in practice today [for computing greatest common divisors] are probably the binary algorithm and Euclid's algorithm for smaller numbers, and either Lehmer's algorithm or Lebealean's version of the ''k''-ary GCD algorithm for larger numbers.
 | isbn = 9780821887592
}}</ref> For comparison, the efficiency of alternatives to Euclid's algorithm may be determined.

One inefficient approach to finding the GCD of two natural numbers ''a'' and ''b'' is to calculate all their common divisors; the GCD is then the largest common divisor. The common divisors can be found by dividing both numbers by successive integers from 2 to the smaller number ''b''. The number of steps of this approach grows linearly with ''b'', or exponentially in the number of digits. Another inefficient approach is to find the prime factors of one or both numbers. As noted [[#Greatest common divisor|above]], the GCD equals the product of the prime factors shared by the two numbers ''a'' and ''b''.<ref name="Schroeder_21" /> Present methods for [[integer factorization|prime factorization]] are also inefficient; many modern cryptography systems even rely on that inefficiency.<ref name="Schroeder_216" />

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>