5
\$\begingroup\$

Following is my code to calculate gcd of two numbers. My intension is not to use any specialised algorithm, just simple maths. Do you see any problem in my solution?

#include <iostream>
#include <algorithm>

int main() {
    int n1, n2;

    std::cin >> n1 >> n2;

    int smaller = min(n1, n2);
    int greater = max(n1, n2);

    if(greater % smaller == 0)
    {
        std::cout << smaller;
        return 0;
    }

    int gcd = 1;

    for (int i = 2; i <= smaller / 2; i++) {
        if(smaller % i == 0 && greater % i == 0)
            gcd = i;
    }

    std::cout << gcd;
    return 0;
} 
\$\endgroup\$
  • 1
    \$\begingroup\$ I'm not entirely sure but because is such an simple problem, isn't just simple math in a case like yours not already an specialized algorithm , because i cannot imagine any other "special" way to do it. But that's maybe because i have not studied it. godbolt.org/g/385Zhs seems alright for clang and friends and the result is what you expect to be \$\endgroup\$ – ExOfDe Oct 2 '17 at 9:23
  • 1
    \$\begingroup\$ Do you consider the "Euclidean algorithm" (which is a well-known and efficient method to compute the gcd, with thousands of sample implementations) "specialized"? \$\endgroup\$ – Martin R Oct 2 '17 at 10:26
  • \$\begingroup\$ @MartinR I know about Euclidean algorithm. Though just wanted to implement simple and basic maths principles. \$\endgroup\$ – Pranit Kothari Oct 2 '17 at 10:34
  • \$\begingroup\$ Did you mean std::min and std::max? If your <algorithm> also puts names into the global namespace, you can easily write code that's not portable. \$\endgroup\$ – Toby Speight Oct 2 '17 at 12:11
  • \$\begingroup\$ Please do not mix different indent style. Pick the one which is most readable and stick with it. \$\endgroup\$ – 12431234123412341234123 Oct 2 '17 at 12:33
13
\$\begingroup\$

While you said that you know about the Euclidean algorithm and "just wanted to implement simple and basic maths principles," I'd like to point out that a basic implementation of the Euclidean algorithm would actually be simpler than what you have. Here's an example:

#include <iostream>
#include <utility>
#include <cstdlib>

int main() {
    int greater, smaller;

    std::cin >> greater >> smaller;

    while (smaller != 0) {
        greater %= smaller;
        std::swap(greater, smaller);
    }

    std::cout << std::abs(greater);
    return 0;
} 

Note that we don't actually need to ensure that abs(greater) >= abs(smaller) before entering the while loop since, if that's not the case, the first iteration of the loop just swaps them.

This GCD implementation has several advantages over yours:

  • It's shorter and arguably simpler.
  • It correctly handles negative and zero inputs.
  • It's also usually faster, especially for large inputs.

Unlike your code, the Euclidean algorithm handles negative inputs correctly. However, the sign of the result will be somewhat arbitrary (and, for C++03 and earlier, implementation-defined), so the code above actually outputs the absolute value of the result. Alternatively, we could simply take the absolute value of the inputs before the loop.

Also, if either input is zero the Euclidean algorithm will output (the absolute value of) the other, which matches the usual definition of the GCD. Your code will typically (if the numbers are non-negative) crash with a division-by-zero error in this case. In the Euclidean algorithm as implemented above, this cannot happen, since the only division is by smaller inside the loop, and the loop condition ensures that smaller cannot be zero.

Ps. One further improvement I'd prefer to make would be to split the GCD calculation into a reusable function, like this:

#include <iostream>
#include <utility>
#include <cstdlib>

int gcd(int greater, int smaller) {
    while (smaller != 0) {
        greater %= smaller;
        std::swap(greater, smaller);
    }
    return std::abs(greater);
}

int main() {
    int n1, n2;
    std::cin >> n1 >> n2;
    std::cout << gcd(n1, n2);
    return 0;
} 

This way, your GCD calculation isn't mixed with your I/O code and other irrelevant "boilerplate". While such mixing may be acceptable for a small single-purpose exercise like this one, for anything more complex you really should try to divide your code as much as possible into independent modules and to maintain a separation of concerns between them. In particular, your math code should not also do I/O, and your I/O code should not do any (nontrivial) math.

\$\endgroup\$
15
\$\begingroup\$
  1. The code does not account for negative numbers, yet the number type (int) allows them. The program will print 1 for the input -15 10, although 5 is the correct answer.
  2. The GCD is usually positive, but your program will print -10 on the input -10 10.
  3. A function int gcd(int, int) will make it easier to test and re-use.
  4. Since you provided a complete program you probably want to check whether the user actually inputs two numbers and not tree 0.1234 or something else that's not an int.

