CSCE 3110 – Project 1
In this programming assignment, you will (1) write a complete C++ program to implement multiplication operations as directed and (2) perform an analysis with respect to the theoretical and experimental running time complexity. The following C++ code for the multiply function computes the product of two operands using only addition: int multiply(int operand1, int operand2)
int multiplier = (operand1 < operand2) ? operand1 : operand2; int multiplicand = (operand1 > operand2) ? operand1 : operand2;
int product = 0;
for (int i = 0; i < multiplier; i++)
product += multiplicand;
This function as given runs in ((, )), which is a linear time algorithm. We would, however, like for this algorithm to run faster, which can reduce the time complexity to (( , )) by using only addition, bit shifting, and possibly the bitwise & operator. Therefore, your objective for this programming assignment is to write a new function called bitMultiply, accepting the same two parameters, to reduce the time complexity of this operation. Some background on bit shifting: For some variable operand and number n, a bit shift is written as either operand = operand << n; or operand = operand >> n;, where the << operator left shifts the bits in operand by n bits and fills in the opened positions with 0’s while the << operator right shifts the bits in operand by n bits, throwing away the lower order n bits and replacing higher order bits with 0’s. The << operator corresponds to multiplying the number by 2 ! , while the >> operator
corresponds to dividing the number by 2
. For example, the decimal value 10 is
represented internally by the bit string 1010, so if we left shift 10 by 2 bits, we obtain 101000, which can be verified to be 10 × 2
. As another hint, C++ supports the bitwise
& operator that performs a bitwise “and” of two integers that can be helpful in inspecting the bits of an integer.
To show this improvement in time complexity, we define the requirements for this program:
• You will prompt for and read in two operands as positive integers (i.e., > 0). Since we are using bit shifting, you will limit the resulting product to the maximum positive value supported by integers, so that if the product exceeds this value you will print an error message and terminate the program. If the user enters a nonpositive value, you will simply continue to re-prompt the user until he/she enters a 1 CSCE 3110 – Project 1 valid positive integer. You may assume that the user enters an integer, though possibly out of range, for this assignment. • For the multiplication operation provided by the multiply function, you will perform this operation 10 times, calculating the amount of time in nanoseconds that it takes to complete each time, and then find the average of all 10 of the passes. • You will then write a new function called bitMultiply, accepting the same two operands as parameters, and compute the product of the two operands using only bit shifting, addition, and perhaps use of the bitwise & operator. Similarly, you will perform this operation 10 times, calculating the amount of time in nanoseconds that it takes to complete each time, and then find the average of all 10 of the passes. ANALYSIS REQUIREMENTS
Perform several runs of your program, ranging from product calculations using small integers to product calculations using large integers (but not overflowing the integer data structure). If your bitMultiply program was done correctly, you should see a significant improvement in the amount of time needed to perform the calculations, but did it improve by the expected amount? Include a screen shot (or typescript) of your program performing several runs with various inputs and write a one or two paragraph analysis of your results that describes whether or not you achieved the results you expected. Plot your results on the same graph, where the size can be used for the xaxis and the running time in nanoseconds can be used for the y-axis. Since the values are fairly large (i.e., in nanoseconds), you may wish to plot your results using the logarithmic values as needed. Provide some explanation or justification on why your results did or did not meet the expected performance metrics.
CSCE 3110 – Project 1