# Euclid Algorithm

• Jan 15th 2012, 10:20 AM
Shizaru
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.
• Jan 15th 2012, 12:03 PM
ILikeSerena
Re: Euclid Algorithm
Quote:

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 $\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! :)

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).
• Jan 15th 2012, 12:21 PM
Shizaru
Re: Euclid Algorithm
Quote:

Originally Posted by ILikeSerena
Welcome to MHF, Shizaru! :)