Binary GCD Algorithm

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 AlgorithmAlgorithm, 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" ...