### 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 .

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 .

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,

.

(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 .

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 .

**Let with , and let . Show that:**__Exercise 3.24.__*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.)***Let be postivie integers. Show that:**__Exercise 3.25.__*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.)***Show that given integers , with each , we can compute the product in time .**__Exercise 3.26.__*Proof**(q.e.d.)***Show that given integers , with each , where , we can compute in time .**__Exercise 3.27.__*Proof**(q.e.d.)***Show that given integers , with each , we can compute , where , in time .**__Exercise 3.28.__*Proof**(q.e.d.)***This exercise develops an algorithm to compute for a given positive integer . Consider the following algorithm:**__Exercise 3.29.__(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.)***Modify the algorithm in the previous exercise so that given positive integers and , with , it computes in time .**__Exercise 3.30.__*Proof**(q.e.d.)***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 .**__Exercise 3.31.__*Proof**(q.e.d.)***Show how to convert (in both directions) in time between the base-10 representation and our implementation's internal representation of an integer .**__Exercise 3.32.__*Proof**(q.e.d.)*