Thread: Speeding up the computation without losing accuracy

  1. #1
    Registered User
    Join Date
    Oct 2003
    Posts
    2

    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

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    LOL, there must be a bunch of you in the same class

    Recently asked
    http://cboard.cprogramming.com/showt...threadid=46325
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Pithagore-fast computation
    By invinciblevn in forum C Programming
    Replies: 11
    Last Post: 01-15-2008, 03:10 AM
  2. mouse accuracy
    By joed in forum Windows Programming
    Replies: 3
    Last Post: 06-25-2005, 04:52 PM