Find the Greatest Common Divisor in Javascript
Github repo with completed solution code & test suite
Given two integers which are not both zero, find the largest positive integer that divides into evenly into each of the integers.
Most of the digital tools we use every day rely on encryption. Somewhere in their architecture, sometimes many times or many places, web apps use RSA encryption to control authorization & authentication, secure stored data, and more.
Yet, these encryption processes frequently utilize a version of one of the oldest recorded algorithms in common use — the Euclidean Algorithm.
Algorithms go back a long way.
While we generally talk about algorithms in the context of mathematics or computer programming, they aren’t limited to those contexts.
After all, an algorithm can be broadly defined as:
a step-by-step procedure for solving a problem or accomplishing some end
By that definition, most of our oldest algorithms are, in fact, recipes.
Obviously, our timeline can only go as far back as surviving written records, thus unfortunately ignoring all the algorithms that were preserved only in oral tradition until later times.
Most of our oldest written records of algorithms are recipes (for beer, stews, and more), and are primarily Mesopotamian, largely due to their practice of using relatively durable clay tablets for writing.
The earliest surviving written records of mathematic (non-foody) algorithms are Egyptian, detailing the process for multiplying numbers, from c. 1700–2000 BC. Next, the Babylonians recorded algorithms for factorization and finding square roots c. 1600 BC.
Next on the timeline? The oldest recorded Integer Relation Algorithm, courtesy of Euclid c. 300 BC.
Euclid of Alexandria remains a shadowy figure to this day. Sure, there are lots of stories about him, but many of those stories are popular legends that circulate attached to any number of different notable ancients. We don’t know where he was born. We don’t know when he was born, or when he died. He wasn’t actually named Euclid — Εὐκλείδης is a descriptor which roughly translates to “The Great”.
When you hear “Euclid” the mental image that springs to mind is probably a vague cluster of geometric shapes.
That’s because he’s most well known for his authorship of Elements (Στοιχεῖα), the definitive treatise that gives us… well, pretty much everything we know about early explorations of abstract mathematical theory. This text is the groundbreaking work on exploring shapes using math, so much so that we still refer to Euclidean Geometry.
Basically, he’s famous for inventing geometry.
It’s not believed that Euclid actually came up with all the groundbreaking work in his book himself — he references a variety of now-lost texts by earlier thinkers, and frequently credits others for their ideas. However, this text is the oldest collection of these ideas that we have, and Euclid did an unbelievable amount of work to organize, expand, and build upon them with his own ideas. He created the record that codified the mathematical innovations of the world as he knew it, and his book was popular enough that copies were widely distributed within his era and never stopped being copied and used.
He didn’t only work on geometric shapes though. Remember the whole bit about the oldest-algorithm-still-in-use-today? Yeah. He wrote that. Did he invent it himself? Most likely not. But he explored and recorded it, making it available to mathematical history and, ultimately, us today.
So what, exactly, is Euclid’s algorithm, anyway?
Again, the challenge it tackles is that of finding the greatest common divisor of two numbers. The divisor is a number that you could divide either number by evenly, e.g. without a remainder (a decimal or fraction).
So, for example 1, 2 , & 4 would be divisors of 4.
1, 2, 3, & 6 are divisors of 6, but 4 divided by 3 is 1.333333 (does not divide evenly, has a remainder of .333333), and 4 & 6 don’t divide evenly into each other either, so the only shared divisors between 4 &6 would be 1 & 2. Therefore, the greatest common divisor of 4 & 6 would be 2.
Now, the logic we just worked through is a basic “brute force” solution to the challenge of finding the greatest common divisor — we made a list of all the divisors for each of our two numbers, compared the lists until we found all the shared divisors, then found the largest number on that list.
This works okay, I guess, for really small numbers (like 4 & 6), but imagine trying to use that approach to find the greatest common divisor for two really large numbers? It would be catastrophically laborious.
So, instead we can apply the algorithm recorded and passed down to us by Euclid.
The depends on the mathematical principle that the greatest common divisor of two numbers is the same as the greatest common divisor of the smaller number and the difference of the larger and smaller numbers (e.g. the larger number minus the smaller number).
For example, the greatest common divisor of 252 and 105 is 21.
- 252 = 21 × 12
- 105 = 21 × 5
Let’s test this logic: 252 minus 105 equals 147.
- 147 = 21 × 7
- 105 = 21 × 5
21 divides evenly into 147, and has no larger divisors shared with 105. Thus far, this mathematical principle seems to be holding true.
What’s the value of this, though? How is it applied to find the greatest common divisor of two numbers more efficiently?
Replacing the larger of our numbers with the difference of the two numbers gives us a smaller number to work with. If we apply this process recursively, we can achieve successively smaller pairs of numbers to work with, until the two numbers finally become equal. When our pair of numbers match, we’ve found the greatest common divisor.
Okay, so what does this look like in code?
To start with, we’ll get a function going — I’m calling it greatestCommonDivisor, and passing in two parameters: firstNum and secondNum.
To start shrinking our numbers, I’m going to call the function recursively.
If you’re new to recursion, check out my post on finding all the permutations of a string in order to access more content & helpful links regarding recursion!
We can call our function again, but this time assign the value of the remainder of firstNum minus secondNum (using the modulo operator) to the variable secondNum. This will allow us to effectively start “shrinking” down our numbers, as Euclid’s logic directs, until the two numbers become equal, alerting us that we’ve found our greatest common divisor.
However, if you’ve used recursion before, you might notice that we’re missing something — a base case.
A base case tells our shrinking pattern when to stop — without it, the function will just keep recursively calling itself over and over until it errors out.
If we throw this code into our console as is, we get a stack overflow error:
So, let’s add a base case:
Earlier, we said that we wanted to find ever-smaller pairs of numbers until the two numbers (firstNum and secondNum) were equal, correct?
So for our base case, we can put that if the remainder of the two numbers is zero, to stop the recursion.
As we’ve written our code thus far, we assign the value of that remainder to secondNum when we recursively call our function. So we can pop a conditional in our function saying that if secondNum is zero (i.e. a falsy value), to stop and return the firstNum.
What happens when we throw this into our console?
🌟 Great! Our function returned 4, which is in fact the greatest common divisor of 8 & 12.
However, there’s a bit more we can do to make this function adaptable and useful.
What happens if the user inputs negative numbers? After all, even if we put in -8 and -12, 4 would still divide evenly into both of them and be the greatest common divisor. What happens if we input negative numbers to our function?
Nope. That’s not right.
Let’s add a conditional to check for negative numbers. If our inputs are negative, we can simply convert them to positive numbers and continue on our way — the greatest common divisor does not change whether a number is positive or negative.
We can check to see if either of our parameters are less than zero. If they are, we can reassign that variable to a value that is the negative of the previous value. Since two negatives make a positive, this will flip our input number to a positive.
Okay, let’s throw that into the console and see if we get our correct value of 4:
🌟 Great! I love that this algorithm is able to accommodate negative numbers, as so many will only work when provided with positive integers.
Except, aren’t we still skipping one bit of the challenge we started with?
Given two integers which are not both zero, find the largest positive integer that divides into evenly into each of the integers.
I’m talking about the “not both zero” part. We don’t have any conditionals checking for that.
So let’s add one, and a nice error message to make our function more intuitive for the user.
This will test to make sure firstNum & secondNum aren’t both zero. It’s okay if one is zero, they just can’t both be. Let’s see what this returns in the console:
🌟 Great! Finally, in one last step for user-friendliness, let’s add an extra requirement to that conditional, so that our users will get the same error message if they attempt to input anything that isn’t an integer.
That’s it! 🌟
Now, our function will return the error message if it receives params which are not both integers or are both zero. Otherwise, it’ll go forward into our recursive loop to find the greatest common divisor.
