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!
helpmealotAsked:
Who is Participating?
 
glebspyConnect With a Mentor 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
 
glebspyCommented:
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++)

 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.


0
 
helpmealotAuthor 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
 
helpmealotAuthor Commented:
Anybody out there?  This question couldn't be that tough. :)
0
 
helpmealotAuthor 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.

All Courses

From novice to tech pro — start learning today.