31-2 Analysis of bit operations in Euclid's algorithm
a. Consider the ordinary "paper and pencil" algorithm for long division: dividing a by b, which yields a quotient q and remainder r. Show that this method requires O((1+lgq)lgb) bit operations.
b. Define μ(a,b)=(1+lga)(1+lgb). Show that the number of bit operations performed by EUCLID in reducing the problem of computing gcd(a,b) to that of computing gcd(b,amodb) is at most c(μ(a,b)−μ(b,amodb)) for some sufficiently large constant c>0.
c. Show that EUCLID(a,b) requires O(μ(a,b)) bit operations in general and O(β2) bit operations when applied to two β-bit inputs.
a.
- Number of comparisons and subtractions: ⌈lga⌉−⌈lgb⌉+1=⌈lgq⌉.
- Length of subtraction: ⌈lgb⌉.
- Total: O((1+lgq)lgb).
b.
===≥=≥μ(a,b)−μ(b,amodb)μ(a,b)−μ(b,r)(1+lga)(1+lgb)−(1+lgb)(1+lgr)(1+lgb)(lga−lgr)(1+lgb)(lga−lgb)(1+lgb)(lgq+1)(1+lgq)lgb(lgr≤lgb)
c. μ(a,b)=(1+lga)(1+lgb)≈β2