I've got these two functions, homegrown obviously, which find the lowest common multiple of two numbers (or least common denominator for two fractions, for example 3 and 6 would be 3) and the highest common factor of two numbers (for example, 15 and 10 would be 5).

void CProblem::SolveFindHCF (__int64 n1, __int64 n2, __int64 *hcf)

{ __int64 i, range;

if (n1 <= -1)

{ n1 *= -1; }

if (n2 <= -1)

{ n2 *= -1; }

*hcf = 1;

if (n1 > n2)

{ range = n2; }

else

{ range = n1; }

for (i = 1; i <= range; i++)

{ if (n1 % i == 0 && n2 % i == 0)

{ *hcf = i; }

}

}

void CProblem::SolveFindLCD (__int64 n1, __int64 n2, __int64 *lcd)

{ __int64 tden, bden;

for (tden = n1; tden < n1 * 10000; tden += n1)

{ for (bden = n2; bden <= tden; bden += n2)

{ if (tden == bden)

{ *lcd = tden; // That's that

return;

}

}

}

}

The problem is the speed. When using large numbers, these functions are very slow. I would like tips on improving the speed of these functions. Sometimes millions of iterations are necessary for any given problem, and this is unacceptable as anyone with half a brain could realize.

Please post ways to enhance the performance and eliminate any bugs in these functions. Whoever contributes the most will get the points. Thanks!

void CProblem::SolveFindHCF (__int64 n1, __int64 n2, __int64 *hcf)

{ __int64 i, range;

if (n1 <= -1)

{ n1 *= -1; }

if (n2 <= -1)

{ n2 *= -1; }

*hcf = 1;

if (n1 > n2)

{ range = n2; }

else

{ range = n1; }

for (i = 1; i <= range; i++)

{ if (n1 % i == 0 && n2 % i == 0)

{ *hcf = i; }

}

}

void CProblem::SolveFindLCD (__int64 n1, __int64 n2, __int64 *lcd)

{ __int64 tden, bden;

for (tden = n1; tden < n1 * 10000; tden += n1)

{ for (bden = n2; bden <= tden; bden += n2)

{ if (tden == bden)

{ *lcd = tden; // That's that

return;

}

}

}

}

The problem is the speed. When using large numbers, these functions are very slow. I would like tips on improving the speed of these functions. Sometimes millions of iterations are necessary for any given problem, and this is unacceptable as anyone with half a brain could realize.

Please post ways to enhance the performance and eliminate any bugs in these functions. Whoever contributes the most will get the points. Thanks!

Numbers A,B

loop:

Switch if necessary so that A>=B

C=B mod A (C=B%A in c++)

if(C==0) Answer is B, break;

otherwise repeat with numbers B,C

end loop

This is a really fast algorithm. From what I know, it could be the fastest in existence.

I guess you can probably turn that into code yourself but if you need help just say.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.

No, sorry - that doesn't look correct.

Also I made a mistake: it should be B>A, not A>B. Or you have to take greater number mod smaller number, anyway.

So it looks like this:

Choose numbers A,B

Sort so B>A

loop:

C=B%A (that guarantees that C<A<B)

if(C==0)return A

else {B=A;A=C;}

end loop

Should work.

I also thought of a good way of using this to determine the LCM of A,B (your second problem) - I think this is pretty fast, too:

LCM(A,B)=(A/HCF(A,B))*B

Do the multiplication,division in the above order so there is less risk of an overflow, although the expression LCM(A,B)=A*B/HCF(A,B) is neater.