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
Famous quotes containing the words historical and/or description:
“This seems a long while ago, and yet it happened since Milton wrote his Paradise Lost. But its antiquity is not the less great for that, for we do not regulate our historical time by the English standard, nor did the English by the Roman, nor the Roman by the Greek.... From this September afternoon, and from between these now cultivated shores, those times seemed more remote than the dark ages.”
—Henry David Thoreau (1817–1862)
“The great object in life is Sensation—to feel that we exist, even though in pain; it is this “craving void” which drives us to gaming, to battle, to travel, to intemperate but keenly felt pursuits of every description whose principal attraction is the agitation inseparable from their accomplishment.”
—George Gordon Noel Byron (1788–1824)