Csce 3110 – project 1

 

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