# HG changeset patch
# User Chris Cannam <c.cannam@qmul.ac.uk>
# Date 1381249397 -3600
# Node ID a067c2eeb13c3049e4b940ae012fcf510f1e7929
# Parent  b247af4c23d22e728d85d08c75e3e7ede9ce28e5
Add gcd

diff -r b247af4c23d2 -r a067c2eeb13c maths/MathUtilities.cpp
--- a/maths/MathUtilities.cpp	Fri Oct 04 18:46:32 2013 +0100
+++ b/maths/MathUtilities.cpp	Tue Oct 08 17:23:17 2013 +0100
@@ -390,3 +390,14 @@
     return f;
 }
 
+int
+MathUtilities::gcd(int a, int b)
+{
+    int c = a % b;
+    if (c == 0) {
+        return b;
+    } else {
+        return gcd(b, c);
+    }
+}
+
diff -r b247af4c23d2 -r a067c2eeb13c maths/MathUtilities.h
--- a/maths/MathUtilities.h	Fri Oct 04 18:46:32 2013 +0100
+++ b/maths/MathUtilities.h	Tue Oct 08 17:23:17 2013 +0100
@@ -66,6 +66,8 @@
     static int nearestPowerOfTwo(int x); // e.g. 1300 -> 1024, 12 -> 16 (not 8)
 
     static int factorial(int x);
+
+    static int gcd(int a, int b);
 };
 
 #endif
diff -r b247af4c23d2 -r a067c2eeb13c tests/TestMathUtilities.cpp
--- a/tests/TestMathUtilities.cpp	Fri Oct 04 18:46:32 2013 +0100
+++ b/tests/TestMathUtilities.cpp	Tue Oct 08 17:23:17 2013 +0100
@@ -133,6 +133,18 @@
     BOOST_CHECK_EQUAL(MathUtilities::factorial(4), 24);
 }
 
+BOOST_AUTO_TEST_CASE(gcd)
+{
+    BOOST_CHECK_EQUAL(MathUtilities::gcd(1, 1), 1);
+    BOOST_CHECK_EQUAL(MathUtilities::gcd(2, 1), 1);
+    BOOST_CHECK_EQUAL(MathUtilities::gcd(2, 3), 1);
+    BOOST_CHECK_EQUAL(MathUtilities::gcd(4, 2), 2);
+    BOOST_CHECK_EQUAL(MathUtilities::gcd(18, 24), 6);
+    BOOST_CHECK_EQUAL(MathUtilities::gcd(27, 18), 9);
+    BOOST_CHECK_EQUAL(MathUtilities::gcd(18, 36), 18);
+    BOOST_CHECK_EQUAL(MathUtilities::gcd(37, 18), 1);
+}
+
 BOOST_AUTO_TEST_SUITE_END()