Computer Science 3675
Summer 1999
Programming Assignment 1

Functions

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

  // sum(A,m,B,n,C,k) stores the sum of integers A and B into array C.
  //
  //   All integers are stored as arrays of bits, with the least
  //   significant bit stored at index 0.
  //
  //   Array A has length m.
  //   Array B has length n.
  //   Array C must have at least n+1 cells available.
  //   Parameter k is an out-parameter, and it is set to the number of
  //   bits in C.

  void sum(BIT A[], int m, BIT B[], int n, BIT C[], int& k);

  // product(A,m,B,n,C,k) stores the product of integers A and B into
  // array C.
  //
  //   All integers are stored as arrays of bits, with the least
  //   significant bit stored at index 0.
  //
  //   Array A has length m.
  //   Array B has length n.
  //   Array C must have at least m+n cells available.
  //   Parameter k is an out-parameter, and it is set to the number of
  //   bits in C.

  void product(BIT A[], int m, BIT B[], int n, BIT C[], int& k);

  typedef char BIT;

Requirements

1. Your functions should not make any assumptions about how large the arrays are. 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.

2. 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. You will find it convenient if you design a helper addition function that computes x*2^z + y, where x and y are integers stored in arrays and z is a nonnegative integer (just an int) giving the amount to shift x to the left before adding. That function can be used to perform addition (by setting z = 0) and as a tool for doing multiplication.

3. Strive for simplicity and elegance in your program.

Testing the functions

1. Sum and product of 0 and 0.
2. Sum and product of 1 and 1.
3. Sum and product of 101001 and 101111100.
4. Sum and product of 111111 and 111111111111.

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};

Print the numbers, along with their sum and product. Print them in standard form, with the least significant bit at the right side. Check the answers!!!

Keeping track of time

1. Time spent learning the language. If you are familiar with C++, this will probably be 0.

2. Time spent developing and writing the program. Count time spent thinking about how to write it.

3. Time spent testing and debugging. Include time spent getting out compile errors, checking test results, finding errors in your program, etc.

Report time spent actually working on the problem, not counting time in between work sessions where you are doing something else.

What to turn in

3675 Assn 1 your name

The body of the email message should report your account of time spent, in hours. For example,

           Learning language: 0 hr
           Development:       2.5 hr
           Debugging/testing: 1.3 hr