Winter 2004 UCLA CS 31 (Shinnerl)

This project is just the original, unabridged version of Project 4, except that the final implementations of multiplication and division must be done without conversion to floating point, as described below. (You may, however, use conversion to floating-point in your prototype solution (Project 5) without penalty.)

The minimum requirements of the prototype solution (Project 5) are the following.

1. It must provide an implementation of multiplication and division that works in most cases, and you must specify what those cases are. The prototype may simply convert to floating-point, do the operation, then convert back to fixed point, just as was discussed in Project 4.
2. It must handle both binary format and at least one other format, either decimal or hexadecimal, for all operations.

I. Overview

Overflow occurs when the absolute value of the number is too large for the number of integer bits available to represent its integer part. Underflow occurs when the number is too close to zero for the number of fraction bits available to represent its fractional part. Both overflow and underflow are possible for both positive and negative numbers.

Implement a program to simulate a binary, fixed-point calculator of user-specified precision, up to a maximum of 64 binary digits each for the integer and fractional number fields. Support simple addition, subtraction, multiplication, and division of both nonnegative and negative numbers.

II. Details

1. All input to the program must be assumed to be in fixed-point binary format of the requested precision, with binary point separating integer and fractional parts, unless, optionally, the user switches to hexadecimal mode, in which case, the input is in fixed-point hexadecimal format. Examples are given above (binary) and below (hex).
2. When the user enters 'd' for decimal mode, his/her input will still be in either binary or hex, and the calculator works the same as before. However, in this mode, all binary (or hex.) output is accompanied by the equivalent decimal values and the suffix dec, both in parentheses. E.g.,

                    00011.01000    (    3.250  dec )
                +   01010.01100    (   10.375  dec )
                =   01101.10100    (   13.625  dec )
   

   Conversion from binary (or hex.) to decimal can always be done exactly.
3. Perform addition and subtraction exactly, in binary, on the given bit sequences, reporting overflow whenever it occurs.

4. Perform multiplication as follows.
   1. Let a_i denote a_i and let 2^i denote 2ⁱ. Think of the product of two fixed-point numbers a and b as a product of polynomials, e.g.,

      a * b =   (a_p 2^p + a_{p-1} 2^{p-1} + ... + a_{1-p} 2^{1-p} + a_{-p} 2^{-p} )
              * (b_p 2^p + b_{p-1} 2^{p-1} + ... + b_{1-p} 2^{1-p} + b_{-p} 2^{-p} )
      
            =    c_{2p}2^{2p} + c_{2p-1}2^{2p-1} + ... + c_{-2p}2^{-2p} ,
      

      where the coefficients a_i, b_j, and c_k are all just bits (0 or 1).
   2. It is easy to verify that the formula for any coefficient c_i is a so-called "convolution" of the coefficients of a and b:

         c_i  = sum_j  a_{i-j} b_j,
      

      where the sum is over j = -p, -p+1, ..., p-1, p, and we let a_k = b_k = 0 when k is not between -p and p.
   3. Note that if c_i is nonzero for any i > p, then overflow occurs. But otherwise, the product can be approximated in fixed point.
   4. If overflow occurs, issue an error message. Do not issue error messages for underflow in intermediate steps, but do issue an error message if the most significant digit of the final product is too small to represent in fixed point.

5. Perform division a/b of fixed-point numbers a and b by multiplying a by 1/b. Use Newton's method and your multiplication function to compute 1/b. Newton's method will be discussed in lecture and discussion. Your division function should return a value irrespective of whether underflow occurs in one of its intermediate steps. If overflow occurs, then issue an error message.

6. For simplicity, always give the integer field and the fraction field of any fixed-point value the same number of bits. This number will be called the precision of the representation and is provided by the user at start-up.
7. Use C-style strings to represent binary fixed-point values.
8. There is no reason to explicitly store the binary point, so don't.
9. Remember that converting between binary (base 2) and hexadecimal (base 16) is easy: every 4 binary digits correspond to exactly one hexadecimal digit (0,1,...,9,a,b,c,d,e,f). E.g., the hexadecimal representation of the binary number 11 0011 1010 1001.0111 1101 0110 0000 is just 33a9.7d60.
10. For convenience, always output binary digits in 4-digit chunks separated by spaces, as in the preceding example. Similarly, ignore spaces between digits in user input.
11. The program runs as follows.

          Print a short menu explaining how to operate the program.
          Request and read in the user's requested number of digits 
             (precision) for each number's integer and fraction fields.
          Request and read in a numerical value, x,
          as a binary fixed-point number.
    
          REPEAT
             
             Prompt for and read in an operator (q,m,c,p,h,b,d,+,-,*, or /).
             The prompt may be simply a list of possible inputs: qmcphbd+-*/>.
             If      the operator is a 'q' or 'Q', terminate execution (quit).
             Else If the operator is an 'm', redisplay the short menu 
                     explaining how to operate the program.
             Else If the operator is a 'c', (re)set x to zero. 
             Else If the operator is a 'p', read in a new precision 
                     and reset all current data values to the new precision.
             Else If the operator is an 'h', switch to hexadecimal I/O format.
             Else If the operator is an 'b', switch (back) to binary I/O format.
             Else If the operator is a 'd', print decimal approximations alongside
                     all binary values until 'd' is reentered ('d' is a toggle).
             Else    display an appropriate error message and continue.
    
             Request and read in a second numerical value, y,
             as a binary fixed-point number.
    
             Perform the indicated binary operation and overwrite
               x by its value, displaying the result to the screen
               as a complete calculation:
               
                                <x-value> 
                   <operator>   <y-value> 
                             =  <new-x-value> 
               
          UNTIL DONE
    

12. OPTIONALLY, you may enable a separate fixed-point decimal mode (command 'D') which accepts fixed-point decimal input. This extension is not required but may be useful for debugging. Note that conversion from decimal to binary typically incurs rounding error, because the binary expansion of one tenth does not terminate.

III. Sample I/O