Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Finding lowest common multiple / highest common factor

Posted on 2001-06-21
5
Medium Priority
?
2,566 Views
Last Modified: 2007-12-19
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!
0
Comment
Question by:helpmealot
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
5 Comments
 
LVL 1

Expert Comment

by:glebspy
ID: 6216777
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
 

Author Comment

by:helpmealot
ID: 6218790
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 Comment

by:helpmealot
ID: 6221472
Anybody out there?  This question couldn't be that tough. :)
0
 
LVL 1

Accepted Solution

by:
glebspy earned 400 total points
ID: 6222978
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
 

Author Comment

by:helpmealot
ID: 6223064
Thank you, it works now, and is much faster than before.
0

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

604 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question