31-2 Analysis of bit operations in Euclid's algorithm

a. Consider the ordinary "paper and pencil" algorithm for long division: dividing aa by bb, which yields a quotient qq and remainder rr. Show that this method requires O((1+lgq)lgb)O((1 + \lg q) \lg b) bit operations.

b. Define μ(a,b)=(1+lga)(1+lgb)\mu(a, b) = (1 + \lg a)(1 + \lg b). Show that the number of bit operations performed by EUCLID\text{EUCLID} in reducing the problem of computing gcd(a,b)\gcd(a, b) to that of computing gcd(b,amod  b)\gcd(b, a \mod b) is at most c(μ(a,b)μ(b,amod  b))c(\mu(a, b) - \mu(b, a \mod b)) for some sufficiently large constant c>0c > 0.

c. Show that EUCLID(a,b)\text{EUCLID}(a, b) requires O(μ(a,b))O(\mu(a, b)) bit operations in general and O(β2)O(\beta^2) bit operations when applied to two β\beta-bit inputs.

a.

  • Number of comparisons and subtractions: lgalgb+1=lgq\lceil \lg a \rceil - \lceil \lg b \rceil + 1 = \lceil \lg q \rceil.
  • Length of subtraction: lgb\lceil \lg b \rceil.
  • Total: O((1+lgq)lgb)O((1 + \lg q) \lg b).

b.

μ(a,b)μ(b,amod  b)=μ(a,b)μ(b,r)=(1+lga)(1+lgb)(1+lgb)(1+lgr)=(1+lgb)(lgalgr)(lgrlgb)(1+lgb)(lgalgb)=(1+lgb)(lgq+1)(1+lgq)lgb \begin{array}{rlll} & \mu(a, b) - \mu(b, a \mod b) \\ = & \mu(a, b) - \mu(b, r) \\ = & (1 + \lg a)(1 + \lg b) - (1 + \lg b)(1 + \lg r) \\ = & (1 + \lg b)(\lg a - \lg r) & (\lg r \le \lg b) \\ \ge & (1 + \lg b)(\lg a - \lg b) \\ = & (1 + \lg b)(\lg q + 1) \\ \ge & (1 + \lg q) \lg b \end{array}

c. μ(a,b)=(1+lga)(1+lgb)β2\mu(a, b) = (1 + \lg a)(1 + \lg b) \approx \beta^2