From f64a82c538ecd4e6f0817e35eb5dee8af86815ce Mon Sep 17 00:00:00 2001 From: Aryadev Chavali Date: Fri, 26 Jul 2024 01:24:28 +0100 Subject: Extracted gcd algorithm into its own function --- src/main.cpp | 28 ++++++++++++++++++++-------- 1 file changed, 20 insertions(+), 8 deletions(-) (limited to 'src') diff --git a/src/main.cpp b/src/main.cpp index 143816a..222cab4 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -18,8 +18,25 @@ #include #include +#include +#include + +#define MIN(A, B) ((A) < (B) ? (A) : (B)) +#define MAX(A, B) ((A) > (B) ? (A) : (B)) + typedef uint64_t word_t; +word_t gcd(word_t a, word_t b) +{ + if (a == b) + return a; + else if (a == 1 || b == 1) + return 1; + for (word_t r = b % a; r != 0; b = a, a = r, r = b % a) + continue; + return a; +} + struct Fraction { word_t numerator, denominator; @@ -37,14 +54,9 @@ struct Fraction // No-Op if already simplified if (is_simplified) return; - word_t a = numerator < denominator ? numerator : denominator, - b = numerator < denominator ? denominator : numerator; - // Euclidean algorithm - for (word_t r = b % a; r != 0; b = a, a = r, r = b % a) - continue; - // a will be the gcd - numerator /= a; - denominator /= a; + word_t hcf = gcd(MIN(numerator, denominator), MAX(numerator, denominator)); + numerator /= hcf; + denominator /= hcf; // Ensure this is a noop after this is_simplified = true; } -- cgit v1.2.3-13-gbd6f