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