Featured Post

Có một Biển Đông trên không gian mạng

Có một Biển Đông trên không gian mạng Thái Dương Mùa hè 2014, giữa lúc người Việt trong nước và hải ngoại đang sôi sục vì Trung Quốc đư...

Sunday, July 26, 2009

Solutions manual for NTB - 3.3. Basic integer arithmetic

Let's review some notations and facts. For an integer , we define its bit length, or simply, its length, which we denote by , to be the number of bits in the binary representation of ; more precisely,



If , we say that is an -bit integer. Notice that if is a positive, -bit integer, then , or equivalently, .

Let a and b be arbitrary integers. Then we have:

(i) We can compute in time .

(ii) We can compute in time .

Let a and b be arbitrary integers. Then we have:

(i) We can compute in time .

(ii) We can compute in time .

(iii) If , we can compute the quotient and the remainder in time .



Exercise 3.24. Let with , and let . Show that:



Proof

If you look at the
list of errata, you'll see that I found a stronger version of this exercise. My proof is as following.

We see that . Hence what we need to prove is:



which is the same as proving:

for some

which in turn can be proved by using this fact:

for all .

(q.e.d.)



Exercise 3.25. Let be postivie integers. Show that:



Proof

As in Exercise 3.24, I think I found a slightly better version of this exercise as follows:



We can prove it using the same technique as the proof of Exercise 3.24. We see that:

,

,



Since we have for all , we see that:



and,

.

(q.e.d.)



Exercise 3.26. Show that given integers , with each , we can compute the product in time .

Proof

(q.e.d.)



Exercise 3.27. Show that given integers , with each , where , we can compute in time .

Proof

(q.e.d.)



Exercise 3.28. Show that given integers , with each , we can compute , where , in time .

Proof

(q.e.d.)



Exercise 3.29. This exercise develops an algorithm to compute for a given positive integer . Consider the following algorithm:







(a) Show that this algorithm correctly computes .

(b) In a straightforward implementation of this algorithm, each loop iteration takes time , yielding a total running time of . Give a more careful implementation, so that each loop iteration takes time , yielding a total running time is .

Proof

(q.e.d.)



Exercise 3.30. Modify the algorithm in the previous exercise so that given positive integers and , with , it computes in time .

Proof

(q.e.d.)



Exercise 3.31. An integer is called a perfect power if for some integers and . Using the algorithm from the previous exercis, design an efficient algorithm that determines if a given is perfect power, and if it is, also computes and such that , where , , and is as small as possible. Your algorithm should run in time where .

Proof

(q.e.d.)



Exercise 3.32. Show how to convert (in both directions) in time between the base-10 representation and our implementation's internal representation of an integer .

Proof

(q.e.d.)