Binary Euclid's Algorithm

This is a discussion on Binary Euclid's Algorithm within the C++ Programming forums, part of the General Programming Boards category; Hi folks. My class is working on the whole fraction thing, which of course involves reducing. I found something interesting ...

  1. #1
    Registered User
    Join Date
    Apr 2004
    Posts
    100

    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

  2. #2
    Software Developer jverkoey's Avatar
    Join Date
    Feb 2003
    Location
    University of Waterloo
    Posts
    1,903
    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....

  3. #3
    Registered User
    Join Date
    Apr 2004
    Posts
    100
    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.

  4. #4
    Software Developer jverkoey's Avatar
    Join Date
    Feb 2003
    Location
    University of Waterloo
    Posts
    1,903
    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.

  5. #5
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

  6. #6
    Registered User
    Join Date
    Sep 2004
    Posts
    2
    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
    Last edited by Kletian; 09-26-2004 at 02:44 AM.

  7. #7
    Registered User
    Join Date
    Apr 2004
    Posts
    100
    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?

  8. #8
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    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.
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 11-13-2005, 01:53 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21