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

Previous Table of Contents Next


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 mi and mj are integers satisfying

with

and

prove that if

then

(4.17)  Prove that Eq. 4.59 is true.


Previous Table of Contents Next

Copyright © CRC Press LLC