Binary Euclid's Algorithm

[exluddite]

Hi folks.
My class is working on the whole fraction thing, which of course involves reducing. I found something interesting via a search of the boards here, the binary Euclid's algorithm.
Anyway I tried crunching the rules into code, and came up with this:

#include <iostream>
#include <cmath>
using namespace std;

int main (int n, int m)
{
    cout<<"enter n";
    cin>>n;
    cout<<"enter m";
    cin>>m;
    if (n>=m)
    {
    if (n%2==0 && m%2==0)
    {    
        n /= 2;
        m /= 2;
    }
    else if ((n%2==0 && m%2!=0)||(n%2!=0 && m%2==0))
    {
        n /= 2;
        m = m;
    }
    else if ((n-m)%2==0)
    {
        m-=n;
    } 
    cout<<"gcd:"<<m;
}           
    else if (m>n)
    {
    if (m%2==0 && n%2==0)
    {    
        m /= 2;
        n /= 2;
    }
    else if( (m%2==0 && n%2!=0)||(m%2!=0 && n%2==0))
    {
        m /= 2;
        n = n;
    }
    else if ((m-n)%2==0)
    {
        n-=m;
    } 
   cout<<"gcd:"<<n;
}       
       system ("pause");
       return 0;
}

I'm getting some weird results, but for the life of me I can't figure out where things are going wrong.
So, I have two questions:
1. Any hints as to where my logic is flawed?
2. I am currently using the new bloodshed compiler. One thing that would help me greatly is if I could "track" a variable through the program to check where it went wrong. How do I do that?

Thanks

[jverkoey]

First off...the link says this is a recursive algorithm...but I'm not seeing where you're making the program run recursively....or I'm on crack and can't see it...but I noticed that your main function has the n and m functions....that's not a good idea.

What you should have is a separate function that you call, recursively to solve the answer. It's really not standard at all to call the main function again, especially when you've given it nonstandard parameters too....

[exluddite]

Ok, I think I see what you mean. This isn't how the function is going to be when it's finished, I just have a habit of taking a piece of a program aside when it gives me a problem.

[jverkoey]

S'no problem, just struck me as odd that you implemented a recursive algorithm without using any recursion (though it is possible...but you still needs loops usually, and I didn't see any of those either)

See my sig for a good definition of recursion.

[PJYelton]

Yeah, you are totally missing the recursion part of the algorithm. For example, rule #2 states if N is even while M is odd, then gcd(N, M) = gcd(N/2, M). That means the greatest common denominator of N and M is the the same as the greatest common denominator of N/2 and M. You divide N by two, but don't continue to take the gcd, instead you just stop.

[Kletian]

If your main goal here is reducing fractions, then you really don't anything more than the standard algorithm gcd(N,M) = gcd(M, N mod M). The binary version is a slight improvement over the original (based on your source) and I doubt it's really worth messing up (beyond curiosity). Consider:

#include <iostream.h>

int GCD(int N, int M)
{
	if (N % M == 0)
	{
		return M;
	}
	else
	{
		return GCD(M, N % M);
	}
}

int main()
{
	int numerator, denominator, g;
	cout<<"Numerator: ";
	cin>>numerator;
	cout<<"Denominator: ";
	cin>>denominator;
	g = GCD(numerator, denominator);
	cout<<endl<<numerator / g<<" / "<<denominator / g<<endl;
	return 0;
}

This should do everything you need it to. Alturnatively you could write

(N % M == 0)?(return M):(return GCD(M, N%M))

in place of the if-else statement

[exluddite]

Well yeah, I have that one figured out. That's exactly what the whole class is doing. I just figured it'd be interesting to make this one work. They seem to suggest that it would be "easier" for a processor to use this method (less steps for it, perhaps?) but I have no idea if that's the case.

Back to the second question, is there something on the bloodshed compiler that would let me "follow" a variable (like n or m in this problem) through a bit of code?

[Hunter2]

I've heard the name 'gdb' tossed around quite a bit here, though I don't know if that's bundled with bloodshed. Alternately you could riddle your code with cout's giving the status of each variable at various stages of the program (or messageboxes in Windows API applications). If the couts go off the screen, log them to a textfile instead.