Solved
Finding lowest common multiple / highest common factor
Posted on 2001-06-21
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!