Solved
My code is slow. Can you speed it up?
Posted on 2001-07-02
Hello,
I have some code here, and the profiler says it's a major bottleneck. I believe it. I am looking for ways to enhance it speedwise. The code solves a fraction problem like (1 2/3) + (2 3/4) or (5 6/2) * (3 2/5) and puts the answer in lowest terms (actually it solves many many problems like that and the idea is to get it to solve them faster). The trick of course is that the answer is a fraction. This code creates an answer still in fraction form. Getting the decimalized answer (1.234) is of course trivial and is not the purpose of this code.
If you have suggestions which significantly speed this code up, I will award 100 points and an A. Otherwise, I will leave this at 50 points and give whomever helps the most the A.
If there are questions regarding what some of the variables mean, please ask. Most I believe should be relatively intuitive.
The code:
----------------
CString CProblem::Solve (void)
{ __int64 hcf;
CFraction top, bottom, ans;
CString ret;
// First we must determine the type of the question.
// This section of code solves all addition and subtraction problems.
if (m_Sign == '+' || m_Sign == '-')
{ __int64 lcd;
__int64 top_factor, bottom_factor;
// Find the lowest common denominator
lcd = SolveFindLCD (m_Fractions[0].m_Den, m_Fractions[1].m_Den);
if (m_Fractions[0].m_Den != m_Fractions[1].m_Den)
{ // top_factor and bottom_factor are the numbers we want to multiply
// the numerators and denominators by to make the two fractions have
// the same denominators. "top_factor" is for the top fraction,
// and "bottom_factor" is for the bottom. For instance, let's say we have
// 1 5/6 + 3 4/7. We want to multiply the numerator and denominator of the
// first fraction (1 5/6) by "top_factor" and the numerator and denominator
// of the second fraction by "bottom_factor". In this example, top_factor would
// be 7, and bottom_factor would be 6.
top_factor = lcd / m_Fractions[0].m_Den;
bottom_factor = lcd / m_Fractions[1].m_Den;
// "top" is the first fraction, "bottom" is the second fraction.
// Continuing the example from above, "top" would represent (1 5/6)
// and "bottom" would represent (5 4/7)
// This code will make the two fractions have the same denominators.
// Continuing the example, after this code executes, the two fractions will
// have a denominator of 42.
top.m_Den = m_Fractions[0].m_Den * top_factor;
top.m_Num = m_Fractions[0].m_Num * top_factor;
top.m_Whole = m_Fractions[0].m_Whole;
bottom.m_Den = m_Fractions[1].m_Den * bottom_factor;
bottom.m_Num = m_Fractions[1].m_Num * bottom_factor;
bottom.m_Whole = m_Fractions[1].m_Whole;
}
else
{ // This code simply reassigns the original fractions to the new
// variables. This is because they happen to have the same denominators
// already anyway. This code won't execute if the denominators are not
// the same.
top.m_Den = m_Fractions[0].m_Den;
top.m_Num = m_Fractions[0].m_Num;
top.m_Whole = m_Fractions[0].m_Whole;
bottom.m_Den = m_Fractions[1].m_Den;
bottom.m_Num = m_Fractions[1].m_Num;
bottom.m_Whole = m_Fractions[1].m_Whole;
}
// Now we have to become specific. At this point, both numbers will
// have the same denominators. Now we do the addition or subtraction.
if (m_Sign == '+')
{ ans.m_Num = top.m_Num + bottom.m_Num; // Add the numerators
ans.m_Den = top.m_Den; // Denominator is the same
ans.m_Whole = top.m_Whole + bottom.m_Whole; // Add the whole numbers
// If the numerator is greater than the denominator, simplify it
// so it's not any longer. e.g. 2 5/2 would become 4 1/2
if (ans.m_Num >= ans.m_Den)
{ ans.m_Whole += (int) ((double) ans.m_Num / (double) ans.m_Den);
ans.m_Num = ans.m_Num % ans.m_Den;
}
}
else // Subtraction
{ // Fractions can be very unusual remember.
// Borrow as much as necessary from the whole number until the subtraction
// can be carried through.
while (top.m_Num - bottom.m_Num < 0)
{ top.m_Whole -= 1;
top.m_Num += top.m_Den;
}
ans.m_Num = top.m_Num - bottom.m_Num; // Subtract the numerators. This will be positive
ans.m_Den = top.m_Den; // Denominator is the same
ans.m_Whole = top.m_Whole - bottom.m_Whole; // Subtract the whole numbers
}
// Approximate the final answer.
ans.m_ApxTotal = (double) ans.m_Whole + (double) ans.m_Num / (double) ans.m_Den;
// Approximate the fractional part of the answer.
ans.m_ApxFraction = (double) ans.m_Num / (double) ans.m_Den;
// Find the highest common factor shared by the numerator and denominator.
// This reduces a fraction like 5/10 to 1/2 (the highest common factor is 5).
hcf = SolveFindHCF (ans.m_Num, ans.m_Den);
ans.m_Num /= hcf;
ans.m_Den /= hcf;
// Create the answer string.
if (m_Sign == '+')
{ // This is an approximation of the actual answer.
// It is used to ensure all the code above arrived at the correct answer.
double apx = m_Fractions[0].m_ApxTotal + m_Fractions[1].m_ApxTotal;
CString temp;
ret.Format ("LCD: %I64d; Top x %I64d; Bottom x %I64d; Ans: %d + %I64d / %I64d;", lcd, top_factor, bottom_factor, ans.m_Whole, ans.m_Num, ans.m_Den);
if (fabs (ans.m_ApxTotal - apx) > .1)
{ temp.Format ("%f =?= %f; The program seems to have failed to calculate this answer correctly.\r\n", ans.m_ApxTotal, apx);
ret += temp;
}
}
else
{ // This is an approximation of the actual answer.
// It is used to ensure all the code above arrived at the correct answer.
double apx = m_Fractions[0].m_ApxTotal - m_Fractions[1].m_ApxTotal;
CString temp;
ret.Format ("LCD: %I64d; Top x %I64d; Bottom x %I64d; Ans: %d + %I64d / %I64d;", lcd, top_factor, bottom_factor, ans.m_Whole, ans.m_Num, ans.m_Den);
if (fabs (ans.m_ApxTotal - apx) > .1)
{ temp.Format ("%f =?= %f; The program seems to have failed to calculate this answer correctly.\r\n", ans.m_ApxTotal, apx);
ret += temp;
}
}
}
// This code executes if we have a multiplication or division problem.
// Since multiplication/division is significantly different from addition/subtraction,
// this warrants a separate section of code, hence the "else if"
else if (m_Sign == 'x' || m_Sign == '?')
{ // Convert the mixed fractions to improper fractions
// "top" is the first fraction, "bottom" is the second.
top.m_Num = m_Fractions[0].m_Whole * m_Fractions[0].m_Den + m_Fractions[0].m_Num;
top.m_Den = m_Fractions[0].m_Den;
bottom.m_Num = m_Fractions[1].m_Whole * m_Fractions[1].m_Den + m_Fractions[1].m_Num;
bottom.m_Den = m_Fractions[1].m_Den;
// Begin constructing the answer.
CString temp;
temp.Format ("%I64d / %I64d * %I64d / %I64d ", top.m_Num, top.m_Den, bottom.m_Num, bottom.m_Den);
ret += temp;
// Initialize
ans.m_Whole = 0;
if (m_Sign == 'x') // Multiply right across
{ ans.m_Num = top.m_Num * bottom.m_Num;
ans.m_Den = top.m_Den * bottom.m_Den;
}
else // Invert and multiply
{ ans.m_Num = top.m_Num * bottom.m_Den;
ans.m_Den = top.m_Den * bottom.m_Num;
}
// If the numerator is greater than the denominator, simplify it
// so it's not any longer. e.g. 2 5/2 would become 4 1/2
if (ans.m_Num >= ans.m_Den)
{ ans.m_Whole += (int) ((double) ans.m_Num / (double) ans.m_Den);
ans.m_Num = ans.m_Num % ans.m_Den;
}
// Find the highest common factor shared by the numerator and denominator.
// This reduces a fraction like 5/10 to 1/2 (the highest common factor is 5).
hcf = SolveFindHCF (ans.m_Num, ans.m_Den);
ans.m_Num /= hcf;
ans.m_Den /= hcf;
// Approximate the final answer.
ans.m_ApxTotal = (double) ans.m_Whole + (double) ans.m_Num / (double) ans.m_Den;
// Approximate the fractional part of the answer.
ans.m_ApxFraction = (double) ans.m_Num / (double) ans.m_Den;
// Generate the answer string.
if (m_Sign == 'x')
{ double apx = m_Fractions[0].m_ApxTotal * m_Fractions[1].m_ApxTotal;
CString temp;
ret.Format ("Ans: %d + %I64d / %I64d;", ans.m_Whole, ans.m_Num, ans.m_Den);
if (fabs (ans.m_ApxTotal - apx) > .1)
{ temp.Format ("%f =?= %f; The program seems to have failed to calculate this answer correctly.\r\n", ans.m_ApxTotal, apx);
ret += temp;
}
}
else
{ double apx = m_Fractions[0].m_ApxTotal / m_Fractions[1].m_ApxTotal;
CString temp;
ret.Format ("Ans: %d + %I64d / %I64d;", ans.m_Whole, ans.m_Num, ans.m_Den);
if (fabs (ans.m_ApxTotal - apx) > .1)
{ temp.Format ("%f =?= %f; The program seems to have failed to calculate this answer correctly.\r\n", ans.m_ApxTotal, apx);
ret += temp;
}
}
}
return ret;
}
// This code finds the highest common factor shared by two numbers.
// For instance, if A = 5 and B = 10, the function will return 5.
// If A = 3 and B = 17, the function will return 1.
__int64 CProblem::SolveFindHCF (__int64 A, __int64 B)
{ if (B < A)
{ __int64 temp;
temp = A;
A = B;
B = temp;
}
if (A == 0 || B == 0 || A == 1 || B == 1)
{ return 1; }
__int64 C;
for (;;)
{ C = B % A;
if (C == 0)
{ return A; }
B = A;
A = C;
}
}
// This function finds the lowest common multiple of two numbers,
// or the Lowest Common Denominator (LCD). For instance, if A = 5
// and B = 10, this function will return 10. If A = 2 and B = 35,
// this function will return 70.
__int64 CProblem::SolveFindLCD (__int64 A, __int64 B)
{ return A / SolveFindHCF (A, B) * B; }