2. Now we consider a division algorithm in the context of the preceding problem. We assume that a and b are positive integers. The goal is to compute the digits of q 0 and 0 r < b, satisfying a = qb + r. Here and in what follows, unless otherwise specied, all variables are integer variables. The algorithm we are going to build is an adaptation of the usual long division algorithm we study in school. Recall that n = max{k : ak = 0}, m = max{k : bk = 0}. Without loss of generality, we can assume n m and a > b 2. As a warm up, let us treat the special case m = 0 rst. In this case, b has only one digit, i.e., 2 b 1, so division can be performed in a straightforward digit-by-digit fashion. Thus the rst step of the division algorithm would be to divide an by b, as an = qn b + rn , where 0 rn < b is the remainder, and qn 0 is the quotient. Obviously, qn 1 because an 1. Computation of qn and rn should be performed in computer's built-in arithmetic. To proceed further, we combine rn with the (n 1)-st digit of a, and divide it by b, that is, rn + an1 = qn1 b + rn1 , where 0 rn1 < b. Since rn < b, we are guaranteed that qn1 1. Computation of qn1 and rn1 should be performed in computer's built-in arithmetic, which imposes an upper bound on . This procedure is repeated until we retrieve the last digit a0 , and we nally get a = an n + . . . + a0 = (qn b + rn ) n + an1 n1 + . . . + a0 = qn b n + (rn + an1 ) n1 + . . . + a0 = qn b n + (qn1 b + rn1 ) n1 + . . . + a0 = . . . = qn b n + qn1 b n1 + . . . + q0 b + r0 (3) n qk k + r0 , =b k=0 which shows that qk is the k-th digit of q, and that r = r0 . In the general case m > 0, the overall structure of the algorithm does not change, but there will be one essential new ingredient in the details. Before describing the algorithm, let us introduce a convenient new notation. For 0 k let a[k, ] = ak + ak+1 + . . . + a k , which is simply the number consisting of those digits of a that are numbered by k, . . . , . For example, when = 10 and a = 1532, we have a[2,4] = 15. The rst step of our algorithm is to compute qnm and 0 rnm < b satisfying a[nm,n] = qnm b + rnm . (4) Since the number of digits of a[nm,n] is the same as that of b, we have qnm 1. Next, we compute qnm1 and 0 rnm1 < b satisfying rnm + anm1 = qnm1 b + rnm1 . (5) Since rnm < b, we are guaranteed that qnm1 1. We repeat this process until we retrieve the last digit a0 , and expect that qk 's give the digits of q. This seems all well and good, except that there is a catch: In (4) and (5), we divide by b, which has m + 1 digits, and we cannot rely on the built-in arithmetic since m can be large. We encounter the divisions (4) and (5) in each step of the paper-and-pencil long division method. There, what helps is intuition and the fact that in practice we usually have m not too large. Here, we need to replace intuition by a well dened algorithm. We shall consider here an approach that is based on a few crucial observations. The rst observation is that since rnm < b and anm1 < , we have rnm + anm1 (b 1) + 1 = b 1, so that the left hand side of (5) has at most m + 2 digits. Noting that the left hand side of (4) has m + 1 digits, we now see that (4) and (5) only require divisions of a number with m + 1 or m + 2 digits by a number with m + 1 digits. In other words, the original division problem a/b has been reduced to the case m n m + 1. This indeed helps, because if two numbers have roughly the same number of digits, then the rst few digits of both numbers can be used to compute a very good approximation of the quotient. For instance, it turns out that under the assumption m n m + 1, if a[m1,n] = q b[m1,m] + r , (6) with 0 r < b[m1,m] , then q q q + 1. (7) This means that the quotient of the number formed by the rst 2 or 3 digits of a, divided by the number formed by the rst 2 digits of b, is either equal to the quotient q of a divided by b, or o by 1. The cases q = q + 1 can easily be detected (and immediately corrected) by comparing the product q b with a. The division (6) can be performed in the built-in arithmetic, because the number of digits of any of the operands therein does not exceed 3. (a) Assuming that we have some means to carry out the divisions (4) and (5), demonstrate the correctness of the algorithm, that is, show that nm qk k . a = r0 + b k=0 (b) Now let us focus on the divisions (4) and (5), that would occur in each iteration of the general division algorithm. Assume that m n m + 1, and x some (small) integer p 0. Let q and 0 r < b[mp,m] be dened by a[mp,n] = q b[mp,m] + r . (8) Derive upper and lower bounds on q in terms of q. Then by using these bounds, show that q q q + 1, (9) as long as p 1. (c) Describe a procedure to identify q, given that we have computed q as in (b) with p = 1. In particular, how do we tell q = q or q = q + 1? (d) What would be the maximum value of that allows the division algorithm to work correctly, supposing that we want to be a power of 10, and that the built-in arithmetic can handle 64 bit integers