1

I am trying to find a faster lcm function than I currently have. I tried to look up some better gcd but couldn't find anything that solves the problem.

#include <bits/stdc++.h>
const int MOD = 1000000007;
using namespace std;

long gcd (long a, long b)
{
    if (a == 0) return b;
    return gcd (b % a, a);
}

long lcm (long a, long b)
{
    if (a == 0 || b == 0) return 0;
    return a * b / gcd (a, b);
}
AbdelAziz AbdelLatef
  • 3,650
  • 6
  • 24
  • 52
acrid
  • 11
  • 1
  • 3
    There are `std::gcd` and `std::lcm`, you can just use those instead of rolling custom ones. – HolyBlackCat Sep 25 '20 at 21:26
  • 1
    Using recursive calls might look shorter but carries certain problems: 1. Stack size is limited, and stack overflow errors are likely for bigger inputs 2. A loop combined with an optimized stack structure could well give better performance results. – πάντα ῥεῖ Sep 25 '20 at 21:28
  • 4
    Warning: `#include ` [loads the gun](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h). `using namespace std;` [takes off the safety](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). After that, [it's really easy for the program to shoot itself](https://godbolt.org/z/6sWGov). Use with caution, but prefer to not use at all. – user4581301 Sep 25 '20 at 21:35
  • See the references under [What is most efficient for GCD?](https://cs.stackexchange.com/questions/1447/what-is-most-efficient-for-gcd). – dxiv Sep 25 '20 at 21:36
  • @OP Open up the `` header file, look for the [std::gcd](https://en.cppreference.com/w/cpp/numeric/gcd) function, and see how the professionals have implemented it. – PaulMcKenzie Sep 25 '20 at 21:41

2 Answers2

0

The mothed you showed is probably the fastest one, but if you want to avoid recursion, try this, it may be slightly faster.

long gcd (long a, long b)
{
    while (a != 0)
    {
        b %= a;
        if (b == 0)
            return a;
        a %= b;
    }
    return b;
}
AbdelAziz AbdelLatef
  • 3,650
  • 6
  • 24
  • 52
0

Though this gcd algorithm is not that bad (and the number of iterations is always small), you can try the Stein's variant, which trades divisions for much faster shifts.

https://en.wikipedia.org/wiki/Binary_GCD_algorithm

Anyway, this does not improve the asymptotic complexity.