How to speed up a programs runtime?

[StMick]

I am trying to solve a least common multiple problem where the user inputs 2 numbers and the least common multiple is returned to the screen.

Does anyone have a suggestion of how to speed up my program/algorithm? Your help would be greatly appreciated. Please see my code below:

int main()
{
    int64_t a, b, i;
    int64_t maximum;
    int64_t power = pow(10,9);

    maximum = 2 * power +2;                // Maximum number allowed.

    cin >> a >> b;
    cout << endl;

    if (a>maximum || b>maximum)            // For cases where a number greater than the maximum is entered.
    {
        return 0;
    }
    if (a<1 || b<1)                        // For cases where a number is less than 1, the minimum, is entered.
    {
        return 0;
    }
    for (i = 1; i<=a*b; i++)
    {
           if (i%a==0)
            {
                if (i%b==0)
                {
                    cout <<i;
                    return 0;
                }
            }
    }
    return 0;

[Ganado]

Hint: The lcm(a, b) = abs(a * b) / gcd(a, b), where abs means absolute value.
GCD = Greater Common Divisor.

gcd(a, b) if implemented correctly has an O(log(min(a, b)) run-time complexity -- that means it's fast.

Hint 2: Look up the Euclidean algorithm if you want the answer to an efficient gcd algorithm.

__________________

Other notes: std::lcm and std::gcd are actually part of the C++17 standard library, but I assume you probably aren't allowed to use them. :(

[jonnin]

<algorithm> has an optimized gcd in it. No sense in trying to beat that, most of the stuff they give us is tweaked out.

[JLBorges]

> I am trying to solve a least common multiple problem where the user inputs 2 numbers and
> the least common multiple is returned to the screen.
> Does anyone have a suggestion of how to speed up my program/algorithm?

The calculation takes so little time that you will not get any measurable speed up, no matter what you do.

[Manga]

While I agree with JLBorges in that you can't sence a noticeable time save...

a >= b ? i = b : i = a;

	for (i; i <= a*b; i++)
	{
		if (i%a == 0 && i%b==0)
		{
				cout << i;
				break;
		}
	}

This code starts i at the lesser of a or b. This stops some wasted repetitions through the for loop.

[jonnin]

if we are going to tweak a questionable algorithm for fun...

i should iterate over a pre-generated list of primes, not all values. Im having a moment, but I think this is correct ... I can't think of a number pair with an LCM that isnt prime (??).
& is possibly marginally less clocks than && in this situation.

a*b quickly runs out of storage capacity and may not be the best comparison if you want to allow ALL 64 bit values to be usable for a & b (or, in just this one comparison, maybe a double is warranted?)

This is all silly, though. Ganado has the right of it.

[Computergeek01]

If you are seeing performance issues on this simple of a program, and that's a big if, then the problem isn't with your code. Try adding the running directory for the binary to the exception list to whatever equates to "Live Monitoring" for your AV client. Alternatively, your disk drive might be on it's way out, SSD's are dirt cheap right now.

[Ganado]

@JLBorges
OP's algorithm is slow as molasses. Try doing two co-prime numbers in the 10^6+ range...

#define PROGRAM 1

#if PROGRAM == 1

#include <iostream>
#include <cmath>
#include <cstdint>

int main()
{
    using namespace std;
    
    int64_t a, b, i;
    int64_t maximum;
    int64_t power = pow(10,9);

    maximum = 2 * power +2;                // Maximum number allowed.

    //cin >> a >> b;
    a = 15485863;
    b = 32452843;
    
    cout << endl;

    if (a>maximum || b>maximum)            // For cases where a number greater than the maximum is entered.
    {
        return 0;
    }
    if (a<1 || b<1)                        // For cases where a number is less than 1, the minimum, is entered.
    {
        return 0;
    }
    for (i = 1; i<=a*b; i++)
    {
           if (i%a==0)
            {
                if (i%b==0)
                {
                    cout <<i;
                    return 0;
                }
            }
    }
    return 0;
}

#elif PROGRAM == 2

#include <iostream>
#include <cmath>
#include <numeric>
#include <cstdint>

int main()
{
    int64_t a, b;
    
    a = 15485863;
    b = 32452843;
    
    // 15485863 * 32452843 = 502560280658509
    
    std::cout << std::lcm(a, b) << std::endl;
}

#elif PROGRAM == 3

#include <iostream>
#include <cmath>
#include <cstdint>

namespace my { 
    template <typename T>
    T gcd(T a, T b)
    {
        while (b != 0)
        {
            T t = b;
            b = a % b;
            a = t;
        }
        return a;
    }
}

int main()
{
    int64_t a, b;
    
    a = 15485863;
    b = 32452843;
    
    std::cout << std::abs(a*b) / my::gcd(a, b) << std::endl;
}

#endif 

@jonnin

I can't think of a number pair with an LCM that isnt prime

Two co-prime numbers will always have an LCM of a*b, or equivalently, a GCD of 1.
So, LCM(9, 10) = 90.

a * b will, of course, never be prime for any a, b > 1.

[jonnin]

I see. I knew I was missing something there. scratch that tweak then :)

[Manga]

ok Ganado, you made your point. I put in some big numbers and had plenty of time to do the laundry, mow the lawn, file my taxes, and watch every starwars movie ever.

Sorry StMick, seems like the loop has got to go.

[Ganado]

Lol, does that include the last few movies? If so, I'm so sorry. :p

[StMick]

Solved! Thank you for your hints, Ganado. Didn't know that LCM (x,y) = abs(x*y) / GCD (x,y).

Those for loops were slowing down the algorithm more than I had thought.

No time to file your taxes with this new speedy program :)