Binary Euclid's Algorithm

• 09-25-2004
exluddite
Binary Euclid's Algorithm
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:

Code:

```#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
• 09-25-2004
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....
• 09-25-2004
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.
• 09-25-2004
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.
• 09-25-2004
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.
• 09-26-2004
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:

Code:

```#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
Code:

`(N % M == 0)?(return M):(return GCD(M, N%M))`
in place of the if-else statement
• 09-26-2004
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?
• 09-26-2004
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.