Mercurial > hg > qm-dsp
changeset 350:a067c2eeb13c
Add gcd
| author | Chris Cannam <c.cannam@qmul.ac.uk> |
|---|---|
| date | Tue, 08 Oct 2013 17:23:17 +0100 |
| parents | b247af4c23d2 |
| children | 5d9489187abd |
| files | maths/MathUtilities.cpp maths/MathUtilities.h tests/TestMathUtilities.cpp |
| diffstat | 3 files changed, 25 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- 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); + } +} +
--- 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
--- 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()