Due: Wed., Sep. 15 at 11:59pm
Warning. This assignment will be harder than it looks. Get started early.
A nonnegative integer can be represented as an array, in binary notation. Each member of the array is either 0 or 1. Then you can write functions to perform arithmetic operations such as addition, subtraction and multiplication.
You can represent a general integer (positive, negative or 0) by including a sign. For example, you can, by convention, let the first bit be 1 for a negative number and 0 for a nonnegative number.
Write an implementation of addition, subtraction, multiplication and greater-than-or-equal tests for 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.| // =========================================================== // // Representing Integers // --------------------- // All integers are stored in binary as arrays of bits. If N is // an array of bits, then N[0] tells the sign of the number, // with 1 meaning a negative number and 0 meaning a nonnegative // number. The remaning bits, N[1], N[2], ... are the binary digits // of the number, with the least significant bit stored at index 1. // For example, 8 is 1000 in binary. So 8 and -8 are stored as follows. // // index 8 index -8 // ----- ----- // 0 0 0 1 // 1 0 1 0 // 2 0 2 0 // 3 0 3 0 // 4 1 4 1 // // // Function Parameters // ------------------- // The addition, subtraction, multiplication and ge functions // all have parameters A and B, representing integers. They // also have parameters m and n indicating the sizes of those arrays. // A, B, m and n are all in-parameters; the represent information // sent from the caller to the function. // // Array A has m bits. This does not count the sign bit. So A has // m+1 slots. // // Array B has n bits, not counting the sign bit. // // The addition, subtraction and multiplication functions all // take another parameter, R, which the function sets to the // result. It is the caller's responsibility to ensure that array R // has enough room available to hold the answer. The number // of required cells is given in the description of each function. // // Variable Rsize is set to hold the number of bits that are actually // in array R, not counting leading 0 bits, and not counting the sign bit. // For example, suppose that R contains 13, represented as follows. // // index 13 // ----- // 0 0 -- sign bit // 1 1 // 2 0 // 3 1 // 4 1 // 5 0 // // Notice that index 5 contains a 0 that is really irrelevant. // R contains positive binary number 01101 (written in standard // high-to-low order), which is equivalent to 1101. The size // is reported to be 4, since R contains 4 relevant bits of information, // not counting the sign bit. // // Rsize is strictly an out parameter. // Its value on entry to the function is not used. //================================================================= typedef int BIT; //================================================================= // 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) + 2 // cells available (including room for the sign bit). //================================================================= void sum(BIT R[], int& Rsize, const BIT A[], int m, const BIT B[], int n); //================================================================= // diff(R,Rsize,A,m,B,n) stores the difference of integers A and B // into array R. That is, it computes R = A - B. // // Array R must have at least max(m,n) + 2 // cells available (including room for the sign bit). //================================================================= void diff(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+1 cells available. //================================================================= void product(BIT R[], int& Rsize, const BIT A[], int m, const BIT B[], int n); //================================================================= // ge(A,m,B,n) returns 1 if A >= B and 0 if A < B. //================================================================= int ge(const BIT A[], int m, const BIT B[], int n);
Create a header file called arithmetic.h, and put exactly the above comments, typedef and prototypes into it. The write an implementation file called arithmetic.cpp. Test it.
You are not asked to write a complete application here. Only four functions 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 program.
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.)
Your functions must have exactly the prototypes shown. If they do not, they will not link with my tester.
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.
In keeping with the previous requirement, it is not acceptable to convert an array to a 32 bit or 64 bit integer, do the arithmetic on that, and then convert back. That approach does not work for large integers.
Your functions must not have requirements that are not stated in the contracts. For example, 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. You cannot assume that there is more room in the in arrays (A and B) than is described by m and n. Do not look at A[m+1], for example.
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.)
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.
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. Elegance is more important than minor improvements in efficiency for this assignment.
If you feel that these requirements are impossible to meet, or you do not see how to meet them, ask for help.
Begin by writing an addition function that does not use the sign bit. It should assume that both numbers are nonnegative.
Keep in mind that the two numbers being added do not necessarily have the same number of bits. But you can loop to the size of the larger one, arranging to get 0 out of the shorter array when you are beyond its end.
Now write an unsigned subtraction function that computes A - B where it is required that A >= B, so that the answer is nonnegative. You learned how to subtract by borrowing. However, you can simulate borrowing by carrying -1. That way, subtraction ends up looking more like addition. Use your addition function as a guide. But think carefully.
Write a multiplication function for nonnegative integers. 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.
Write the ge function.
Now write separate functions to handle signed numbers. Just handle various combinations of signs. There are only four possibilities. For example, how do you add a negative number to another negative number? How do you add a negative number to a positive number? Do not forget the requirement of your basic subtraction function that A >= B. How can you meet this?
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 sample 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.)
An easy way to do these tests is just to initialize some arrays in your program. For example, write
BIT A3[] = {0,1,0,0,1,0,1};
BIT B3[] = {0,0,0,1,1,1,1,1,0,1};
to initialize arrays A3 and B3 to the positive binary numbers 101001 and
101111100, respectively. When you add new
tests, do not remove the old tests. Always keep your full test suite
at your disposal.
To turn in your assignment, log into one of the Unix machines in the lab. Issue the following command.
~karl/3675/bin/submit 1 arithmetic.cpp arithmetic.hYou should get confirmation that your files were handed in successfully.