Euclid's algorithm is widely used in practice, especially for small numbers, due to its simplicity. An alternative algorithm, the [[binary GCD algorithm]], exploits the [[binary numeral system|binary]] representation used by computers to avoid divisions and thereby increase efficiency, although it too is ''O''(''n''²); it merely shrinks the constant hidden by the [[big-O notation]] on many real machines.
== Relation with continued fractions ==
The quotients that appear when the Euclidean algorithm is applied to the inputs ''a'' and ''b'' are precisely the numbers occurring in the [[continued fraction]] representation of ''a''/''b''.
Take for instance the example of ''a'' = 1071 and ''b'' = 1029 used above.
Here is the calculation with highlighted quotients:
This method can even be used for [[real number|real]] inputs ''a'' and ''b''; if ''a''/''b'' is [[irrational number|irrational]], then the Euclidean algorithm will not terminate, but the computed sequence of quotients still represents the (now infinite) continued fraction representation of ''a''/''b''.
