13. Consider the problem of generating constants ,for an RTM system. Make a study of this problem in the manner of this chapter.

14. Do a study in the manner of this chapter on the problem of computation versus control flow for realizing Boolean functions, as illustrated in Figure 34. Be sure to estimate the cost and speed of the obvious ways to do the task, as a basis for comparison.

15. (A) Add a multiply instruction to the Crtm-1 computer of Chapter 6 so that. giving one instruction carries out the operation. (B) Add a multiply-step (i.e., an add an shift) and evaluate it against the other systems.

16. (A) Write down a process for converting an RTM system to a Fortran program for simulation. Carry out this conversion process for the various schemes in this chapter. (B) What must be true of the Fortran system so that the simulation is possible?

17. Unwind the control of the RP algorithm and evaluate it.

18. Checking the RTM System (Part 2). The problem is to check the actual system exhaustively. The difficulty is that there is no obvious way to know whether a given multiplication 4s right except by comparing it to a true source. One solution that .might have been suggested is to tie the system to a computer and use the computer (which presumably has a true multiply) to compare. This is a good solution, if an interface is available, and a terrible solution if not. A second solution that might have been suggested is to create two multipliers, say the 8-step and the RP, and play them against each other. If they are in error at least it will be in the same way! This is a reasonable solution, though inelegant and clearly not fool-proof. A third solution, and the one we recommend comes from considering the identity:

If this is not zero, then there must be an error in the multiplier. Now do this, over all values of A and B that lead to legal products (since A+B must be less than 2^8). In this manner every product gets executed at least once and checked. (A) Design such a tester to exhaustively check the multipliers in this chapter. (B) Does this scheme guarantee that the multiplier is correct? (C) If not, what is the difficulty and can you fix it? (D) Does this whole exercise suggest a general way to test certain systems? What is it? (E) Can you list some other functions which might be checked this way? Some others that seem to you unlikely? (F) How do you know that your tester is correct?

19. Algorithms for Multiplication. Consider the identity used in Problem 12:

(A) Can this be used to design a multiplier? (B) Do so.

20. In this chapter we have not considered one of the simplest of all multiplication algorithms. This simply consists of adding the multiplicand to itself a number of times that is equal to the multiplier. Design a minimal cost RTM system to implement this algorithm.

161