In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems. Algorithms can perform calculation, data processing and automated reasoning tasks.
A graphical expression of Euclid’s algorithm to find the greatest common divisor for 1599 and 650.
1599 = 650×2 + 299 650 = 299×2 + 52 299 = 52×5 + 39 52 = 39×1 + 13 39 = 13×3 + 0
An algorithm is an effective method that can be expressed within a finite amount of space and time and in a well-defined formal language for calculating a function. Starting from an initial state and initial input (perhaps empty), the instructions describe a computation that, when executed, proceeds through a finite number of well-defined successive states, eventually producing “output” and terminating at a final ending state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as randomized algorithms, incorporate random input.
What is Euclid ‘s Algorithm ?
Euclid ‘s algorithm to compute the greatest common divisor (GCD) to two numbers appears as Proposition II in Book VII (“Elementary Number Theory”) of his Elements. Euclid poses the problem thus: “Given two numbers not prime to one another, to find their greatest common measure”. He defines “A number [to be] a multitude composed of units”: a counting number, a positive integer not including zero. To “measure” is to place a shorter measuring length s successively (q times) along longer length l until the remaining portion r is less than the shorter length s.
How to solve Euclid ‘s Algorithm ?