Computer science is (almost by definition) a science about computers -- a device first conceptualized in the 1800's. Computers have become so revolutionary, that it is difficult to think of our lives today without them. That said, algorithms are much older and have existed in the world for millennia. Incredibly, a few of the algorithms created before the Common Era (AD) are still in use today. One such algorithm was first described in Euclid's Elements (~ 300 BC) and has come to be known as the Euclidean Algorithm.
The algorithm is a simple way to find the greatest common divisor (GCD) of two numbers, which is useful for a number of different applications (like reducing fractions). The first method (envisioned by Euclid) uses simple subtraction:
{% method %} {% sample lang="vim" %} import:14-27, lang="vim" {% sample lang="c" %} import:17-30, lang="c_cpp" {% sample lang="cs" %} import:8-23, lang="csharp" {% sample lang="clj" %} import:2-8, lang="clojure" {% sample lang="cpp" %} import:18-31, lang="c_cpp" {% sample lang="java" %} import:3-16, lang="java" {% sample lang="kotlin" %} import:3-13, lang="kotlin" {% sample lang="js" %} import:15-29, lang="javascript" {% sample lang="lisp" %} import:3-12, lang="lisp" {% sample lang="py" %} import:11-27, lang="python" {% sample lang="hs" %} import:3-13, lang="haskell" {% sample lang="rs" %} import:3-15, lang="rust" {% sample lang="ml" %} import:9-17, lang="ocaml" {% sample lang="go" %} import:25-38, lang="go" {% sample lang="swift" %} import:1-14, lang="swift" {% sample lang="m" %} import:3-17, lang="matlab" {% sample lang="lua" %} import:1-14, lang="lua" {% sample lang="jl" %} import:12-25, lang="julia" {% sample lang="nim" %} import:13-24, lang="nim" {% sample lang="asm-x64" %} import:35-56, lang="asm-x64" {% sample lang="f90" %} import:1-19, lang="fortran" {% sample lang="php" %} import:4-18, lang="php" {% sample lang="factor" %} import:1-13, lang="factor" {% sample lang="ws" %} import, lang="whitespace" {% sample lang="scala" %} import:3-8, lang="scala" {% sample lang="racket" %} import:3-14, lang="racket" {% sample lang="ruby" %} import:8-19, lang="ruby" {% sample lang="st" %} import:1-13, lang="smalltalk" {% sample lang="emojic" %} import:2-17, lang:"emojicode" {% sample lang="lolcode" %} import:25-40, lang="LOLCODE" {% sample lang="bash" %} import:24-38, lang="bash" {% sample lang="d" %} import:19-33, lang="d" {% sample lang="piet" %}
{% sample lang="ss" %} import:1-7, lang="scheme" {% sample lang="scratch" %}
{% sample lang="ps1" %} import:1-14, lang="powershell" {% sample lang="coco" %} import:1-9, lang="coconut"
{% endmethod %}
Here, we simply line the two numbers up every step and subtract the lower value from the higher one every timestep. Once the two values are equal, we call that value the greatest common divisor. A graph of a and b as they change every step would look something like this:
Modern implementations, though, often use the modulus operator (%) like so
{% method %} {% sample lang="vim" %} import:1-12, lang="vim" {% sample lang="c" %} import:4-16, lang="c_cpp" {% sample lang="cs" %} import:25-39, lang="csharp" {% sample lang="clj" %} import:9-13, lang="clojure" {% sample lang="cpp" %} import:5-15, lang="c_cpp" {% sample lang="java" %} import:18-26, lang="java" {% sample lang="kotlin" %} import:15-26, lang="kotlin" {% sample lang="js" %} import:1-13, lang="javascript" {% sample lang="lisp" %} import:14-18, lang="lisp" {% sample lang="py" %} import:1-9, lang="python" {% sample lang="hs" %} import:18-25, lang="haskell" {% sample lang="rs" %} import:17-27, lang="rust" {% sample lang="ml" %} import:3-7, lang="ocaml" {% sample lang="go" %} import:14-23, lang="go" {% sample lang="swift" %} import:16-27, lang="swift" {% sample lang="m" %} import:19-31, lang="matlab" {% sample lang="lua" %} import:16-25, lang="lua" {% sample lang="jl" %} import:1-10, lang="julia" {% sample lang="nim" %} import:1-11, lang="nim" {% sample lang="asm-x64" %} import:10-33, lang="asm-x64" {% sample lang="f90" %} import:21-34, lang="fortran" {% sample lang="php" %} import:20-30, lang="php" {% sample lang="factor" %} import:15-25, lang="factor" {% sample lang="ws" %} import, lang="whitespace" {% sample lang="scala" %} import:10-14, lang="scala" {% sample lang="racket" %} import:16-24, lang="racket" {% sample lang="ruby" %} import:1-6, lang="ruby" {% sample lang="st" %} import:15-25, lang="smalltalk" {% sample lang="emojic" %} import:19-31, lang:"emojicode" {% sample lang="lolcode" %} import:9-23, lang="LOLCODE" {% sample lang="bash" %} import:10-22, lang="bash" {% sample lang="d" %} import:4-17, lang="d" {% sample lang="piet" %}
{% sample lang="ss" %} import:9-12, lang="scheme" {% sample lang="scratch" %}
{% sample lang="ps1" %} import:16-27, lang="powershell" {% sample lang="coco" %} import:12-15, lang="coconut"
{% endmethod %}
Here, we set b to be the remainder of a%b and a to be whatever b was last timestep. Because of how the modulus operator works, this will provide the same information as the subtraction-based implementation, but when we show a and b as they change with time, we can see that it might take many fewer steps:
The Euclidean Algorithm is truly fundamental to many other algorithms throughout the history of computer science and will definitely be used again later. At least to me, it's amazing how such an ancient algorithm can still have modern use and appeal. That said, there are still other algorithms out there that can find the greatest common divisor of two numbers that are arguably better in certain cases than the Euclidean algorithm, but the fact that we are discussing Euclid two millennia after his death shows how timeless and universal mathematics truly is. I think that's pretty cool.
Here's a video on the Euclidean algorithm:
{% method %} {% sample lang="vim" %} import, lang="vim" {% sample lang="c" %} import, lang="c_cpp" {% sample lang="cs" %}
import, lang="csharp" {% sample lang="clj" %} import, lang="clojure" {% sample lang="cpp" %} import, lang="c_cpp" {% sample lang="java" %} import, lang="java" {% sample lang="kotlin" %} import, lang="kotlin" {% sample lang="js" %} import, lang="javascript" {% sample lang="lisp" %} import, lang="lisp" {% sample lang="py" %} import, lang="python" {% sample lang="hs" %} import, lang="haskell" {% sample lang="rs" %} import, lang="rust" {% sample lang="ml" %} import, lang="ocaml" {% sample lang="go" %} import, lang="go" {% sample lang="swift" %} import, lang="swift" {% sample lang="m" %} import, lang="matlab" {% sample lang="lua" %} import, lang="lua" {% sample lang="jl" %} import, lang="julia" {% sample lang="nim" %} import, lang="nim" % {% sample lang="asm-x64" %} import, lang="asm-x64" {% sample lang="f90" %} import, lang="fortran" {% sample lang="php" %} import, lang="php" {% sample lang="factor" %} import, lang="factor" {% sample lang="ws" %} Here is a readable version of the algorithms with comments. First, subtraction method: import, lang="whitespace" and modulo method: import, lang="whitespace" {% sample lang="scala" %} import, lang="scala" {% sample lang="racket" %} import, lang="racket" {% sample lang="ruby" %} import, lang="ruby" {% sample lang="st" %} import, lang="smalltalk" {% sample lang="emojic" %} import, lang:"emojicode" {% sample lang="lolcode" %} import, lang="LOLCODE" {% sample lang="bash" %} import, lang="bash" {% sample lang="d" %} import, lang="d" {% sample lang="piet" %} A text version of the program is provided for both versions.
import:126-146 {% sample lang="ss" %} import:, lang="scheme" {% sample lang="scratch" %} The code snippets were taken from this Scratch project
{% sample lang="ps1" %} import, lang="powershell" {% sample lang="coco" %} import, lang="coconut"
{% endmethod %}
<script> MathJax.Hub.Queue(["Typeset",MathJax.Hub]); </script>The code examples are licensed under the MIT license (found in LICENSE.md).
The text of this chapter was written by James Schloss and is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License.
- The image "Euclidsub" was created by James Schloss and is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License.
- The image "Euclidmod" was created by James Schloss and is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License.
After initial licensing (#560), the following pull requests have modified the text or graphics of this chapter:
- none