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.

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

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用