# Finding lowest common multiple / highest common factor

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!
###### Who is Participating?

Commented:
Dear Helpmealot,
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.
0

Commented:
I can give you a good tip for the highest common factor. Use this algorithm:

Numbers A,B

loop:

Switch if necessary so that A>=B

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

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.

0

Author Commented:
Does this implementation appear to be correct?

__int64 CProblem::SolveFindHCF (__int64 A, __int64 B)
{ if (A < B)
{ __int64 temp;
temp = A;
A = B;
B = temp;
}

if (A == 0 || B == 0)
{ return 1; }

__int64 C;
for (;;)
{ C = B % A;
if (C == 0)
{ return B; }

A = B;
B = C;
}
}
0

Author Commented:
Anybody out there?  This question couldn't be that tough. :)
0

Author Commented:
Thank you, it works now, and is much faster than before.
0
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.