Binary GCD algorithm

The binary GCD algorithm, also known as Stein's algorithm or the binary Euclidean algorithm, computes the greatest common divisor of two nonnegative integers. Where the classical Euclidean algorithm relies on division, this method uses only arithmetic shifts, comparisons and subtraction, which are simpler operations on a computer. It works by repeatedly applying a few identities, such as removing common factors of two and replacing a pair of odd numbers by the smaller one and their difference. The physicist and programmer Josef Stein published its contemporary form in 1967, but a version of the idea was already known in ancient China by the second century BCE. Practical implementations count trailing zero bits and avoid branches so the loop runs fast.