Binary GCD Algorithm - Historical Description

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:

"If possible halve it; otherwise, take the denominator and the numerator, subtract the lesser from the greater, and do that alternately to make them the same. Reduce by the same number."

This just looks like a normal Euclidian algorithm, but the ambiguity lies in the phrase "if possible halve it". The traditional interpretation is that this only works when 'both' numbers to begin with are even, under which the algorithm is just a slightly inferior Euclidean algorithm (for using subtraction instead of division). But the phrase may as well mean dividing by 2 should 'either' of the numbers become even, in which case it is the binary GCD algorithm.

Read more about this topic:  Binary GCD Algorithm

Other articles related to "historical description":

Guldize - Historical Description
... A number of customs also were associated with the feast, a man would have been chosen to rush to the site of the feast with the corn neck and enter the building by stealth avoiding an appointed lady who would have soaked the carrier of the neck if discovered ... If this game was successful then the carrier of the neck would have been entitled to take a kiss from female "guard" of the property ...

Famous quotes containing the words description and/or historical:

    God damnit, why must all those journalists be such sticklers for detail? Why, they’d hold you to an accurate description of the first time you ever made love, expecting you to remember the color of the room and the shape of the windows.
    Lyndon Baines Johnson (1908–1973)

    By contrast with history, evolution is an unconscious process. Another, and perhaps a better way of putting it would be to say that evolution is a natural process, history a human one.... Insofar as we treat man as a part of nature—for instance in a biological survey of evolution—we are precisely not treating him as a historical being. As a historically developing being, he is set over against nature, both as a knower and as a doer.
    Owen Barfield (b. 1898)