Computer Science 3675
Fall 2000
Programming Assignment 1

Assigned: 8/21/00
Due: 9/1/00, 11pm

Arithmetic on large integers can be done by storing an integer in an array, in binary notation. So 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 addition, subtraction and multiplication of nonnegative integers, stored in binary, in C++. Make your functions have the following contracts and prototypes. 

  // sum(A,m,B,n,C) stores the sum of integers A and B into array C.
  //
  //   All integers are stored in binary as arrays of bits, with the least
  //   significant bit stored at index 0.  Each value in each array
  //   is either 0 or 1.
  //
  //   Array A has length m.
  //   Array B has length n.
  //
  //   If k = max(m,n), then array C must have at least k+1
  //   cells available.  Those k+1 cells are set to hold the
  //   binary sum of A and B.

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

  // difference(A,m,B,n,C) stores the difference A - B of integers 
  // A and B into array C.
  //
  // It is required that A >= B, and m >= n.
  //
  //   All integers are stored in binary as arrays of bits, with the least
  //   significant bit stored at index 0.  Each value in each array
  //   is either 0 or 1.
  //
  //   Array A has length m.
  //   Array B has length n.
  //
  //   Array C must have at least m cells available.  
  /    Those m cells are set to hold the binary difference A - B.

  void difference(BIT A[], int m, BIT B[], int n, BIT C[]);

  // product(A,m,B,n,C) stores the product of integers A and B into
  // array C.
  //
  //   All integers are stored in binary as arrays of bits, with the least
  //   significant bit stored at index 0.  Each value in each array
  //   is either 0 or 1.
  //
  //   Array A has length m.
  //   Array B has length n.
  //
  //   Array C must have at least m+n cells available.  Those m+n
  //   bits are set to the product of A and B.

  void product(BIT A[], int m, BIT B[], int n, BIT C[]);
For type BIT, use int. So you should write 
  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.

Your program 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. 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, difference or product.

  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.)

  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, 10+5 = 10 + 1 + 1 + 1 + 1 + 1.) 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 addition algorithm involves carries, and the subtraction algorithm involves borrows. If you like, you can treat subtraction similarly to addition, but carry a -1. That simplifies it.

    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 might 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. You can feel free to write any desired helper functions, as long as the required two functions are present.

    (By 2^z I mean 2 to the z power. Multiplying by 2^z is the same as adding z zeros to the right end of a binary number, just as multiplying by 10^z is the same as adding z zeros to the end of a decimal number.)

  6. Strive for simplicity and elegance in your program.

  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.
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.

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). You might get leading zeros, which you can ignore. For example, you might find that the sum of 1 and 1 is 010.

  1. 0 + 0 = 0
  2. 0 x 0 = 0
  3. 0 - 0 = 0
  4. 1 + 1 = 10
  5. 1 - 1 = 0
  6. 1 x 1 = 1
  7. 10 + 11 = 101
  8. 11 - 10 = 1
  9. 10 x 11 = 110
  10. 101001 + 101111100 = 110100101
  11. 101111100 + 101001 = 110100101
  12. 101111100 - 101001 = 101010011
  13. 101111100 x 101001 = 11110011011100
  14. 111111 + 111111111111 = 1000000111110
  15. 111111111111 + 111111 = 1000000111110
  16. 111111 x 111111111111 = 111110111111000001
  17. 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};
to intialize arrays A3 and B3 to the binary numbers 101001 and 101111100, respectively. Notice that the numbers are written in the arrays with the least significant bit first.

How to turn in your program

To turn in your program, log into one of the Dell computers in room 320, running Solaris, and using your own Unix account. If your program is called arithmetic.cc, issue commands 
    alias handin "/export/stu/classes/csci3675/bin/handin csci3675"
    handin 1 arithmetic.cc
This will automatically submit your program. You should receive a confirmation that the assignment was submitted. If you make a mistake and want to resubmit, you may do so up to the deadline. Your submission will be the most recently submitted program.

If you do not have a Unix account, please let me know so that one can be set up for you.

Be sure to include your name in the program itself.