E1. {Find Remainder}. Divide m by n and let r be the (new) remainder {r have 0≤r<n}
E2. {Is r zero?} If r = 0, the algorithm terminates and n is the answer. Otherwise,
E3. {Interchange}. Let the new value of m be the current value of n and the new value of n be the current value of r. Go back to Step E1.
The termination of the above method is guaranteed, as m and n must reduce in each iteration and r must become zero in finite number of repetitions of steps E1, E2 and E3.
The great Greek mathematician Euclid sometimes between fourth and third century BC, at least knew and may be the first to suggest, the above algorithm. The algorithm is considered as among the first non-trivial algorithms. However, the word ‘algorithm’ itself came into usage quite late. The word is derived from the name of the Persian mathematician Mohammed al-Khwarizmi who lived during the ninth century A.D. The word ‘al-khowarizmi’ when written in Latin became ‘Algorismus’, from which ‘algorithm’ is a small step away.
In order to familiarise ourselves with the notation usually used to express algorithms, next, we express the Euclid’s Algorithm in a pseudo-code notation which is closer to a programming language.
Algorithm GCD-Euclid (m, n)
E2. {Is r zero?} If r = 0, the algorithm terminates and n is the answer. Otherwise,
E3. {Interchange}. Let the new value of m be the current value of n and the new value of n be the current value of r. Go back to Step E1.
The termination of the above method is guaranteed, as m and n must reduce in each iteration and r must become zero in finite number of repetitions of steps E1, E2 and E3.
The great Greek mathematician Euclid sometimes between fourth and third century BC, at least knew and may be the first to suggest, the above algorithm. The algorithm is considered as among the first non-trivial algorithms. However, the word ‘algorithm’ itself came into usage quite late. The word is derived from the name of the Persian mathematician Mohammed al-Khwarizmi who lived during the ninth century A.D. The word ‘al-khowarizmi’ when written in Latin became ‘Algorismus’, from which ‘algorithm’ is a small step away.
In order to familiarise ourselves with the notation usually used to express algorithms, next, we express the Euclid’s Algorithm in a pseudo-code notation which is closer to a programming language.
Algorithm GCD-Euclid (m, n)
{This algorithm computes the greatest common divisor of two given positive integers}
begin {of algorithm}
while n ≠ 0 do
begin {of while loop}
r ← m mod n;
{a new variable is used to store the remainder which is obtained by dividing m by n, with 0≤ r < m}
m ←n;
{the value of n is assigned as new value of m; but at this stage value of n remains unchanged}
n← r;
{the value of r becomes the new value of n and the value of r remains unchanged}
end {of while loop}
return (n).
end; {of algorithm}
0 comments:
Post a Comment