Computer Science 3675
Fall 2003
Programming Assignment 1

Due: Wed Sep 17, 11:59pm.

Arithmetic on large integers can be done by storing an integer in an array, in binary notation. Each member of the array is either 0 or 1. Functions can be written to perform operations such as addition, subtraction and multiplication.

Functions

Write an implementation of increment, addition and multiplication of nonnegative integers, stored in binary, in C++. Make your functions have the following contracts and prototypes.

  //  -----------------------------------------------------------
  // |The following comments apply to all of the functions below.|
  //  -----------------------------------------------------------
  //
  // All integers are stored in binary as arrays of bits, with the least
  // significant bit stored at index 0.
  //
  // Array A has m bits.
  // Array B has n bits.
  //
  // It is the caller's responsibility to ensure that array R 
  // has enough cells available to hold the answer.  The number
  // required is given for each function.  
  //
  // Variable Rsize is set to hold the number of bits that are actually
  // in array R, not counting leading 0 bits.  For example, if
  // R contains 01101 (from high to low index), 
  // then its length is 4, since the leading 0 (in R[4])
  // is ignored.  If all members of R are 0, then the length is 0.  Rsize is
  // strictly an out parameter.  Its value on entry to the function is
  // not used.
  //  
  // For inc and sum, it is allowed for arrays R and A to be the 
  // same array, or for R to be a different array.  When R and A are the same
  // array, the result is put into array A,
  // clobbering the former contents of A.

  //=================================================================
  // inc(R,Rsize,A,m) stores one larger than the binary number in A into
  // array R.  That is, it computes R = A + 1 in binary.
  //
  // Array R must have at least m+1 cells available.
  //=================================================================

  void inc(BIT R[], int& Rsize, const BIT A[], int m);

  //=================================================================
  // sum(R,Rsize,A,m,B,n) stores the sum of integers A and B
  // into array R.  That is, it computes R = A + B.
  //
  // Array R must have at least max(m,n) + 1
  // cells available.  Those cells are set to hold the
  // binary sum of A and B
  //=================================================================

  void sum(BIT R[], int& Rsize, const BIT A[], int m, const BIT B[], int n);

  //=================================================================
  // product(R,Rsize,A,m,B,n) stores the product of integers A and B into
  // array R.  That is, it computes R = A * B.
  //
  // Array R must have at least m+n cells available.  Those
  // bits are set to the product of A and B.
  //
  // Arrays A, B and C must be different arrays for this function.
  //=================================================================

  void product(BIT R[], int& Rsize, const BIT A[], int m, const BIT B[], int n);

  typedef int BIT;

Requirements

You are not asked to write a complete application here. Only three functions are to be provided. They are for use in other programs. I will test them by using them in another program.

For ease of grading, call your implementation file arithmetic.cc and your header file arithmetic.h. Do not include a main function in arithmetic.cc.

Your functions should meet the following requirements. (And yes, I will grade down for failure to meet these requirements, even if you have not been asked to meet such stringent requirements in the past.)

1. Your functions must have exactly the prototypes shown. If they do not, they will not link with my tester.

2. Your functions must not make any assumptions about how large the arrays are, other than those explicitly stated in the contracts. For example, it is unacceptable to assume that the numbers have no more than 100 bits in them. It must be possible to compile your functions and put them into a library, and find that they can be used for arbitrarily large integers without recompiling them.

3. Your functions must not have requirements that are not stated in the contracts. For example, it is unacceptable to insist that array C be set to all zeros by the caller before calling sum or product, since the contract does not say anything about that.

4. Your functions must not have any visible actions not stated in the contracts. For example, the contracts do not indicate that anything is being read or written, so nothing should be read or written. (Don't use cin or cout, for example.) The contract for multiplication does not state that arrays A and B are changed, so don't change them. (You can't, since they are constant.)

5. Your functions must implement something close to the standard addition and multiplication algorithms. It is not acceptable, for example, to add x and y by starting at x and doing y increments. That is extremely slow. Similarly, it is not acceptable to multiply x and y by adding y to itself x times. That is also too slow.

   The multiplication algorithm that you learned in grade shool has you write down all of the intermediate products before adding them all up. It is not necessary to do that. Just accumulate the sum as you generate each intermediate product. Be sure to shift over an appropriate amount.

6. Strive for simplicity and elegance in your program. This is important, since you will be comparing your solution in C++ to another form of solution.

7. Comment your program well. Make it clear and readable. Literate programming is a form of programming where programs are written in a way that is intended to be read, as a textbook would be read. Get as close to literate programming as you can. Write your program for other people to read. Include the given contracts in your program.

If you feel that these requirements are impossible to meet, or you do not see how to meet them, ask for help.

Testing the functions

Test your functions. In order to do the testing, you will want a function that prints a binary number. That is not part of the assignment, and should not be turned in, but software designers often find that they need to write extra functions to aid in testing.

IF YOU DO NOT TEST YOUR FUNCTIONS, YOU CAN REST ASSURED THAT THEY DO NOT WORK, AND THEY WILL FARE POORLY WHEN GRADED. TEST THEM THOROUGHLY. DO NOT BE SATISFIED WITH ONE OR TWO TESTS.

Here are some recommended tests. You would be well advised to do others as well. All numbers are in standard binary notation (high order bit first). (x means times.)

1. 0 + 0 = 0
2. 0 x 0 = 0
3. 1 + 1 = 10
4. 1 x 1 = 1
5. 10 + 11 = 101
6. 10 x 11 = 110
7. 101001 + 101111100 = 110100101
8. 101111100 + 101001 = 110100101
9. 101111100 x 101001 = 11110011011100
10. 111111 + 111111111111 = 1000000111110
11. 111111111111 + 111111 = 1000000111110
12. 111111 x 111111111111 = 111110111111000001
13. 111111111111 x 111111 = 111110111111000001

An easy way to do these tests is just to initialize some arrays in your program. For example, write

    BIT A3[] = {1,0,0,1,0,1};
    BIT B3[] = {0,0,1,1,1,1,1,0,1};

How to turn in the assignment

To turn in your assignment, log into one of the Unix machines in the lab. Issue the following commands.

  alias handin3675="~cs3675-001_fall2003/bin/handin cs3675-001_fall2003"
  handin3675 1 arithmetic.cc

You will find it convenient to copy the alias line into your .bash_profile file. That way, you will not need to type it every time.