Computer Science 3675
Section 001
Fall 2011
Programming Assignment 1

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

Functions

Write an implementation of increment, addition and multiplication of nonnegative integers, stored in binary, in either Java or C++. Design your functions as shown in one of the following pages.

• Java
• C++

Recording your time

Please keep track, as best you can, of the number of hours that you spend on this. In the source file that you submit, write a comment at the top telling your name, and just below that your estimate of the number of hours used for: (1) learning the language or library; (2) writing the module; (3) testing and debugging. Try to be as honest and accurate as possible and reasonable.

Requirements

You are not asked to write a complete application here. Only three functions (or methods) are to be provided. They are for use in other programs. I will test them by using them in another program. Do not include a main function or method.

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. You are not allowed to trivialize the problem by using a library that performs arithmetic on large integers. The idea is to program the algorithms.

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.

3. Your functions must not make any assumptions about how large the arrays are, other than those explicitly stated. You cannot assume that the numbers fit into a 64-bit integer. It is unacceptable to assume that the numbers have no more than 100 bits in them. It must be possible to compile your class or functions and put them into a library, and find that they can be used for arbitrarily large integers without recompiling them.

4. Say that a binary number is normalized if its most significant bit is 1, or if it is 0, and has no bits. Your functions must produce normalized results. They cannot presume, however, that their parameter arrays are normalized. For example, a parameter to the addition function might be a positive number that starts with a 0.

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

6. 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. Your functions cannot change any of the parameter arrays except those explicitly mentioned as output parameters.

7. Strive for simplicity and elegance in your definitions. Try to make them clear and readable. Do not be excessively concerned with efficiency.

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 be sure 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. 0 + 1 = 1
4. 0 x 1 = 0
5. 1 + 1 = 10
6. 1 x 1 = 1
7. 10 + 11 = 101
8. 10 x 11 = 110
9. 101001 + 101111100 = 110100101
10. 101111100 + 101001 = 110100101
11. 101111100 x 101001 = 11110011011100
12. 111111 + 111111111111 = 1000000111110
13. 111111111111 + 111111 = 1000000111110
14. 111111 x 111111111111 = 111110111111000001
15. 111111111111 x 111111 = 111110111111000001
16. 11111111111111111111111111111111111111111111111111111111111111111111111111111111 + 1 = 100000000000000000000000000000000000000000000000000000000000000000000000000000000

Systems

You can use any system that you like. If you have any questions about this, or if you have trouble using a system, please let me know.

Submitting Your Work

To submit your work you will need to log into one of the Linux computers in Austin 208, or log into login.cs.ecu.edu remotely (using ssh or putty or NX client). Be sure that your files are on that computer, and that your current directory is the one that contains those files. Call a Java version Arithmetic.java, and call a C++ version arithmetic.cpp. If you use Java, delete any initial package line from the beginning of your file.

Then, in a terminal, issue command

  ~abrahamsonk/3675/bin/submit 1 Arithmetic.java

  ~abrahamsonk/3675/bin/submit 1 arithmetic.cpp