Data Structure And Algorithms In Python - Euclidean algorithm — 3

In previous two blogs, we were working on normal GCD (Greatest Common Divisor) programs.

We Followed below mentioned steps mainly.

1. To find the largest common factor, start at the end and work backwards
2. Running i from min(m,n) to 1.
3. First common factor that we find will be GCD!

If you haven’t checked these blogs, please do check the same. Below are links for both of them.
→ Data Structure And Algorithms — 2
→ Data Structure and Architecture-1

Lets cover Euclidean Algorithm for GCD today

First lets understand what is Euclidean.

Definition of Euclidean : of, relating to, or based on the geometry of Euclid or a geometry with similar axioms

Euclidean geometry was given by Greek mathematician Euclid. It is the study of plane and solid figures on the basis of axioms and theorems.

Euclid

Lets discuss about Euclidean distance and Manhattan distance as well.

Manhattan distance between two points is the length of the shortest path that connects them, measured in city blocks.

Euclidean distance is defined as the distance between two points

Seems like both are same thing, but here is the key difference.

Lets assume you are in Bengaluru and travelling to your relative's home. You take out your car and start driving towards your destination and take turn according to the map and road. This is called Manhattan distance.

Lets assume again, you hire a chopper to reach to you relative’s place. You don't need to take any turn, and you will reach your destination directly. This is called Euclidean distance.

Euclidean vs Manhattan Distance

In above example, Green line denotes Euclidean distance and Blue line donates Manhattan distance.

Euclidean distance is calculated in each of the distance tools. Conceptually, the Euclidean algorithm works as follows:
→ For each cell, the distance to each source cell is determined by calculating the hypotenuse with x_max and y_max as the other two legs of the triangle.

Now, Lets understand, what is Euclidean algorithm?

Euclidean algorithm, or Euclid’s algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder.

The most common use of the Euclidean algorithm is for finding modular inverses. There is a simple tweak of it that allows you, given two integers a, N, to calculate integers x, y such that ax + yN = gcd(a, N) — this is known as the extended Euclidean algorithm.

There are numerous algorithms to find GCD of two numbers. However, in most of them, the execution time will be the same since the algorithm will run checking all numbers one by one between 1 and the smallest number.

In Euclidean algorithm, the execution time will the minimum since the algorithm will shrink the 2 numbers and give the correct output.

Euclid’s algorithm steps: —

1. Suppose d divides both m and n, and m > n
2. Then m = ad, n = bd
3. m-n = ad — bd = (a-b)d
4. d divides m-n
5. gcd(m,n) = gcd(n,m-n)
6. Consider, gcd(m,n) with m > n
7. If n divides m, return n
8. Else, compute gcd(n,m-n) and return that value

First Algo

Another way of Algo

Algo Optimization:

1. Suppose n does not divide m
2. m = qn + r,
   where q is the quotient, r is the remainder when we divide m by n!
3. Assume d divides both m and n.
4. m = ad, n = bd
5. So ad = q(bd) + r
6. It follows that r = cd, so d divides r as well
7. Consider gcd(m,n) with m > n
8. If n divides m, return n
9. Otherwise, let r = m%n
10. Return gcd(n,r)

Thank you for reading. Links to other blogs: —

Data Structure And Algorithms — 2
Data Structure and Architecture-1
Hessian Matrix
First order and Second order — Calculus
Statistical Inference 2 — Hypothesis Testing
Statistical Inference
Central Limit Theorem — Statistics