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.
Write an implementation of addition 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. // // 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[]); // 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. // // 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;
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.)
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.)
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.
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.
Report time spent actually working on the problem, not counting time in between work sessions where you are doing something else.
3675 Assn 1 your nameBe sure to include your name in the program itself.
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 hrOf course, the times shown here are only examples, and might not be representative of the times that you use.