284 ARITHMETIC 4.3.3 C4. Break into Fig. 8. (Free web hosting music)
284 ARITHMETIC 4.3.3 C4. Break into Fig. 8. Toom-Cook algorithm for high-precision multiplication. C4. [Break into r + 1 parts.] Let the number at the top of stack C be regarded as a list of r + 1 numbers with q bits each, (U, . . . UrUo)a4. (The top of stack C now contains an (r + 1)q = (qk + qk+l)-bit number.) For j = 0, 17 **, 2r, compute the pbit numbers (. * f (UTj + UT-1)j + * * * + Ul)j + uo = U(j) and successively put these values onto stack U. (The bottom of stack U now contains U(O), then comes U(l), etc., with U(2r) on top. Note that U(j) 5 U(2r) < 24((2+ + (2r)+l + . * * + 1) < 24+72+ 2 2p, by exercise 3.) Then remove U, . . . UIUo from stack C. Now the top of stack C contains another list of r + 1 q-bit numbers, V7 . . . VIVi, and the pbit numbers (. . .(Kj + K-1)j + * * . + h)j + vo = V(j) should be put onto stack V in the same way. After this has been done, remove V, . . . VIVO from stack C. C5. [Recurse.] Successively put the following items onto stack C, at the same time emptying stacks U and V: code-2, V(2r), U(2r), code-3, V(2r -l), U(2r -l), . . . . code-3, V(l), U(l), code-3, V(O), U(0). Go back to step C3. C6. [Save one product.] (At this point the multiplication algorithm has set w to one of the products W(j) = U(j)V(j).) Put w onto stack W. (This number w contains 2(qk + qk-1) bits.) Go back to step C3.