The **binary GCD algorithm**, also known as **Stein's algorithm**, is an algorithm that computes the greatest common divisor of two nonnegative integers. It gains a measure of efficiency over the ancient Euclidean algorithm by replacing divisions and multiplications with shifts, which are cheaper when operating on the binary representation used by modern computers. This is particularly critical on embedded platforms that have no direct processor support for division. Although the algorithm was first published by the Israeli physicist and programmer Josef Stein in 1967, it may have been known in 1st-century China.

Read more about Binary GCD Algorithm: Algorithm, Efficiency, Historical Description

### Other articles related to "binary gcd algorithm, algorithm, gcd":

**Binary GCD Algorithm**- Historical Description

... An

**algorithm**for computing the

**GCD**of two numbers was described in the ancient Chinese mathematics book The Nine Chapters on the Mathematical Art ... The original

**algorithm**was used to reduce a fraction ... The description reads This just looks like a normal Euclidian

**algorithm**, but the ambiguity lies in the phrase "if possible halve it" ...

Main Site Subjects

Related Phrases

Related Words