Master Euclid's GCD Algorithm with Clear Visuals 📊

I am a Professor in the Computer Science department at the University of Cambridge. Through this channel I welcome anyone in the world to attend my lectures. This video is an optional extra and it is not included in the official playlist of the lectures for this course.

Euclid's Algorithm for computing the Greatest Common Divisor of two integers is one of the oldest documented non-trivial algorithms in the literature, dating back to ~300 BC.

We explain it using a geometric interpretation: if the two integers are the sides of a rectangle, the GCD is the side of the largest square tile that may be used to tile the rectangle completely, without leftovers.

Many thanks to those of you who are giving thumbs up to these videos and subscribing to the channel. Your support is greatly appreciated and it causes Youtube to offer this material to more viewers who might like it.


Course web page:
https://www.cl.cam.ac.uk/teaching/current/Algorithms/

Course handout:
https://www.cl.cam.ac.uk/teaching/2022/Algorithms/2021-2022-stajano-algs-handout.pdf

My home page:
http://frank.stajano.com