Algorithms and Data Structures in C++ by Alan Parker CRC Press, CRC Press LLC ISBN: 0849371716   Pub Date: 08/01/93

4.6 Problems

(4.1)  Modify Code List 4.1 to simulate 16, 32, and 64-bit 2’s complement addition. Add a procedure to detect for overflow and indicate via output when overflow has occurred.

(4.2)  Modify Code List 4.5 to simulate a CLA adder with 3 sections each with 3 groups each with 8 1-bit adders.

(4.3)  Write a C++ program to simulate restoring division. Your program should support n bit inputs. Use the overload operators to perform addition and subtraction of each of the inputs.

(4.4)  Modify the Code List 4.13 to support n bit inputs. Use a similar register structure as the example in Figure 4.14.

(4.5)  First by example, then by proof, demonstrate the technique of shifting over 1’s and 0’s in non-restoring division.

(4.6)  Write a C++ program to simulate modify Code List 4.15 to shift over 1’s and 0’s.

(4.7)  Derive the conditions for overflow in fixed point division.

(4.8)  Add all the common logical functions to Code List 4.7.

(4.9)  Rewrite Code List 4.7 to simulate a JK Flip-Flop.

(4.10)  Calculate the average number of operations required in the Booth algorithm for 2’s complement multiplication. How does this compare to the shift-add technique?

(4.11)  Modify Code List 4.7 to simulate Carry Lookahead Addition at the gate level for an 8-bit module.

(4.12)  [Moderately Difficult] Modify Code List 4.13 to output, to a PostScript file, the timing diagram for the circuit which is simulated. Make rational assumptions about the desired interface. Use the program to generate a PostScript file for the timing diagram in Figure 4.12.

(4.13)  Graphically illustrate Newton’s method described in Eq. 4.37.

(4.14)  Theoretically demonstrate that the gcd function in Code List 4.21 does in fact return the greatest common divisor of the inputs x and y.

(4.15)  [Uniqueness] Show that if a residue number system is defined with moduli

and A and B are integers such that

and if

with

then

(4.16)  If m_i and m_j are integers satisfying

with

and

prove that if

then

(4.17)  Prove that Eq. 4.59 is true.