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 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
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