Euclidean Algorithm meaning & python snippet
Tags: machinelearning, python, algorithms
Published: 2021-05-13 16:24:41

This algorithm helps us get the greatest common divisor(gcd) of 2 integers. In other words, the result of our computation is the highest possible number `(lets say 1)` that we can divide by two given numbers `(4 and 5)` which will give a remainder `(or you could say left over after a division)` of zero for both given numbers. Lets break this down a little bit :
our two numbers earlier were `4` and `5`, but these could be any random numbers which follow two rules :
1st >> one number must be larger than the other.
2nd >> both must not be even numbers.
The euclidian algorithm formula is `q = a * b + r` where the letters are placeholders for numbers forexample
```
5 = 4 * 1 + 1 or
11 = 2 * 5 + 1
```
Lets get our hands a little dirty and see how we arrived to the answers of 5 and 11 above:
`now is the time to open your editor and create a python file so we can write some simple code. my file is called index.py`
When calculating we always have our 2 numbers, remember earlier we chose `(4 and 5)`. These numbers replace `q` and `a` whereby `q` takes the bigger number `(5)` and `a` the smaller `(4)` so `5 = 4 * b + r` therefore in `index.py`
```
# formula is q = a * b + r
q = 5
a = 4
```
our task is to find numbers to replace `b` and `r` to complete our equation. according to the Euclidian theorem, `b` is the number of times `a` goes into (divides) `q` while `r` is the remainder of that operation.
so `5` goes into `4` once with a remainder of `1` so we will equate our remainder to `r` and our initial answer to b. In python we could use an inbuilt function called `divmod( )` to do this computation and it takes the two numbers as arguments and returns a quotient and remainder as the result in an array therefore in `index.py`
```
# formula is q = a * b + r
q = 5
a = 4
result = divmod(q,a)
b = result[0]
r = result[1]
```
However according to the Euclidian theorem, our remainder must be zero so if `r` isn't `0` we aren't done. It states that we have to place `a` in the position of `q` and `r` in the position of `a` or simply replace our initial values that were used in the calculation by new values following the above procedure therefore in `index.py`
```
# formula is q = a * b + r
q = 5
a = 4
result = divmod(q,a)
b = result[0]
r = result[1]
q = a
a = r
```
Take a scenario where you didn't use `(4 and 5)` , probably (11 and 5). You will have to repeat the calculations until `r = 0`. When `r = 0` , we obtain the gcd from the value of r just exactly before you did the last calculation to obtain `r = 0` for us to get the desired final result therefore in `index.py` we can use a for loop to do our calculations over and over until `r = 0` :
```
# formula is q = a * b + r
q = 5
a = 4
result = divmod(q,a)
b = result[0]
r = result[1]
q = a
a = r
finalResult = 0 #initialize a variable outside the for loop so 
                #that it is accessed globally
for i in range(q):
  finalResult = r #store our gcd value as the loop is starting so 
                  #that we can capture the previous value of r 
                  #before the calculation which equates `r = 0`
  result = divmod(q,a)
  b = result[0]
  r = result[1]
  if r == 0:
    break #constantly check the current value in r and make sure 
          #when it is 0 you can stop the loop
  q = a
  a = r
print(finalresult)
```

And that's it folks, Enjoy
Find me on [twitter](https://twitter.com/CoucoSeth)