Editing Binary GCD algorithm (section)

{{Short description|Algorithm for computing the greatest common divisor}}
{{Use dmy dates|date=April 2022}}
[[File:binary_GCD_algorithm_visualisation.svg|thumb|upright=1.8|Visualisation of using the binary GCD algorithm to find the greatest common divisor (GCD) of 36 and 24.  Thus, the GCD is 2<sup>2</sup> × 3 = 12.]]

The '''binary GCD algorithm''', also known as '''Stein's algorithm''' or the '''binary Euclidean algorithm''',{{r|brenta|brentb}} is an algorithm that computes the [[greatest common divisor]] (GCD) of two nonnegative integers. Stein's algorithm uses simpler arithmetic operations than the conventional [[Euclidean algorithm]]; it replaces division with [[arithmetic shift]]s, comparisons, and subtraction.

Although the algorithm in its contemporary form was first published by the physicist and programmer Josef Stein in 1967,<ref name="Stein"/> it was known by the 2nd century BCE, in ancient China.{{r|Knuth98}}