#MathsInMinutes Day 14: Euclids Algorithm
Day 14: Euclid´s algorithm
● An algorithm is a method, or recipe, for solving a problem by following a set of rules.
● Euclid´s algorithm is an early example, formulated around 300BC. It is designed to find the greatest common divisor, GCD, of two numbers.
● Algorithms are fundamental to computer science, and most electronic devices use them to produce useful output.
● The simplest version of Euclid´s algorithm uses the fact that the GCD of two numbers is the same as the GCD of the smaller number and the difference between them.
● This allows us to repeatedly remove the larger number in the pair, reducing the size of the numbers involved until one vanishes. The last non-zero number is then the GCD of the original pair.
● This method can take many repetitions to reach the answer.
● A more efficient method, the standard algorithm, replaces the larger number by the remainder obtained when dividing it by the smaller number, until there is no remainder.
---------------------------------------------------------------------------------------------------------
I hope you enjoyed!
If you liked this content consider buying the original book:
http://a.co/72sJoVV
If you want to be notified about a new blog entry in this series, please leave a short message below along the lines of "i am interested" so I can write your handle down and @ you in the next entry.