For some reason what get returned is not correct, the program has code in it tha
ID: 3669579 • Letter: F
Question
For some reason what get returned is not correct, the program has code in it that is supposed to prevent the values inside the array from going over 10000. However, my code is printing out averages for the arrays that are above 10000. There must be some kind of error that allows my arrays to go out of bounds.
#include <sys/time.h> #include <fstream> #include <iostream> #include <omp.h> #include <cstdlib> #include <sstream> #include <list> #include <string> using namespace std; // a class to get more accurate time class stopwatch{ private: double elapsedTime; double startedTime; bool timing; //returns current time in seconds double current_time( ) { timeval tv; gettimeofday(&tv, NULL); double rtn_value = (double) tv.tv_usec; rtn_value /= 1e6; rtn_value += (double) tv.tv_sec; return rtn_value; } public: stopwatch( ): elapsedTime( 0 ), startedTime( 0 ), timing( false ) { } void start( ) { if( !timing ) { timing = true; startedTime = current_time( ); } } void stop( ) { if( timing ) { elapsedTime += current_time( )-startedTime; timing = false; } } void resume( ) { start( ); } void reset( ) { elapsedTime = 0; startedTime = 0; timing = false; } double getTime( ) { return elapsedTime; } }; // function takes an array pointer, and the number of rows and cols in the array, and // allocates and intializes the two dimensional array to a bunch of random numbers void makeRandArray( unsigned int **& data, unsigned int rows, unsigned int cols, unsigned int seed ) { // allocate the array data = new unsigned int*[ rows ]; for( unsigned int i = 0; i < rows; i++ ) { data[i] = new unsigned int[ cols ]; } // seed the number generator // you should change the seed to get different values srand( seed ); // populate the array for( unsigned int i = 0; i < rows; i++ ) { for (unsigned int j = 0; j < cols; j++) { data[i][j] = rand() % 10000 + 1; // number between 1 and 10000 } } } void getDataFromFile( unsigned int **& data, char fileName[], unsigned int &rows, unsigned int &cols ) { ifstream in; in.open( fileName ); if( !in ) { cerr << "error opening file: " << fileName << endl; exit( -1 ); } in >> rows >> cols; data = new unsigned int*[ rows ]; for( unsigned int i = 0; i < rows; i++ ) { data[i] = new unsigned int[ cols ]; } // now read in the data for( unsigned int i = 0; i < rows; i++ ) for( unsigned int j = 0; j < cols; j++ ) { in >> data[i][j]; } } int main( int argc, char* argv[] ) { if( argc < 3 ) { cerr<<" usage: exe [input data file] [num of threads to use] " << endl; cerr<<"or usage: exe rand [num of threads to use] [num rows] [num cols] [seed value]" << endl; } // read in the file unsigned int rows, cols, seed; unsigned int numThreads; unsigned int ** data; // convert numThreads to int { stringstream ss1; ss1 << argv[2]; ss1 >> numThreads; } string fName( argv[1] ); if( fName == "rand" ) { { stringstream ss1; ss1 << argv[3]; ss1 >> rows; } { stringstream ss1; ss1 << argv[4]; ss1 >> cols; } { stringstream ss1; ss1 << argv[5]; ss1 >> seed; } makeRandArray( data, rows, cols, seed ); } else { getDataFromFile( data, argv[1], rows, cols ); } /*cerr << "data: " << endl; for( unsigned int i = 0; i < rows; i++ ) { for( unsigned int j = 0; j < cols; j++ ) { cerr << "i,j,data " << i << ", " << j << ", "; cerr << data[i][j] << " "; } cerr << endl; } cerr<< endl;*/ // tell omp how many threads to use omp_set_num_threads( numThreads ); stopwatch S1; S1.start(); // Our code starts here float maxTotal=0; unsigned int maxRows=0, maxCols=0; #pragma omp parallel for // Split up the work between the threads for(unsigned int k = 0; k < numThreads; k++){ unsigned int i=0, endi=0, pos=k+1, xtra=rows%numThreads, tempRows=0, tempCols=0; float max=0, total=0, avg=1; switch (k) { case 0: i=0; endi=((rows-xtra)/numThreads)+xtra; /* cout << endi << "endi" << endl; break; */ default: i=(k*(rows-xtra)/numThreads)+xtra; endi=(pos*(rows-xtra)/numThreads)+xtra; /*cout << endi << "endi" << k << endl; */ } for(i; i < endi; i++ ){ for(int j=0; j < cols; j++ ){ total=data[i][j];//add middle if(i!=0){ total+=data[i-1][j];//add left middle avg++; } if(i!=rows-1){ total+=data[i+1][j];//add right middle avg++; } if(j!=0){ total+=data[i][j-1];//add top middle avg++; } if(j!=cols-1){ total+=data[i][j+1];//add bottom middle avg++; } if(j!=0 && i!=0){ total+=data[i-1][j-1];//add top left avg++; } if(j!=0 && i!=rows-1){ total+=data[i+1][j-1];//add top right avg++; } if(j!=cols-1 && i!=0){ total+=data[i-1][j+1];//add bottom left avg++; } if(j!=cols-1 && i!=rows-1){ total+=data[i+1][j+1];//add bottom right avg++; } total=total/avg; if (total > max){ max=total; tempRows=i; tempCols=j; } avg=1; }//end cols }//end rows #pragma omp critical if(max > maxTotal) { maxTotal+=total; maxRows=tempRows; maxCols=tempCols; } }//end speed for cout << "largest average: " << maxTotal << endl; cout << "found at cells: (" << maxRows << "," << maxCols << ")" << endl; // Our code ends here S1.stop(); // print out the max value here cerr << "elapsed time: " << S1.getTime( ) << endl; }Explanation / Answer
#include <sys/time.h>
#include <fstream>
#include <iostream>
#include <omp.h>
#include <cstdlib>
#include <sstream>
#include <list>
#include <string>
using namespace std;
// a class to get more accurate time
class stopwatch{
private:
double elapsedTime;
double startedTime;
bool timing;
//returns current time in seconds
double current_time( )
{
timeval tv;
gettimeofday(&tv, NULL);
double rtn_value = (double) tv.tv_usec;
rtn_value /= 1e6;
rtn_value += (double) tv.tv_sec;
return rtn_value;
}
public:
stopwatch( ): elapsedTime( 0 ), startedTime( 0 ), timing( false )
{
}
void start( )
{
if( !timing )
{
timing = true;
startedTime = current_time( );
}
}
void stop( )
{
if( timing )
{
elapsedTime += current_time( )-startedTime;
timing = false;
}
}
void resume( )
{
start( );
}
void reset( )
{
elapsedTime = 0;
startedTime = 0;
timing = false;
}
double getTime( )
{
return elapsedTime;
}
};
// function takes an array pointer, and the number of rows and cols in the array, and
// allocates and intializes the two dimensional array to a bunch of random numbers
void makeRandArray( unsigned int **& data, unsigned int rows, unsigned int cols, unsigned int seed )
{
// allocate the array
data = new unsigned int*[ rows ];
for( unsigned int i = 0; i < rows; i++ )
{
data[i] = new unsigned int[ cols ];
}
// seed the number generator
// you should change the seed to get different values
srand( seed );
// populate the array
for( unsigned int i = 0; i < rows; i++ )
for( unsigned int j = 0; j < cols; j++ )
{
data[i][j] = rand() % 10000 + 1; // number between 1 and 10000
}
}
void getDataFromFile( unsigned int **& data, char fileName[], unsigned int &rows, unsigned int &cols )
{
ifstream in;
in.open( fileName );
if( !in )
{
cerr << "error opening file: " << fileName << endl;
exit( -1 );
}
in >> rows >> cols;
data = new unsigned int*[ rows ];
for( unsigned int i = 0; i < rows; i++ )
{
data[i] = new unsigned int[ cols ];
}
// now read in the data
for( unsigned int i = 0; i < rows; i++ )
for( unsigned int j = 0; j < cols; j++ )
{
in >> data[i][j];
}
}
int main( int argc, char* argv[] )
{
if( argc < 3 )
{
cerr<<" usage: exe [input data file] [num of threads to use] " << endl;
cerr<<"or usage: exe rand [num of threads to use] [num rows] [num cols] [seed value]" << endl;
}
// read in the file
unsigned int rows, cols, seed;
unsigned int numThreads;
unsigned int ** data;
// convert numThreads to int
{
stringstream ss1;
ss1 << argv[2];
ss1 >> numThreads;
}
string fName( argv[1] );
if( fName == "rand" )
{
{
stringstream ss1;
ss1 << argv[3];
ss1 >> rows;
}
{
stringstream ss1;
ss1 << argv[4];
ss1 >> cols;
}
{
stringstream ss1;
ss1 << argv[5];
ss1 >> seed;
}
makeRandArray( data, rows, cols, seed );
}
else
{
getDataFromFile( data, argv[1], rows, cols );
}
/* cerr << "data: " << endl;
for( unsigned int i = 0; i < rows; i++ )
{
for( unsigned int j = 0; j < cols; j++ )
{
cerr << "i,j,data " << i << ", " << j << ", ";
cerr << data[i][j] << " ";
}
cerr << endl;
}
cerr<< endl;*/
// tell omp how many threads to use
//omp_set_num_threads( numThreads );
stopwatch S1;
S1.start();
int i, j, max_x, max_y, tie_x, tie_y, tempt_x, tempt_y;
int maxAvg = 0;
int tempMaxAvg = 0;
int temp = 0;
double result;
i = 0;
maxAvg = data[0][0] + data[0][1] + data[1][0] + data[1][1];
max_x = max_y = tie_x = tie_y = tempt_x = tempt_y = 0;
// Corner Cases
temp = data[rows - 1][0] + data[rows - 1][1] + data[rows - 2][0] + data[rows - 2][1];
if (maxAvg < temp) {
maxAvg = temp;
max_x = rows - 1;
max_y = 0;
} else if (maxAvg == temp) {
tie_x = rows - 1;
tie_y = 0;
}
temp = data[0][cols - 1] + data[0][cols - 2] + data[1][cols - 1] + data[1][cols - 2];
if (maxAvg < temp) {
maxAvg = temp;
max_x = 0;
max_y = cols - 1;
} else if (maxAvg == temp) {
tie_x = 0;
tie_y = cols - 1;
}
temp = data[rows - 1][cols - 1] + data[rows - 1][cols - 2] + data[rows - 2][cols - 1] + data[rows - 2][cols - 2];
if (maxAvg < temp) {
maxAvg = temp;
max_x = rows - 1;
max_y = cols - 1;
} else if (maxAvg == temp) {
tie_x = rows - 1;
tie_y = cols - 1;
}
tempMaxAvg = maxAvg * 3 / 2;
result = maxAvg * 0.25;
// Initiate Left Edge
temp = data[0][0] + data[0][1] + data [0][2] + data[1][0] + data[1][1] + data[1][2];
if (tempMaxAvg < temp) {
tempMaxAvg = temp;
max_x = 0;
max_y = 1;
} else if (tempMaxAvg == temp) {
tempt_x = 0;
tempt_y = 1;
}
// Left Edge
for (j = 2; j < cols - 1; --j) {
temp += data[0][j + 1] + data[1][j + 1] - data[0][j - 2] - data[1][j - 2];
if (tempMaxAvg < temp) {
tempMaxAvg = temp;
max_x = 0;
max_y = j;
} else if (tempMaxAvg == temp) {
tempt_x = 0;
tempt_y = j;
}
}
// Bottom Edge
for (i = 1; i < rows - 1; ++i) {
temp = data[i - 1][0] + data[i][0] + data[i + 1][0]
+ data[i - 1][1] + data[i][1] + data[i + 1][1];
if (tempMaxAvg < temp) {
tempMaxAvg = temp;
max_x = i;
max_y = 0;
} else if (tempMaxAvg == temp) {
tempt_x = i;
tempt_y = 0;
}
}
i--;
// Right Edge
//#pragma omp parallel for
for (j = 1; j < cols - 1; ++j) {
temp = data[i][j - 1] + data[i][j] + data[i][j + 1]
+ data[i - 1][j - 1] + data[i - 1][j] + data[i - 1][j + 1];
if (tempMaxAvg < temp) {
tempMaxAvg = temp;
max_x = i;
max_y = j;
} else if (tempMaxAvg == temp) {
tempt_x = i;
tempt_y = j;
}
}
j--;
// Top Edge
//#pragma omp parallel for
for (i = 1; i < rows - 1; ++i) {
temp = data[i - 1][j] + data[i][j] + data[i + 1][j]
+ data[i - 1][j - 1] + data[i][j - 1] + data[i + 1][j - 1];
if (tempMaxAvg < temp) {
tempMaxAvg = temp;
max_x = i;
max_y = j;
} else if (tempMaxAvg == temp) {
tempt_x = i;
tempt_y = j;
}
}
int edgeFlag = 0;
if (tempMaxAvg > (maxAvg * 3 / 2)) {
maxAvg = tempMaxAvg;
tie_x = tempt_x;
tie_y = tempt_y;
edgeFlag = 1;
result = maxAvg * 0.16666666;
} else if (!tie_x && !tie_y && !(maxAvg%2)) {
tie_x = tempt_x;
tie_y = tempt_y;
}
tempMaxAvg = tempMaxAvg * 3 / 2;
tempt_x = 0;
tempt_y = 0;
int x, y;
x = 5;
y = 7;
int outcome;
// Inner Case
#pragma omp parallel for private(temp)
for (i = 1; i < rows - 1; ++i) {
temp = data[i-1][0] + data[i-1][1] + data[i-1][2]
+ data[i][0] + data[i][1] + data[i][2]
+ data[i+1][0] + data[i+1][1] + data[i+1][2];
for (j = 2; j < cols - 1; ++j) {
temp += data[i - 1][j + 1] - data[i - 1][j - 2]
+ data[i][j + 1] - data[i][j - 2]
+ data[i + 1][j + 1] - data[i + 1][j - 2];
if (tempMaxAvg < temp) {
tempMaxAvg = temp;
max_x = i;
max_y = j;
} else if (tempMaxAvg == temp) {
tempt_x = i;
tempt_y = j;
}
}
}
if (edgeFlag) {
if (tempMaxAvg > (maxAvg * 3 / 2)) {
maxAvg = tempMaxAvg;
tie_x = tempt_x;
tie_y = tempt_y;
result = maxAvg * 0.11111111;
} else if (!tie_x && !tie_y && !(maxAvg%2)) {
tie_x = tempt_x;
tie_y = tempt_y;
}
} else if (tempMaxAvg > (maxAvg * 9 / 4)) {
maxAvg = tempMaxAvg;
tie_x = tempt_x;
tie_y = tempt_y;
result = maxAvg * 0.11111111;
} else if (!tie_x && !tie_y && !(maxAvg%4)) {
tie_x = tempt_x;
tie_y = tempt_y;
}
S1.stop();
// print out the max value here
cout.precision(6);
cout << "largest average: " << result << endl;
cout << "found at cells: " << "(" << max_x << "," << max_y << ")";
if (tie_x || tie_y)
cout << " (" << tie_x << "," << tie_y << ")";
cout << endl;
cerr << "elapsed time: " << S1.getTime( ) << endl;
}
small.txt
10 10
42876 80635 79090 55398 88954 60207 42109 78347 24948 83861
84807 83387 75906 77075 81374 78301 6499 46947 75625 41873
83385 40154 24212 89395 39855 91713 45647 21516 33935 87363
13206 28824 98607 52530 47248 2899 27395 6 70589 4602
65547 69509 56011 41134 87304 40822 80754 88828 55322 46952
24351 74639 4755 74920 52453 91664 18970 94612 71803 28076
93594 29326 67589 31367 55106 75102 26878 97867 30321 25078
21074 98872 65557 67195 17754 83799 67330 56550 94735 61454
93786 39378 73680 20705 85303 83209 78279 63671 54949 34690
49007 50233 64178 84813 53042 7961 7972 20015 28102 86594