That being said, thank you for

  • not using namespace std;
  • properly indenting your code (you could add braces around the if, though)
  • using proper names where they were reasonable (n1 and n2 aren't long-lived enough)

I guess that you know that there are better algorithms, so for a simple algorithm like this there is not much to improve. You certainly have to consider negative numbers, though.

Also, some variables are available for the whole scope (n1 and n2), but only used for a short time. Try to limit the scope of a variable as much as possible, as it prevents errors like

for(i = 2; i <= n1 / 2; ++i) // should have been "smaller", whoops
\$\endgroup\$
  • \$\begingroup\$ -1 for recommendation to use unsigned. This is a bad idea since there's no protection against converting a negative int to a large unsigned int. Also GCD is normally defined over all integers. \$\endgroup\$ – kevin cline Oct 3 '17 at 9:50
  • \$\begingroup\$ @kevincline There is no protection against converting a large unsigned int into a negative value either. My point was that OP only covered unsigned int, not int with the original code. Either way, changed gcds signature, since my first and third point did not really play well together. \$\endgroup\$ – Zeta Oct 3 '17 at 9:52
1
\$\begingroup\$

I'll add to comments made by others.

In "real life" - use the standard library version

Well, first and foremost - I understand you're writing this as an exercise, but it must be said that for code you actually intend to use for anything - prefer the C++ standard library's std::gcd from <numeric>.

As a comment kindly points out, this is only available starting from C++17.

Consider recursion over loops

I would suggest you consider avoiding loops in favor of recursion, unless you're working on some super-optimized version (in which case your code would be different anyway).

I'm not claiming that's the "best" thing to do, but in mathematics we often define things recrusively and validate the definition inductively. This also goes for the the gcd: Consider the following recursive implementation (assuming non-negative integers):

constexpr unsigned gcd(unsigned n, unsigned m)
    if (m == 0) { return n; }
    if (n < m)  { return gcd(m, n); }
    return gcd(m, n - m);
}

(I chose unsigned to avoid more code for negative numbers.)

it is very easy to prove this is correct - that each statement is correct. And I do mean prove in the mathematical sense. With imperative code and loops, that doesn't happen as often.

One should note the above implementation is problematic in that it involves much deeper recursion than is necessary: O(n/m) calls (for n > m) rather than O(log(n/m)) (thanks @KevinCline for reminding me to point that out.) Here's another version - more efficient, even more terse, and also recursive:

constexpr int gcd(int greater, int lesser) {
    if (smaller == 0) { return greater; }
    return gcd(m, n % m);
}

... and we don't even need to assume non-negativity.

Consider templating for wider applicability

The last example (as well as many imperative/loop-based versions) could be used for any type which behavies kinda-sorta like the integers (e.g. constitutes a Euclidean Domain if you ignore overflow). So you can implement your GCD at once for all such types:

template <typename EuclideanDomain>
constexpr EuclideanDomain gcd(EuclideanDomain greater, EuclideanDomain lesser) {
    if (smaller == 0) { return greater; }
    return gcd(m, n % m);
}
\$\endgroup\$
  • \$\begingroup\$ Your first recursive definition will run in O(n/m) time instead of O(log(n)) time, and will overflow the stack when n is 100000 and m is 1. The second would be better written as: return lesser == 0 ? greater : gcd(lesser, greater % lesser) \$\endgroup\$ – kevin cline Oct 3 '17 at 9:54
  • \$\begingroup\$ @kevincline: The point about complexity is indeed worth mentioning, yes. As for a stack overflow - tail recursion should kick in. \$\endgroup\$ – einpoklum Oct 3 '17 at 10:09
  • \$\begingroup\$ my advice is exactly the reverse: always use loops instead of recursion, unless there is a good argument for recursion. The advantages: 1) you don't consume stack. Sometimes the compiler optimizations can transform your recursion into a loop, but if it can't high level of recursion can lead to stack starvation and program crash. 2) it's (depending on who you ask :p ) easier to implement, understand and read. 3) it's definitely easier to debug, and this is a big point. \$\endgroup\$ – bolov Oct 3 '17 at 19:30
  • \$\begingroup\$ Of course there are algorithms that are more naturally implemented as recursion, but if you want to compute the sum of a vector recursively please do pick a functional language for that instead of C++. \$\endgroup\$ – bolov Oct 3 '17 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.