4.3.3 HOW FAST CAN WE MULTIPLY? (Web site construction) 283 Algorithm
4.3.3 HOW FAST CAN WE MULTIPLY? 283 Algorithm C (High-precision multiplication of binary numbers). Given a positive integer n and two nonnegative n-bit integers u and 21, this algorithm forms their 2n-bit product, 20. Four auxiliary stacks are used to hold the long numbers that are manipulated during the procedure: Stacks U, V: Temporary storage of U(j) and V(j) in step C4. Stack C: Numbers to be multiplied, and control codes. Stack W: Storage of W(j). These stacks may contain either binary numbers or special control symbols called code-l, code-a, and code-3. The algorithm also constructs an auxiliary table of numbers qk, rk; this table is maintained in such a manner that it may be stored as a linear list, where a single pointer that traverses the list (moving back and forth) may be used to access the current table entry of interest. (Stacks C and W are used to control the recursive mechanism of this multi- plication algorithm in a reasonably straightforward manner that is a special case of general procedures discussed in Chapter 8.) Cl. [Compute 4, r tables.] Set stacks U, V, C, and W empty. Set k c 1, qo + 41 + 16, ro t r1 t 4, Q + 4, R + 2. Now if qk-1 + qk < n, set kcIc+l, Q+Q+R R+lJ&], qkCsQ, rktsR, and repeat this operation Until q-1 + qk 2 n. (iVOi%: The CdCUkttiOU of R t [flj does not require a square root to be taken, since we may simply set R +- R + 1 if (R + 1)2 5 Q and leave R unchanged if (R + 1)2 > Q; see exercise 2. In this step we build the sequences k=O 1 2 3 4 5 6 . . . qk = 24 24 26 2 210 213 216 rk = 22 22 22 22 23 23 24 1:: The multiplication of 70000-bit numbers would cause this step to terminate with k = 6, since 70000 < 213 + 216.) C2. [Put U, v on stack.] Put code-l on stack C, then place u and v onto stack C as numbers of exactly q&l + qk bits each. C3. [Check recursion level.] Decrease k by 1. If k = 0, the top of stack C now contains two 32-bit numbers, u and v; remove them, set w +-uv using a built-in routine for multiplying 32-bit numbers, and go to step ClO. If k > 0, Set 7 + ?-k, g + qk, p +- qk-1 + qk, and g0 Oil t0 Step c4.