Greatest Common Denominator/Divisor/Factor (Geek Style – Euclidean Algorithm)

I recall learning about performing fractional math when I was young.  To be completely honest, I never actually learned an efficient way of determining greatest common denominator.  I brute forced it most of the time, meaning I just kept trying numbers until it seemed like I got the right denominator.  My method was very similar to what you see here at Kahn Academy.  As part of an algorithms course, I needed to write a function to determine the Greatest Common Denominator.  Any time you start talking about writing code

Any time you start talking about writing code, and you consider performing a function that “brute forces” an answer, your code will not run very fast.  Sometimes, you have no choice but to brute force a solution.  Sometimes there is a better way.  In this case, brute force is not the best way.  Here is how a brute force method would look:

Continue reading → Greatest Common Denominator/Divisor/Factor (Geek Style – Euclidean Algorithm)