Efficiency of Alternative Methods
Euclid's algorithm is widely used in practice, especially for small numbers, due to its simplicity. 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 above, the GCD equals the product of the prime factors shared by the two numbers a and b. Present methods for prime factorization are also inefficient; many modern cryptography systems even rely on that inefficiency.
The binary GCD algorithm is an efficient alternative that substitutes division with faster operations by exploiting the binary representation used by computers. However, this alternative also scales like O(h²). It is generally faster than the Euclidean algorithm on real computers, even though it scales in the same way. Additional efficiency can be gleaned by examining only the leading digits of the two numbers a and b. The binary algorithm can be extended to other bases (k-ary algorithms), with up to fivefold increases in speed.
A recursive approach for very large integers (with more than 25,000 digits) leads to subquadratic integer GCD algorithms, such as those of Schönhage, and Stehlé and Zimmermann. These algorithms exploit the 2×2 matrix form of the Euclidean algorithm given above. These subquadratic methods generally scale as O(h (log h)2 (log log h)).
Read more about this topic: Euclidean Algorithm, Algorithmic Efficiency
Famous quotes containing the words efficiency, alternative and/or methods:
“Ill take fifty percent efficiency to get one hundred percent loyalty.”
—Samuel Goldwyn (18821974)
“If you have abandoned one faith, do not abandon all faith. There is always an alternative to the faith we lose. Or is it the same faith under another mask?”
—Graham Greene (19041991)
“With a generous endowment of motherhood provided by legislation, with all laws against voluntary motherhood and education in its methods repealed, with the feminist ideal of education accepted in home and school, and with all special barriers removed in every field of human activity, there is no reason why woman should not become almost a human thing. It will be time enough then to consider whether she has a soul.”
—Crystal Eastman (18811928)