Results 1 to 4 of 4

Math Help - Euclid Algorithm

  1. #1
    Junior Member
    Joined
    Oct 2011
    From
    United States
    Posts
    41

    Euclid Algorithm

    "Let T(n) denote the average number of integer divisions performed when using Euclid's algorithm to compute gcd(u,n) for u, n integers satisfying u \geq n > 0. Compute T(14). What is the asymptotic behaviour of T?"

    Please help. What I don't get is that we don't have a value for u in this function so I don't get what I am supposed to compute?

    "Discuss the role of Euclid algorithm in computing the sum of two rational numbers. Give two methods for determining a common denominator. Compare the computational complexity of the resulting additional algorithms?"

    I can't make heads nor tails of this. Can someone just help explain me what this means. I have no problems with calculations but I don't know what this even is.
    Last edited by Shizaru; January 15th 2012 at 09:24 AM. Reason: more to add
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Euclid Algorithm

    Quote Originally Posted by Shizaru View Post
    "Let T(n) denote the average number of integer divisions performed when using Euclid's algorithm to compute gcd(u,n) for u, n integers satisfying u \geq n > 0. Compute T(14). What is the asymptotic behaviour of T?"

    Please help. What I don't get is that we don't have a value for u in this function so I don't get what I am supposed to compute?

    "Discuss the role of Euclid algorithm in computing the sum of two rational numbers. Give two methods for determining a common denominator. Compare the computational complexity of the resulting additional algorithms?"

    I can't make heads nor tails of this. Can someone just help explain me what this means. I have no problems with calculations but I don't know what this even is.
    Welcome to MHF, Shizaru!

    Start with u=14, and work your way up to u=27.
    When you get to u=28, you should see that the number of integer divisions is the same as it is for u=14.
    So if you average the results of u=14 up to u=27, you find T(14).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2011
    From
    United States
    Posts
    41

    Re: Euclid Algorithm

    Quote Originally Posted by ILikeSerena View Post
    Welcome to MHF, Shizaru!

    Start with u=14, and work your way up to u=27.
    When you get to u=28, you should see that the number of integer divisions is the same as it is for u=14.
    So if you average the results of u=14 up to u=27, you find T(14).
    thanks! good post. so i have a finite set of values to work with, i can calculate this. thanks.

    as for my second query, a similar help would be great!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Euclid Algorithm

    To add 2 fractions optimally, you need to find the least common multiple (lcm) of the denominators.
    Alternatively you can cross multiply, add, and simplify.

    How would you find the lcm respectively the simplification?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 29th 2009, 04:54 AM
  2. Finding GCD using Euclid's algorithm
    Posted in the Number Theory Forum
    Replies: 15
    Last Post: September 23rd 2008, 06:45 PM
  3. Another GCD using Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 23rd 2008, 09:03 AM
  4. Euclid's algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 3rd 2008, 05:18 AM
  5. Euclid Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: April 10th 2008, 05:28 AM

Search Tags


/mathhelpforum @mathhelpforum