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.
// 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;
// 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; }
Its hard to follow that code. But one thing I would wonder about is how you are finding the LCD of the numbers. You should be using Euclid's algorithm. this rapidly converges on the GCD without involving division operations.
reduces a fraction like 11/5 to 2 1/5. right? If so that is a bad approach. It uses a loop so it has to perform its work potentially many times--and it is considerable work. Why not use the logic
You can even avoid the test that is in the while loop. On a modern CPU this code should be nearly as fast as the code that does the test, so you are probably better off just runing the code each time, the test doesn't save much time when the code is skipped and makes the code longer to execute when both the test and reduction must be done.
0
helpmealotAuthor Commented:
Greetings nietod! I saw your first comment (before you posted your second), added a bunch of comments to the code, and "edited" the "question" by including the comments. My problem is of course the same as before, but the code may be a bit easier to follow now with the comments.
0
Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.
It might help if you posted the CFraction class. It looks to me like this code is directly modifying the members of the CFraction class. That is unwise, it should be using the members of the CFraction class.
There does not appear to be any parameters to this procedure. That seems strange and probably unwise.
Its unclear what these arrays are, like m_fractions.
Why are you approximating parts of the calculation?
0
helpmealotAuthor Commented:
Yes it is modifying code directly which is the opposite of the way it should be. This project is still in its early stages. I've not yet actually implemented any member functions for the CFraction class except: one to create a random fraction which fits certain parameters, one to generate a random number within a certain range, and one to return the length of a number in digits.
Here is the definition:
----------
struct CProblem;
struct CFraction
{ __int64 m_Num;
int m_NumL; // numerator, numerator length
__int64 m_Den;
int m_DenL; // denominator, denominator length
int m_Whole;
int m_WholeL; // whole number, whole number length
// Highest common factor shared by 2 numbers
__int64 SolveFindHCF (__int64 n1, __int64 n2);
// Lowest common multiple shared by 2 numbers
__int64 SolveFindLCD (__int64 n1, __int64 n2);
// Adds or subtracts two fractions like 1/2 and 2/3.
// Whole numbers are not involved here.
void SolveFractions (bool subtract, __int64 n1, __int64 d1, __int64 n2, __int64 d2, __int64 *nres, __int64 *dres);
CWorksheet *m_Worksheet;
};
----------
This code is all a part of a program I'm using to make worksheets for some students I tutor (6th graders, going on to 7th grade). The program works fine, and it can generate a page of problems with answers in about a tenth of a second. This is really sad considering this is a P3-866. I'm continuing to work on it because, as you noticed, it's a bit "shoddy" in its present condition and needs substantial work.
m_Fractions is an array of two CFraction objects. These two fractions make up the "Problem" as in the following:
2 1/3
+ 3 5/7
m_Fraction[0] is the top fraction, m_Fraction[1] is the bottom fraction. Originally I had considered the possibility of generating a number of fractions in just one problem, as in:
2 1/3
3 5/7
5 1/2
+ 3 2/3
-------
This has never materialized, and consequently, this array is an artifact which should probably be replaced by two individual variables.
The approximations are for debugging. The program used them to see if it was in fact answering the question correctly. This, like the array of 2 fractions, is an artifact and will be changed. Removing this approximating code would speed up the calculation.
0
helpmealotAuthor Commented:
I forgot to explain three more things you will encounter within the code above.
1st - CProblem::SolveFractions is not used presently. It is another artifact.
2nd - CFraction::GetLength returns the length of a number, in digits. The number 12345 would be 5 for instance. This function is used to construct the worksheet and keep the numbers nicely aligned.
3rd - CWorksheet is a class containing an array of CProblem structures. It creates the problems, which in turn create the components to the problem (the fractions themselves), formats the problems into a worksheet, and creates an answer sheet by utilizing the CProblem::Solve function.
The numbers that are generated and the types of problems that are generated are governed by the CSettings structure. Within this structure are a variety of parameters which limit or expand the types of problems the CProblem::Create function will allow.
>> I've not yet actually implemented any member functions for the CFraction class
BIG mistake. You can't make it fast until you make it right. Make it right first, then make it fast.
Good OOP design will help you to write clean code that can be more easily understood and more easily optimized. I woudl start over and write the classes right.
>> int m_NumL; // numerator, numerator length
What are these "lengths"?
>> double m_ApxTotal; // Approximate the whole answer (whole + numerator / denominator)
>> double m_ApxFraction; // Approximate the fraction (numerator / denominator)
What are these for? i would guess you don't want to store them. If they are ever needed--which is questionable, you probalby should calculate them when needed. Otherwise you yhave to calculate them continually and that is just more overhead.
>> // Generate a random number from min to max, inclusive
>> int Random (int min, int max);
thsi probably shoudl be a non-member function or at least a static member function. I doubt it needs t be a non-static member function.
>> // Get the length of a number
>> int GetLength (__int64 num);
What is this? Should this be a static member function?
>> void SolveFractions (bool subtract, __int64 n1, __int64 d1, __int64 n2,
>> __int64 d2, __int64 *nres, __int64 *dres);
thsi seems Like a bad form. at the very least I t should be
CFraction Add(CFraction F1, CFraction2);
CFraction Sub(CFraction F1, CFraction2);
but better yet, you shoudl overload the + and - operators for the CFraction class. Then you can write things like
F1 = F2 + F3;
That is much more expresive and much easier to work with. That allows you to write faster code--because it is clearer. Best of all, this code really isn't any harder to write than the SolveFractions() fucntion, it is just easier to use.
>> m_Fractions is an array of two CFraction objects.
There are better ways of handling this, but I dop't think you are read for that.
Honestly, I would start over and write the DFraction class right.
0
leCommented:
I beleive this program is fast enough for what it is doing.
100000 Multiplications in 3 second on my 500 Mh Pentium 3.
Idea: Numbers are first "normalized" 2 1/5 is represented as 11/5. Then operations are performed on "normalized" numbers.
Then result is denormalized;
#include <stdio.h>
#include <time.h>
struct nOrmalForm
{
__int64 Top ;
__int64 Bot ;
};
struct nUmber : public nOrmalForm
{
nUmber() {};
nUmber(int I, int T, int B) : Int(I)
{
Top = T;
Bot = B;
}
__int64 Int ;
};
int main(int, char*)
{
nUmber Number1(10, 127, 513);
nOrmalForm NormalForm1;
nUmber Number2(10, 127, 513);
nOrmalForm NormalForm2;
nOrmalForm RezNF;
nUmber RezNumber;
long Start = time(0);
for (int i = 0; i < 100000; i++)
{
MakeNormalForm(Number1, NormalForm1);
MakeNormalForm(Number2, NormalForm2);
Mult(NormalForm1, NormalForm2, RezNF);
Denormalize(RezNF, RezNumber);
}
long Dif = time(0) - Start;
printf("%d: %I64d %I64d/%I64d\n", Dif, RezNumber.Int, RezNumber.Top,RezNumber.Bot);
return 0;
}
0
helpmealotAuthor Commented:
First, nietod, you've pointed out a variety of useful things and for that you deserve points. I will post another question in this topic of 50 points which you may "answer" and get an A. Second, I like le's algorithms a bit better than my own. Therefore, he also should be awarded. For the purposes of my original question, he did answer it and will therefore get an A.
Now, nietod...
>> You can't make it fast until you make it right.
Good point. :)
>> I would guess you don't want to store them
Indeed, your guess was a good one. I will be fixing this problem.
>> thsi probably shoudl be a non-member function or at least a static member function
Yes, I changed it to a static member function.
>>>> int GetLength (__int64 num);
>>What is this? Should this be a static member function?
Yes, I changed it to a static member function.
>> F1 = F2 + F3;
Yes, yesterday I saw your comment and did just this. It does work much more nicely. The only problem I see is as follows. Part of the original answer sheet contained such information as the factors by which the fractional parts of the numbers should be multiplied to get the denominators equal. That is, it would tell me that 1 2/3 + 2 3/4 need to multiplied by 4/4 and 3/3 respectively in order to make the numbers "addable". Could you suggest a way to incorporate this functionality? I'm at a bit of a loss.
>>>> m_Fractions is an array of two CFraction objects.
>>There are better ways of handling this, but I dop't think you are read for that.
Suggest away! :)
>> Honestly, I would start over and write the DFraction class right.
Nah, the amount of work is really not that great. I've already fixed many of the problems you've pointed out. All I really have to do is add member functions that access private variables. This is not that complicated because of "Find and replace".
Thank you for all your help thus far. As I said, you will be able to find a question for you to answer in this forum.
Now, le, thank you for essentially rewriting the entire routine. It seems a bit cleaner than the current implementation (actually, it seems a lot cleaner). Of course, it will take me a bit to implement it into the existing program, but that's life. I appreciate your input. I will post back if I have any additional questions.
>> I like le's algorithms a bit better than my own
I don't.
I would write it right. Actually there are some improvements in that code, like a slightly better use of classes. But it really shoudl use oeprators and the inheritance is a little questionable and the implimentation ot he inheritance is a little slow.
If you make a good number class for this, it should be very easy to write yoru code. The first step is to begin work on that number class.
>> Could you suggest a way to incorporate this functionality? I'm at a bit of
>> a loss.
Yes. But I wuldn't do it yet. Start with the basics of the number class, then add it later when it is more appropriate. But basically you need a LCM function for the class. Somethine like
int LCM(CNumber Num1,CNumber Num2)
This will not lead to duplicate code, you will then be able to use this in the arithmetic operations.
>> Suggest away! :)
When the class is properly written, you can use it in a valarray<>. This is much like a matrix in mathematics. Its likely to simply this sort of thing greatly. But again, this is too soon for that. Start slow.
>> Nah, the amount of work is really not that great
You need to start over to make it better organized and cleaner. You don';t have to scrap the exiting code, but I woudl add peices back in a little bit at a time and make them right.
Basiclly I would start with a number class that stores the mixed fraction number.
Add a constructor to it that constructs from a seperate numerator,denomentator and whole number.
Add a copy constructor,
add an == operator--actually the default will do, but its not bad to write your own for cases like this
Add a static GCD function that uses euler's method.
Add a reduce function that puts everything in the class in its lowest terms.
Add operator *= as a member function It will need to use the reduce function.
Add operator * as a free function and write it to use *=.
Add the other aritmetic (/ + -) operators in the same way
Add a compare function (static) that works like strcmp() (same return convention).
Add comparison operators (non-member) that use the compare function to do the work.
That is the tact I would take. Then you will have a well-behaved classs for continuing on to the really good stuff.
>> Of course, it will take me a bit to implement it
>> into the existing program, but that's life
That is the part you might want to avoid. Best to write your class right, then take advantage of that.
0
Featured Post
It’s time to recognize experts that go above and beyond with helpful solutions and engagement on site. Choose from the top experts in the Hall of Fame or on the right rail of your favorite topic page. Look for the blue “Nominate” button on their profile to vote.