CSCE 3110 Project 1 PROGRAM DESCRIPTION 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; } return product; } 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 0s 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 0s. 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 Due: 11:59 PM on Wednesday, May 29, 2019 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. SAMPLE OUTPUT (input shown in bold): $ ./a.out Enter first positive integer: 3847849 Enter second positive integer: 9573535 Error: Product results in integer overflow. $ ./a.out Enter first positive integer: 134 Enter second positive integer: 8531 Multiplication using only ADDITION: Product: 1143154 Pass 1: 0 seconds 25371 nanoseconds Product: 1143154 Pass 2: 0 seconds 2528 nanoseconds Product: 1143154 Pass 3: 0 seconds 2295 nanoseconds Product: 1143154 Pass 4: 0 seconds 2428 nanoseconds 2 CSCE 3110 Project 1 Due: 11:59 PM on Wednesday, May 29, 2019 Product: 1143154 Pass 5: 0 seconds 2219 nanoseconds Product: 1143154 Pass 6: 0 seconds 2446 nanoseconds Product: 1143154 Pass 7: 0 seconds 5348 nanoseconds Product: 1143154 Pass 8: 0 seconds 2247 nanoseconds Product: 1143154 Pass 9: 0 seconds 2227 nanoseconds Product: 1143154 Pass 10: 0 seconds 2334 nanoseconds Average: 0 seconds 4944.3 nanoseconds Multiplication using only ADDITION and BIT SHIFTS: Product: 1143154 Pass 1: 0 seconds 2384 nanoseconds Product: 1143154 Pass 2: 0 seconds 1908 nanoseconds Product: 1143154 Pass 3: 0 seconds 1992 nanoseconds Product: 1143154 Pass 4: 0 seconds 2065 nanoseconds Product: 1143154 Pass 5: 0 seconds 1848 nanoseconds Product: 1143154 Pass 6: 0 seconds 1887 nanoseconds Product: 1143154 Pass 7: 0 seconds 2278 nanoseconds Product: 1143154 Pass 8: 0 seconds 2123 nanoseconds Product: 1143154 Pass 9: 0 seconds 1866 nanoseconds Product: 1143154 Pass 10: 0 seconds 1892 nanoseconds Average: 0 seconds 2024.3 nanoseconds $ ./a.out Enter first positive integer: 0 Enter first positive integer: 3834852 Enter second positive integer: -3481 Enter second positive integer: 348721 Multiplication using only ADDITION: Product: 1558595236 Pass 1: 0 seconds 922810 nanoseconds Product: 1558595236 Pass 2: 0 seconds 960872 nanoseconds 3 CSCE 3110 Project 1 Due: 11:59 PM on Wednesday, May 29, 2019 Product: 1558595236 Pass 3: 0 seconds 967389 nanoseconds Product: 1558595236 Pass 4: 0 seconds 975816 nanoseconds Product: 1558595236 Pass 5: 0 seconds 916739 nanoseconds Product: 1558595236 Pass 6: 0 seconds 939650 nanoseconds Product: 1558595236 Pass 7: 0 seconds 942581 nanoseconds Product: 1558595236 Pass 8: 0 seconds 974544 nanoseconds Product: 1558595236 Pass 9: 0 seconds 947730 nanoseconds Product: 1558595236 Pass 10: 0 seconds 903583 nanoseconds Average: 0 seconds 945171 nanoseconds Multiplication using only ADDITION and BIT SHIFTS: Product: 1558595236 Pass 1: 0 seconds 4188 nanoseconds Product: 1558595236 Pass 2: 0 seconds 3368 nanoseconds Product: 1558595236 Pass 3: 0 seconds 6116 nanoseconds Product: 1558595236 Pass 4: 0 seconds 3206 nanoseconds Product: 1558595236 Pass 5: 0 seconds 3203 nanoseconds Product: 1558595236 Pass 6: 0 seconds 4097 nanoseconds Product: 1558595236 Pass 7: 0 seconds 4066 nanoseconds Product: 1558595236 Pass 8: 0 seconds 3302 nanoseconds Product: 1558595236 Pass 9: 0 seconds 5067 nanoseconds Product: 1558595236 Pass 10: 0 seconds 5433 nanoseconds Average: 0 seconds 4204.6 nanoseconds REQUIREMENTS Your code should be well documented in terms of comments. For example, good comments in general consist of a header (with your name, course section, date, 4
