writing reduce function more efficiently

[UGAman22]

Hi I was wondering how I could re write this code so it will make my program more efficient and it will also be able to account for negative numerators (my program does not allow negative denominators or zero). My program takes a really long time when I start to enter large fractions because the loop has to go through so many times. If anyone could help me rewrite this so I don't have to wait so long and it will make my code more efficient I would greatly appreciate it!

void fraction::reduce()
    for(int i = numer * denom; i > 1; i--)
    {
        if((numer % i) == 0 && (denom % i) == 0)
        {
            numer = numer / i;
            denom = denom / i;
        }
    }

[Militie]

That seems to be the most efficient way. You are finding the greatest common factor. Now what you need to do is make sure you break the for loop. Once you have found the greatest common factor you don't need to keep looking for more common factors. Stick a break; after the two numer and denom statements and that should increase the efficiency in the long run.

[firedraco]

Why are you starting a numer*denom and going down? % will never equal 0 unless the second argument is <= the first, which will not happen for quite some time. Just start at the smallest of the number or denominator.

On the other hand, you seem to be trying to implement gcd; go look at Wikipedia for a better implementation.

[UGAman22]

it works with this one, but the only thing is when i enter a negative integer for one of them then it automatically does not reduce because the gcd is a negative number. And it does take forever for it to run my program completely when I am printing out my array of fractions. That is why I need to know how to rewrite it so it is better and negatives will still make it reduce as well. But i should start at say the denominator maybe since it will always be positive?

[Militie]

Take a look at the program I modified based off of your premise.

Notice the clock, run it with a few different sized values for your numerator and denominator. You will notice that as your values get larger, so does the time to compute the reduced value for each.

#include <iostream>
#include <ctime>


int numer, denom;

void reduce(){

	double numer_d = static_cast<double> (numer);
	double denom_d = static_cast<double> (denom);

	if (numer == 0)
	{
		std::cout << "Your numerator is equal to zero. The reduced fraction is zero (0/1).";
	}

	else if (denom == 0)
	{
		std::cout << "Your denomenator is zero, this is undefined.";
	}

	else if ((numer_d / denom_d) < 0){
		for (int i = numer * denom; i < -1; i++)
		{
			if ((numer % i) == 0 && (denom % i) == 0)
			{
				numer = numer / i;
				denom = denom / i;
				break;
			}
		}
	}
	else {
		for (int i = numer * denom; i > 1; i--)
		{
			if ((numer % i) == 0 && (denom % i) == 0)
			{
				numer = numer / i;
				denom = denom / i;
				break;
			}
		}
	}
}

int main()
{
	numer = 105000;
	denom = 15000;
	clock_t t;
	t = clock();
	reduce();
	t = clock() - t;
	std::cout << "Your fraction is, " << numer << '/' << denom;
	std::cout << "\n" << "It took " << (float)t / CLOCKS_PER_SEC << " seconds!\n";
}

[UGAman22]

I'm kinda confused. Are you just trying to show me the run time when the reduce function is called?

[Militie]

Yes, what I asked you to try was editing the size of the numerator and denominator, and checking the difference in time.

If you had done it you would have found that the time it takes for the reduce() function to run increases as the size of your numerator and denominator. This is because of the efficiency of the function. The efficiency of your function reduce is O(n).

SO the answer to your first question is Yes, it will take longer to run the larger the numbers are.