Thread: Need Help With This..

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

    Question Need Help With This..

    Hi..

    I need to speed up a program, i think the easiest way is to modify the pixval function, I'm clueless on this..Can anyone help??

    Here it is:

    Code:
    #include <stdio.h>
    #include <math.h>
    
    
    typedef struct complex Complex;
    struct complex{ double real; double imag;};
    
    #define size 1000
    
    int pix[size][size];
    
    Complex mult( const Complex a, const Complex b)
    {
    Complex res;
    res.real = a.real*b.real-a.imag*b.imag;
    res.imag = a.real*b.imag+a.imag*b.real;
    return res;
    }
    
    Complex add( const Complex a, const Complex b)
    {
    Complex res;
    res.real = a.real+b.real;
    res.imag = a.imag+b.imag;
    return res;
    }
    
    double abs( const Complex a)
    {
    return sqrt( a.real*a.real + a.imag*a.imag);
    }
    
    int pixval( double xx, double yy)
    {
    Complex z = {0,0};
    Complex c ;
    int j;
    c.real = yy; c.imag = xx;
    for (j = 0 ; j < 1000 && abs(z) < 2 ; j+=1){
    z = add( mult(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()
    {
    int x,y;
    fillpix(-2.0 , -2.0 , 4.0/size, 4.0/size);
    for (y = 0 ; y < size; y+=(size/20)){
    for (x = 0 ; x < size; x+=(size/50))
    printf("%c", ' '+pix[y][x]);
    printf("\n");
    }
    }

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    You should get a small speed up by passing all parameters by reference (ie. via a pointer).
    For instance:
    Code:
    void mult(const Complex *a, const Complex *b, Complex *result);
    gg

  3. #3
    Registered User Sargnagel's Avatar
    Join Date
    Aug 2002
    Posts
    166
    I've never used complex numbers before, but wouldn't it be better to use the complex arithmetic built into the ANSI C99 standard?
    <complex.h>

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    Skip the sqrt() call in abs() and do
    abs(z) < 4

    Here are my changes
    Code:
    #include <stdio.h>
    #include <math.h>
    
    // Get the number of processor clock ticks
    // This is for gcc3.x compiler only, if you have some
    // other compiler, you need something else here
    #define RDTSC(llptr) { \
        __asm__ __volatile__ ( \
        "rdtsc" \
        : "=A" (llptr) ); }
    
    typedef struct complex Complex;
    struct complex {
        double real;
        double imag;
    };
    
    #define size 1000
    #define limit 1000
    
    // if your compiler supports inline functions, then try it
    #define HAS_INLINE  /*inline*/
    
    int pix[size][size];
    
    // use pointers
    HAS_INLINE Complex mult(const Complex *a, const Complex *b)
    {
        Complex res;
        res.real = a->real * b->real - a->imag * b->imag;
        res.imag = a->real * b->imag + a->imag * b->real;
        return res;
    }
    
    // use pointers
    HAS_INLINE Complex add(const Complex *a, const Complex *b)
    {
        Complex res;
        res.real = a->real + b->real;
        res.imag = a->imag + b->imag;
        return res;
    }
    
    // don't do sqrt()
    // instead of sqrt(x) < 2,  do x < 4
    HAS_INLINE double Cabs(const Complex *a)
    {
        return a->real * a->real + a->imag * a->imag;
    }
    
    int pixval(double xx, double yy)
    {
        Complex z = { 0, 0 };
        Complex c;
        int j;
        c.real = yy;
        c.imag = xx;
        for (j = 0; j < limit && Cabs(&z) < 4; j += 1) {
            Complex t = mult( &z, &z);
            z = add( &t, &c);
        }
        return j / 20;
    }
    
    void fillpix(double x0, double y0, double xinc, double yinc)
    {
        int x, y;
        double  xd, yd;
        for (x = 0, xd = x0; x < size; ++x, xd += xinc ) {
            for (y = 0, yd = y0 ; y < size; ++y, yd += yinc ) {
                // mathematically, multiplication is repeated addition
                // computationally, it isn't due to small errors caused by
                // floating point numbers being approximations
                // this leads to some small differences in the results
    #if 1
                pix[x][y] = pixval( xd, yd );   // about 1% quicker than repeated multiply
    #else
                pix[x][y] = pixval( x0 + x * xinc, y0 + y * yinc );
    #endif
            }
        }
    }
    
    int main()
    {
        unsigned long long t1, t2;
        int x, y;
        RDTSC(t1);
        fillpix(-2.0, -2.0, 4.0 / size, 4.0 / size);
        RDTSC(t2);
        fprintf( stderr, "time=%lld\n", t2-t1 );
        for (y = 0; y < size; y += (size / 20)) {
            for (x = 0; x < size; x += (size / 50))
                printf("%c", ' ' + pix[y][x]);
            printf("\n");
        }
        return 0;
    }
    On my machine, I got these results
    your code: time=46645352892
    my code: time=23917603812
    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.

  5. #5
    Registered User
    Join Date
    Oct 2003
    Posts
    6
    Thanks very much everyone, especially Salem!!

    This is for a friend, and i'm sure he'll be very pleased..

    Once again, thanks for your help guys!

    Nagi~

  6. #6
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    I got an additional 30% speedup ontop of Salem's optimizations by using the following constructs:
    Code:
    void mult(const Complex *a, const Complex *b, Complex *res);
    void add(const Complex *a, const Complex *b, Complex *res);
    This prevents alot of data from being moved around when you don't "return res;".

    gg

  7. #7
    Registered User
    Join Date
    Oct 2003
    Posts
    6
    codeplug, how do you incorporate that into salems code?

    You'll have to excuse me, my C skills are quite limited..

  8. #8
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    Your friend will know.

    gg

  9. #9
    Registered User
    Join Date
    Oct 2003
    Posts
    6
    thanks for the help guys..

    nagi~

  10. #10
    Registered User The Dog's Avatar
    Join Date
    May 2002
    Location
    Cape Town
    Posts
    788
    Without the "return res", you won't be able to create complex calculations in one go eg.
    Code:
    Complex a, b, c, d;
    //..
    //..
    add( mult( &a, &b ), mult( &c, &d ) );
    Preference would prevail I guess.

  11. #11
    Registered User
    Join Date
    Oct 2003
    Posts
    2
    I can't get it to compile

    I keep ketting errors with the void and add sections

    Any idea?

Popular pages Recent additions subscribe to a feed