# Thread: Euclid Algorithm

1. ## 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 $\displaystyle \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.

2. ## Re: Euclid Algorithm

Originally Posted by Shizaru
"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 $\displaystyle \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).

3. ## Re: Euclid Algorithm

Originally Posted by ILikeSerena
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!

4. ## 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?