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.

algorithm step by step

  • 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.

Latest Articles

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...

Must read

Dictionaries | HashMap in Python | Working with Key-Values

Dictionaries in Python is similar to Hashmap...

You might also likeRELATED
Recommended to you