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 + \lg q) \lg b)$ bit operations.

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

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

a.

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

b.

$$ \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. $\mu(a, b) = (1 + \lg a)(1 + \lg b) \approx \beta^2$