?
Solved

Finding lowest common multiple / highest common factor

Posted on 2001-06-21
5
Medium Priority
?
2,551 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

On Demand Webinar: Networking for the Cloud Era

Ready to improve network connectivity? Watch this webinar to learn how SD-WANs and a one-click instant connect tool can boost provisions, deployment, and management of your cloud connection.

Question has a verified solution.

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

Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
  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 goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…

743 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