Description
The simplest form of Euclid's algorithm starts with a pair of positive integers and forms a new pair that consists of the smaller number and the difference between the larger and smaller numbers. The process repeats until the numbers are equal; then that value is the greatest common divisor of the original pair. However if one number is much smaller than the other, many subtraction steps will be needed before the larger number is reduced to a value less than or equal to the other number in the pair.
Subtracting a small positive number from a big number enough times until what is left is less than the original smaller number can be replaced by finding the remainder in long division. Thus the division form of Euclid's algorithm starts with a pair of positive integers and forms a new pair that consists of the smaller number and the remainder obtained by dividing the larger number by the smaller number. The process repeats until one number is zero. The other number then is the greatest common divisor of the original pair.
Read more about this topic: Euclidean Algorithm
Famous quotes containing the word description:
“To give an accurate description of what has never occurred is not merely the proper occupation of the historian, but the inalienable privilege of any man of parts and culture.”
—Oscar Wilde (1854–1900)
“An intentional object is given by a word or a phrase which gives a description under which.”
—Gertrude Elizabeth Margaret Anscombe (b. 1919)
“I fancy it must be the quantity of animal food eaten by the English which renders their character insusceptible of civilisation. I suspect it is in their kitchens and not in their churches that their reformation must be worked, and that Missionaries of that description from [France] would avail more than those who should endeavor to tame them by precepts of religion or philosophy.”
—Thomas Jefferson (1743–1826)