Programming Algorithm Algorithm - a well-defined Successive Steps | Explaining Euclid's...

# Algorithm – a well-defined Successive Steps | Explaining Euclid’s Algorithm

-

By 1950 the word Algorithm was most frequently associated with Euclid’s algorithm, a process for finding GCD of two numbers. here we will discuss it to understand the successive steps of an Algorithm.

(Euclid’s Algorithm): Given two positive integers $m$ and $n$, find their Greatest Common Divisor (GCD). GCD is the largest positive integer that evenly divide both $m$ and $n$.[mathjax]

## Algorithm – successive steps

Step 1: [Find remainder] – Divide $m$ by $n$ and let $r$ be the remainder. (Here, $0≤r<n$).
Step 2: [Is it zero?] – If $r=0$, the algorithm terminates. $n$ is the answer.
Step 3: [Reduce] – set $m←n$, $n←r$, and go back to Step 1.╻

## Explaining Euclid’s Algorithm

Each step of an Algorithm, begins with a phrase in brackets that sum up as briefly as possible the principal content of that step. This phrase also usually appears in an accompanying flow chart. • After the summarizing-phrase, comes a description in words and symbols of some action to be performed or some decision to make. Parenthesized-comment like in the Step 1 may also appear. Comments include the explanatory information about the step.
• The arrow $”←”$ in Step 3, is the most important replacement operation. Also known as assignment or substitution. “m←n” means that the current value of $n$ will replace the value of variable $m$.
• We will not say, “set m=n”, rather we will ask, “does m=n?”. The “=” sign denotes a condition, and the “←” sign denotes an action. $”n←n+1″$ (read “n gets n+1”) denotes the operation of ‘increasing $n$ by $1$’.
• Notice that the order of actions in Step 3 is important. “Set $m←n, n ←r$” is quite different from “Set $n←r, m←n$”. When several variables are all set equal to the same quantity, $”n←r, m ←r”$, is similar to $”n←m←r”$. To interchange the value of two variable, we write “Exchange $m↔n$”. “Set $t←m, m←n, n←t$” can also specify the same action, when $t$ is a new variable.
• An algorithm starts with the lowest-numbered step, usually step 1, subsequent steps follow the sequential order.  -unless otherwise specified. In Step 3, “Go back to Step 1” specifies the computational order in an obvious fashion.
• In Step 2, the condition”If $r=0$” preface the action, so, if $r≠0$, then rest of the sentence does not apply and no action is specified. We might have added the redundant sentence, “If $r≠0$, go on to the Step 3.”
• The Heavy vertical line “Ι” appears at the end of Step 3, which indicates the end of algorithm and the resumption of the text.

### Example

Lets work out an example on euclid’s Algorithm. Consider $m=119$ and $n=544$. Beginning with step 1, dividing $m$ by $n$, gives the quotient equals to zero, and the remainder is $119$. -Which means $544$ divide $119$, $0$ times, and $119$ remains, in case of finding Remainder. -But in Decimal Division, it has a different scenario. Thus, $r←119.$ We proceed to step 2, and since $r≠0,$ no action occurs. In step 3, we set $m←544, \text{ }n←119.$ It is clear that, if $m<n,$ the quotient in step 1 is always will always be zero, therefore, algorithm always proceed to interchange $m$ and $n$ in this rather cumbersome fashion. I this case, we could add a new step:

Step 0: [ensure m ≥n.] If $m<n$, exchange $m↔n.$

This would make no essential change in the algorithm, except to increase its length slightly. Back at step 1, we find that $\frac{544}{119}=4\frac{68}{119},$ so, remainder $r=68.$ Again, step 2 is inapplicable, and at step 3, we set $m←119,\text{ }n←68.$ The next round sets $r←51,$ and ultimately, $m←68,\text{ }n←51.$ Next, $r←17,$ and $m←51,\text{ }n←17.$ Finally, when $51$ is divided by $17,$ we set reminder, $r←0$, so at step 2 the algorithm terminates. The greatest common divisor (gcd) of $119, \text{ and }544$ is $17.$

This is the end of discussion on “Euclid’s Algo”, and the well-defined successive steps to an Algorithm. This topic I chose from the book “The Art of Computer programming”, by Donald E. Knuth. – Which I think, is a great book to study Computer Programming.

### Property Decorator | Getters Setters and Deleters in Python

In this article, we will talk about the Property Decorator in Python. It enables the class functionality...

### Dictionaries | HashMap in Python | Working with Key-Values

Dictionaries in Python is similar to Hashmap comparing to other languages. It stores data as a key-value...

### Hash Table | Indexing | Hashing Algorithm | Python Implementation

This article will talk about a high-level view of the Hash Table. As a programmer, this technique...

### Eigenvector Eigenvalue | Linear Algebra Fundamentals

Eigenvector ($bar{v}$) in linear algebra is a non-zero vector (matrix) that doesn't change its direction during linear...

### Pivot Table | Microsoft Excel | Create Data Insight Easily

Pivot table in microsoft Excel is an useful function that gives us a way to create insight...

### Macro Function in Microsoft Excel | Automate Repetitive Task

This article we will talk about the Macro. It is a function in microsoft excel which basically...