Speeding up the computation without losing accuracy
I need to speed up computation without losing accuracy on the folling program for a Uni assesment can anyone help.
------------------------------------------------------------------------------------
Code:
#include <iostream>
#include <complex>
using namespace std;
typedef complex<double> Complex;
const int size = 1000;
int pix[size][size];
int pixval( double xx, double yy)
{
Complex z = 0;
Complex c(xx,yy);
int j;
for (j = 0 ; j < 1000 && abs(z) < 2 ; ++j)
z = z*z+c;
return j / 20;
}
void fillpix(double x0, double y0, double xinc, double yinc)
{
int x, y;
for( x = 0 ; x < size ; ++x)
for( y = 0 ; y < size ; ++y)
pix[x][y] = pixval( x0+x*xinc, y0+y*yinc);
}
int main()
{
fillpix(0.2, 0.2, 0.001, 0.001);
for (int y = 0 ; y < size; y+=(size/60)){
for (int x = 0 ; x < size; x+=(size/20))
cout << char( ' '+pix[y][x]);
cout << endl;
}
}
------------------------------------------------------------------------------------
Here is some things I've been asked to consider
The time taken by the program is taken to be that returned for user time ( the time the CPU spends on your computation), given by
time prog when run on sol for a size of 1000*1000 pixels.
The final program should produce the same results as the original. Check this by writing out, to a file, the array produced by the original, and comparing any new results with this gold standard.
You should check that all 1000*1000 cells are the same.)
It is also possible to generate a much smaller output file by creating a signature -
Consider an array of 3 unsigned integers (buckets).
Initialise these to zero, then add
cells 0, 3, 6, ... into the zeroth bucket
cells 1, 4, 7, ... into the middle bucket
cells 2, 5, 8, ... into the last bucket.
(Every cell in the 2D array is to be added into some bucket).
The sequence of values in the array of buckets is the signature, and will be the same if created from identical 2D arrays of cells.
However, we may want an array of 1, 3, 17, or n buckets - the number of buckets should be a constant.
You are advised to try speeding up the computation by improving pixval, in which the computer spends most of its effort ( see man prof).
You should think about
Compiler optimisation
The CC compiler accepts flags for degrees of optimisation
-O1 .. -O5
-fast
Reorganising the program
Some program forms run faster than others.
Loop unrolling
Current computers work fastest on sequences without branches.
Re-arrange the program to cut down branches.
Algebraic reorganisation
you are welcome to work at the level of the underlying algebra. Remember that some variables are complex.
Inlining functions
A C++ compiler accepts the keyword inline as a request to the compiler to avoid a function call by planting code where the function is called.
The syntax is
inline double fn( int ss) { return ss+8.4;};
Any help very much appreciated
Thanks
Richard
