Euclid Algorithm

• Jan 15th 2012, 09: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 \$\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.
• Jan 15th 2012, 11:03 AM
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 \$\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).
• Jan 15th 2012, 11:21 AM
Shizaru
Re: Euclid Algorithm
Quote:

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!
• Jan 15th 2012, 11:32 AM
ILikeSerena
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?