Jan 222014

Task: write a function called GCD that prints the greatest common divisor of two positive integers (a and b). Hint: you can use the fact that GCD(a, b) = GCD(b, a mod b) and GCD(a, 0) = a

This is my “proper” solution. Written in portable shell script (not bash, but also works in bash), returns only the denominator so that it can be used further as a function, even if it’s not actually one. Easily converted. Assumes good faith, doesn’t check if the input is indeed a number.

Took me a while, figuring out the algorithm, finding out (again) how to do math in shell and finding some gotchas. However, here’s another one, the modern sysadmin’s solution, in Python, this one is much faster to write:

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">