gcd problem

[mdbrock7]

I am in a beginner C++ class and I have a homework problem where I must to find the greatest common divisor through subtraction. I am totally lost. Can anyone show me what I am doing wrong?

#include <iostream>
using namespace std;

int main ()
{
int m;
int n;
int firstNum = m;
int secondNum = n;

cout << "1st number:" << endl;
cin >> firstNum;
cout << "2nd number:" << endl;
cin >> secondNum;

while (m != 0)
{

if (n > m )
{
int t = m; m = n; n = t;
}

m = n - m;

}

cout << "the gcd of" << endl;
cout << firstNum;
cout << "and" << endl;
cout << secondNum;
cout << "is" << endl;
cout << n;

return 0;
}

[Narue]

The traditional (if inefficient) algorithm is:

# Pseudocode
gcd ( m, n )
begin
  while m != n do
    if m > n
      m := m - n
    else
      n := n - m
  loop

  return m
end

[mdbrock7]

Thanks for the reply but I'm still confused

[Narue]

>Thanks for the reply but I'm still confused
Well, aside from spelling out the algorithm so that it's trivial to convert to C++, there's not much more I can do to help you. Search google for analyses on the algorithm. It's been around for a while, so you shouldn't have trouble finding anything.

[JoBe]

Hi,

Ever tought about using the Algorithm of Euclides?

Example of getting the greatest common devider gcd(1147, 851)
Steps:
1) 1147 = 1x851 + 296
2) 851 = 2x296+259
3) 296 = 1x259 + 37
4) 259 = 7x37
Rest equals 0.
Then the gcd equals 37.

If you can translate this into C++ code, you should be able to find the solution.

If it's not clear, google for the Algorithm of Euclides!

[mdbrock7]

The problem is I have to use this basic shell to get my answer. This is what I have so far. No matter what two numbers I enter I always get an answer of zero which is obviously not the gcd. I have spent hours trying to adjust it but I just can't get it to work. Any thoughts on a fix?

#include <iostream>
using namespace std;

int main ()
{
int m;
int n;
int firstNum;
int secondNum;

cout << "1st number:" << endl;
cin >> firstNum;
cout << "2nd number:" << endl;
cin >> secondNum;

m = firstNum;
n = secondNum;

while (m != 0)
{

if (n > m )
{
int t = m; m = n; n = t;
}

m = m - n;

}

cout << "the gcd of" << endl;
cout << firstNum;
cout << "and" << endl;
cout << secondNum;
cout << "is" << endl;
cout << m;

return 0;
}

[Narue]

>Ever tought about using the Algorithm of Euclides?
The pseudocode I gave was the Euclidean algorithm. It was an earlier formulation of the problem using subtraction instead of the later (more efficient) algorithm that uses the remainder of integer division.

>The problem is I have to use this basic shell to get my answer.
Then it's homework, and we won't do it for you. Unless you're incapable of doing simple math, it's a small step to convert the algorithm I gave you into something that fits your shell.

[mdbrock7]

You can't give me a hint where my code goes wrong? It compiles and executes without any errors but I'm just not getting the right answer. Is the problem in my If statement?

[mdbrock7]

i tried using your pseudocode and this is what I now have. It doesn't return any value. Any suggestions?

#include <iostream>
using namespace std;

int main ()
{
int m;
int n;
int firstNum;
int secondNum;

cout << "Enter 1st number:" << endl;
cin >> firstNum;
cout << "Enter 2nd number:" << endl;
cin >> secondNum;

m = firstNum;
n = secondNum;

while (m != n);
{
if (m > n)
m = m - n;
else
n = n - m;
}

return m;

cout << "the gcd of" << endl;
cout << firstNum;
cout << "and" << endl;
cout << secondNum;
cout << "is" << endl;
cout << m;

return 0;
}

[JoBe]

Why do you return m after the loop??

There's no need to :!:

And look at your loop, look how you defined it :!:

[Narue]

>Any suggestions?
Read a book on C++, and read the warnings your compiler gives you:

#include <iostream>

using namespace std;

int main()
{
  int m; 
  int n;
  int firstNum;
  int secondNum;

  cout << "Enter 1st number:" << endl;
  cin >> firstNum;
  cout << "Enter 2nd number:" << endl;
  cin >> secondNum;

  m = firstNum;
  n = secondNum;

  while (m != n)
  {
    if (m > n)
      m = m - n;
    else
      n = n - m;
  }

  cout << "the gcd of " << firstNum
       << " and " << secondNum
       << " is " << m << endl;

  return 0;
}

[mdbrock7]

its not giving me any warnings and I have read a couple of C++ books.

Can't someone just give me the answer and then breifly explain what I was doing wrong?
This is not something that I even get a grade on. It's just homework for my ownpractice. I am asking you guys the same questions I would ask my teacher if he were available.

Thanks for the help you are giving me but I am having a hard time catching on to this particular problem.

I'll keep working and hopefully I'll figure it out

[JoBe]

Euh, I gave you tips and Narue gave you the solution :rolleyes:

Before you write a responce, I'd suggest you better read what someone wrote to help you :!:

[mdbrock7]

Euh, I gave you tips and Narue gave you the solution :rolleyes:

Before you write a responce, I'd suggest you better read what someone wrote to help you :!:

Where is the solution?

I appreciate the tips that were given. Thanks a lot for your help. I just want to understand this and I haven't been able to so far.

Edited: Now I got it. I thought he just replied with my earlier code
Thanks for your help guys.
I still don't see exactly what I was doing wrong (other than returning m). Was that the problem? Can you point out exactly what was changed? This has drove me nuts the past couple of days.

[Fasola]

what does := mean?

[Narue]

>its not giving me any warnings
Your settings are too low. Turn your compiler up to the highest warning level and you'll catch more problems.

>Can't someone just give me the answer
No, because then you wouldn't learn squat. The whole point of this exercise is for you to learn, not for you to get people who already know how to do it to do it for you.

>I still don't see exactly what I was doing wrong

while (m != n);

This is a complete loop. The semicolon acts as the loop body. The problem is more obvious when you put the body on its own line:

while (m != n)
  ;

>what does := mean?
It's my pseudocode convention for assignment, borrowed from Pascal.

[mdbrock7]

Another problem:
If "0" is entered as one of the numbers the program doesn't work. Would this statement be an acceptable fix?

if ((firstNum <= 0) || (secondNum <= 0))
{
cout << "Numbers must be greater than zero" << endl;
return 0;
}
while (m != n)
{
if (m > n)
m = m - n;
else
n = n - m;
}

[Narue]

Did you try it? Or did you just come running here to get our okay before experimenting? I'll let you in on a little secret. I don't know about everyone else, but most of my advanced knowledge comes from experimentation on my own. If I had waited for someone to tell me about this stuff, I wouldn't be able to program my way out of a wet paper bag.