| Assigned: | Monday, August 20 |
| Due: | Wednesday, September 5, 11:59pm |
This assignment is intended to be done using procedural programming and to form a baseline so that, when you do assignment 2, you can compare procedural programming to equational programming, at least for these functions.
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.
Write a Java class called Arithmetic in a file called Arithmetic.java, with static methods to increment, add and multiply nonnegative integers. The integers must be represented in binary as arrays of bytes, with one bit stored per byte, and with the low order bit at index 0. Use this template.
You can add any number of private static methods.
Just in case you missed it,
the integers must be represented in binary as arrays of bytes, with one bit stored per byte, and with the low order bit at index 0.
Do not tell me that you did not see that, because you did.
**Note** Please do not include a package line. If there is a package line, then I must either put your file into a directory whose name matches your package name or I must remove the package line. If your IDE (such as Eclipse) puts in a package line, just remove it in the version that you submit.
You are not asked to write a complete application here. Just define three functions (or methods), for other classes to use. I will test them by using them in another class. Do not include a main method.
Your functions must meet the following requirements.
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.
Your addition and multiplication methods 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 much 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.
Your methods 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 and put it into a library, and find that it can be used for arbitrarily large integers without recompiling it.
Say that a binary number is normalized if its most significant bit is 1. As a special case, a normalized representation of the number 0 is an array if 0 bytes.
Your methods 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 number whose high-order bit is 0.
Pay attention to this requirement. In the past, most students have ignored it and lost points as a result.
Your methods must not have requirements that have not been stated. For example, they cannot require that the caller perform some initialization that is not explicitly stated. You must use the descriptions given above. Do not add any additional requirements.
Your methods 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 public methods (inc, sum and product) cannot change any of the parameter arrays. They must put the result in a new array. (Private methods can do whatever you want them to do.)
Your functions must be thread-safe, meaning that two threads can use them concurrently without interfering with each other. So your functions cannot use any static variables.
Strive for simplicity and elegance in your definitions. Try to make them clear and readable. Do not be excessively concerned with efficiency. Keep it simple.
Test your methods thoroughly. Do not be satisfied with one or two tests of each method. In the past, few submissions of this assignment passed all of the tests that I tried. Pay attention to what these methods do when one or both parameters are 0. Test your methods on parameters that are not normalized. I will.
Test your class by writing a separate class ArithmeticTest that does the testing. It will have at least a main method and a method that prints a binary number.
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). Check the number of bits as well. The result of 0 + 0 should have 0 bits.
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.
To submit your work you will need to log into one of the Linux computers in Austin 208, or log into xlogin.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. Be sure to include your name in the program.
Then, in a terminal, issue command
~abrahamsonk/3675/bin/submit 1 Arithmetic.java ArithmeticTest.javaCommand
~abrahamsonk/3675/bin/submit 1will tell you what you have submitted.
To ask a question about your program, first submit it,
but use assignment name q1. For example, use command
~abrahamsonk/3675/bin/submit q1 Arithmetic.java
Then send me an email with your question. Do not expect
me to read your mind. Tell me what your question(s) are.
I will look at the file that you have submitted as q1.
If you have another question later, resubmit your new file
as assignment q1 and send another email.