-
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");
}
}
-
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
-
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>
-
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
-
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~
-
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
-
codeplug, how do you incorporate that into salems code?
You'll have to excuse me, my C skills are quite limited..
-
Your friend will know.
gg
-
thanks for the help guys..
nagi~
-
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.
-
I can't get it to compile
I keep ketting errors with the void and add sections
Any idea?