Thread: please help me understand the euclids algorithm

  1. #1
    Registered User
    Join Date
    Mar 2005
    Posts
    7

    please help me understand the euclids algorithm

    i don't understand why this works:

    Code:
    int gcd(int a, int b)
    {
        if (b == 0)
            return a;
    
        return gcd(b, a % b);
    }
    so if i have the fracking 10/4 and i call gcd(10,4) it would return 2? how the hell does it work? i really don't understand this....recursion-wah?

  2. #2
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    trace it out:
    10 , 4 : 10 doesn't == 0 so we call again
    4, 2 : 2 doesn't == 0 so we call again
    2, 0 : 0 == 0 so we return 2

    http://en.wikipedia.org/wiki/Euclidean_algorithm

  3. #3
    Registered User
    Join Date
    Mar 2005
    Posts
    7
    yeah but i really don't understand HOW this works....i don't want to use this code if i don't understand it

  4. #4
    Registered User
    Join Date
    Mar 2005
    Posts
    7
    would this bit of code work????
    Code:
    int gcd (int numer, int denom)
    {
    	if (denom == 0)
    		return numer;
    	return gcd(denom,numer % denom);
    }
    
    //
    //
    //
    void reduceRational (int& numer, int& denom)
    {
    	int factor = gcd (numer, denom);
    	numer /= factor;
    	denom /= factor;
    }
    ????

  5. #5
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Did you read the link?

  6. #6
    Registered User
    Join Date
    Mar 2005
    Posts
    7
    Quote Originally Posted by Thantos
    Did you read the link?

    ya but it didn't make a whole lot of sense...what about my code?

  7. #7
    Registered User
    Join Date
    Sep 2004
    Posts
    39
    Code:
    int gcd(int a, int b)
    {
    Above is a function that takes two ints and gives them the name a and b

    Code:
        if (b == 0)
    This checks to see if b is equal to zero

    Code:
            return a;
    if b was equal to zero than return a
    Code:
        return gcd(b, a % b);
    }
    if b does not equal zero then the function calls it self over and over again until b finally equals zero

    so in the above is you called the function with the two ints 10 and 4 like so:
    Code:
    gcd(10, 4);
    it will check to see if 4 is eqaul to zero and if it is not then it recalls the function using gcd(4, 10%4) which is really gcd(4, 2) (the % finds the remainder of the two numbers). So now we repeat the same proccess. 2 does not equal zero so we do gcd(2, 4%2) which is gcd(2,0). Now that b (0) is equal to zero we return a which is 2.

    I am not sure how to explain it any easier.

  8. #8
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    the reduceRational function should work and the gcd should work. However the gcd parameter names are a little misleading since its only the numerator and the denomitor during the first call.

  9. #9
    Registered User
    Join Date
    Mar 2005
    Posts
    7
    Quote Originally Posted by Bitphire
    Code:
    int gcd(int a, int b)
    {
    Above is a function that takes two ints and gives them the name a and b

    Code:
        if (b == 0)
    This checks to see if b is equal to zero

    Code:
            return a;
    if b was equal to zero than return a
    Code:
        return gcd(b, a % b);
    }
    if b does not equal zero then the function calls it self over and over again until b finally equals zero

    so in the above is you called the function with the two ints 10 and 4 like so:
    Code:
    gcd(10, 4);
    it will check to see if 4 is eqaul to zero and if it is not then it recalls the function using gcd(4, 10%4) which is really gcd(4, 2) (the % finds the remainder of the two numbers). So now we repeat the same proccess. 2 does not equal zero so we do gcd(2, 4%2) which is gcd(2,0). Now that b (0) is equal to zero we return a which is 2.

    I am not sure how to explain it any easier.
    i understand HOW the function actually goes about working

    i don't understand WHY it works...WHY does calling itself over and over get you the gcd????????????\





    what about my code? does that work?

  10. #10
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    Maybe think of it like this:
    Code:
    int gcd1(int a, int b)
    {
        if (b == 0)
            return a;
        int x = gcd2(b, a % b);
        return x; 
    }
    
    int gcd2(int a, int b)
    {
        if (b == 0)
            return a;
        in y = gcd3(b, a % b);
        return y;
    }
    int gcd3(int a, int b)
    {
        if (b == 0)
            return a;
    
       }
    Last edited by 7stud; 03-02-2005 at 08:47 PM.

  11. #11
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    try using the non recursive version and see if that helps you understand it better.

    Note this is a very old algoirthm created by a freakin genius.
    The proof for this may be outside of your comprehension.

  12. #12
    Registered User
    Join Date
    Mar 2005
    Posts
    7
    Quote Originally Posted by Thantos
    try using the non recursive version and see if that helps you understand it better.

    Note this is a very old algoirthm created by a freakin genius.
    The proof for this may be outside of your comprehension.
    ouch. try me.

  13. #13
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    i don't understand WHY it works...WHY does calling itself over and over get you the gcd
    Then why did you post any code?

  14. #14
    Registered User
    Join Date
    Mar 2005
    Posts
    7
    i dunno...i just wanna know how this works so when my teacher asks me im not all "well i got it off the internet"

  15. #15

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 11-13-2005, 02: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. Binary Euclid's Algorithm
    By exluddite in forum C++ Programming
    Replies: 7
    Last Post: 09-26-2004, 08:08 PM
  4. Euclid's algorithm
    By Unregistered in forum C Programming
    Replies: 7
    Last Post: 10-03-2001, 10:59 PM