4.3.3 HOW FAST (Photoshop web design) CAN WE MULTIPLY? 285 C7.
4.3.3 HOW FAST CAN WE MULTIPLY? 285 C7. [Find Ps.] Set r + rk, q + ok, p + ok-1 + ok. (At this point stack W contains a sequence of numbers ending with W(O), W(l), . . . , W(2r) from bottom to top, where each W(j) is a 2pbit number.) Now for j = 1, 2, 3, . . . , 2r, perform the following loop: For t = 2r, 2r -1, 2r -2, . . . , j, set W(t) c (W(t) -W(t -l))/j. (Here j must increase and t must decrease. The quantity (W(t) -W(t -l))/j will always be a nonnegative integer that fits in 2p bits; cf. (15).) C8. [Find w s.] For j = 2r -1, 2r -2, . . . , 1, perform the following loop: For t=j,j+1,…,2r-l,setW(t)cW(t)-jW(t+l). (Herejmust decrease and t must increase. The result of this operation will again be a nonnegative 2pbit integer; cf. (l f).) C9. [Set answer.] Set w to the 2(ql, + qk+r)-bit integer (. . . (W(2r)29 + W(2r -1))2 +. . . + W(l))29 + W(0). Remove W(2r), . . . , W(0) from stack W. ClO. [Return.] Set k c Ic + 1. Remove the top of stack C. If it is code-3, go to step C6. If it is code-2, put w onto stack W and go to step C7. And if it is code-l, terminate the algorithm (w is the answer). 1 Let us now estimate the running time, T(n), for Algorithm C, in terms of some things we shall call cycles, i.e., elementary machine operations. Step Cl takes O(qk) cycles, even if we represent the number qk internally as a long string of qk bits followed by some delimiter, since qk + ok-1 + . . . + qo will be O(qk). Step C2 obviously takes O(qk) cycles. Now let tk denote the amount of computation required to get from step C3 to step Cl0 for a particular value of Ic (after Ic has been decreased at the beginning of step C3). Step C3 requires O(q) cycles at most. Step C4 involves r multiplications of p-bit numbers by (lg2r)-bit numbers, and r additions of pbit numbers, all repeated 4r + 2 times. Thus we need a total of O(r2qlogr) cycles. Step C5 requires moving 4r + 2 p-bit numbers, so it involves O(rq) cycles. Step C6 requires O(q) cycles, and it is done 2r + 1 times per iteration. The recursion involved when the algorithm essentially invokes itself (by returning to step C3) requires tkyl cycles, 2r + 1 times. Step Ci requires O(r2) subtractions of p-bit numbers and divisions of 2pbit by (lg 2r)-bit numbers, so it requires O(r2q log r) cycles. Similarly, step C8 requires O(r2q logr) cycles. Step C9 involves O(rq) cycles, and Cl0 takes hardly any time at all. Summing up, we have T(n) = O(qk) + O(qk) + t&-l, where (if q = qk and r = rk) the main contribution to the running time satisfies tk = o(q) + o(r2q hr) + o(v) + (2r t 1)0(q) + O(r2q 1% r) + O(r2q log r) + O(w) + O(q) + ( Jr + l)tk-1 = o(r2q logr) + (2r + l)tk-l.