 #### Previous topic

Multi-Threaded Programming Introduction using the Sum3 Problem

#### Next topic

Sum3 Simple Implementation (Serial)

# Sum3 Problem Overview¶

## Basic Description¶

The Sum3 problem is described by a rather simple question: Given a set of integers, how many triples of distinct elements in that list add up to 0.

For example, given the following list:

```-1, -2, 0, 2, 3
```

```-1 + -2 + 3 = 0
-2 + 0 + 2 = 0
```

The simplest way to code a solution to the Sum3 problem is to use a double nested looping structure to generate the indices of all possible triples in the input array. Clearly, this is simple to express in code, but has an unfortunate time complexity of . For example, the following C++ code uses 3 for loops to achieve a correct solution.

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23``` ```#include using namespace std; int main( ) { int dataSize = 5; int* data = new int[ dataSize ]; data = -1; data = -2; data = 0; data = 2; data = 3; // do the naive Sum3 computation. O(n^3) int count = 0; for (int i = 0; i < dataSize-2; i++) for (int j = i+1; j < dataSize-1; j++) for (int k = j+1; k < dataSize; k++) if (data[i] + data[j] + data[k] == 0) count++; cout<< count <

## Complete Naive Solution¶

The next code block uses the same solution as above, but includes a command line parameter that will generate an array of random numbers of a user-specified size. The getRandInt() function loads the vector passed into it with random integers. The data vector allocates space for the number of integers required, and is then passed to the getRandInt() function. This version of the program allows the user to get a feel for how and program behaves in practice. Try compiling the program and running it.

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61``` ```#include #include using namespace std; int getRandInt( int* dataVec, int dataSize ) { // load up a vector with random integers int num; for( int i = 0; i < dataSize; i++ ) { // integers will be 1-100 num = rand() % 100 +1; if( rand( ) % 2 == 0 ) { // make some integers negative num *= -1; } dataVec[i] = num; } } int main(int argc, char * argv[] ) { int dataSize = 0; if( argc < 2 ) { std::cerr << "usage: exe [num of nums] [optional seed value]" << std::endl; exit( -1 ); } { std::stringstream ss1; ss1 << argv; ss1 >> dataSize; } if( argc >= 3 ) { std::stringstream ss1; int seed; ss1 << argv; ss1 >> seed; srand( seed ); } else { srand( 0 ); } // create a data vector int* data = new int[ dataSize ]; // load it up with random data getRandInt( data, dataSize ); int *dataPtr = &data; // do the naive Sum3 computation. O(n^3) int count = 0; for (int i = 0; i < dataSize-2; i++) for (int j = i+1; j < dataSize-1; j++) for (int k = j+1; k < dataSize; k++) if (dataPtr[i] + dataPtr[j] + dataPtr[k] == 0){ count++; } cout<< count <

Here are some running times for the previous program:

Array Size Time (s)
500 .106
1000 .804
1500 2.698
2000 6.382
2500 12.459
3000 21.519
3500 34.162

The running times are plotted. The cubic nature of the curve is clearly visible. Exercise

Create a Makefile and use the Makefile to compile the program listed above. Run the program using the time command on linux to see some running times. Collect running times on two different machines. Write a brief report indicating your results and listing the machine specifications. List reasons why one machine is faster than the other.

To find out machine specs on linux, check out the lspci abd lscpu commands, and check out the /proc filesystem. Check the man pages and/or google for information on how to use/interpret these resources