cmathoptimizationmathematical-optimizationfractals

Newton Fractal Optimization


I have implemented the Newton fractal in C. I was wondering if anyone knows how I can improve the efficiency of the code without using threads or multiple processes. I have tried unrolling the while loops, but it did not do much. I also tried using -o1, -o2, and -o3 when compiling this also did not do much. If you guys have any suggestions please let me know, thanks.

typedef struct s_float2 {
    float   x;
    float   y;
}   t_float2;

static t_float2 next(t_float2 z)
{
    t_float2    new;
    float       temp_deno;

    temp_deno = 3 * pow((pow(z.x, 2) + pow(z.y, 2)), 2);
    new.x = ((pow(z.x, 5) + 2 * pow(z.x, 3) * pow(z.y, 2)
                - pow(z.x, 2) + z.x * pow(z.y, 4) + pow(z.y, 2)) / temp_deno);
    new.y = ((z.y * (pow(z.x, 4) + 2 * pow(z.x, 2)
                    * pow(z.y, 2) + 2 * z.x + pow(z.y, 4))) / temp_deno);
    z.x -= new.x;
    z.y -= new.y;
    return (z);
}

static t_float2 find_diff(t_float2 z, t_float2 root)
{
    t_float2    new;

    new.x = z.x - root.x;
    new.y = z.y - root.y;
    return (new);
}

void    init_roots(t_float2 *roots)
{
    static int  flag;

    flag = 0;
    if (flag == 0)
    {
        roots[0] = (t_float2){ 1, 0 };
        roots[1] = (t_float2){ -0.5, sqrt(3) / 2 };
        roots[2] = (t_float2){ -0.5, -sqrt(3) / 2 };
        flag = 1;
    }
    return ;
}

void    calculate_newton(t_fractal *fractal)
{
    t_float2        z;
    int             iterations;
    int             i;
    t_float2        difference;
    static t_float2 roots[3];

    fractal->name = "newton";
    init_roots(&roots);
    iterations = -1;
    z.x = (fractal->x / fractal->zoom) + fractal->offset_x;
    z.y = (fractal->y / fractal->zoom) + fractal->offset_y;
    while (++iterations < fractal->max_iterations)
    {
        z = next(z);
        i = -1;
        while (++i < 3)
        {
            difference = find_diff(z, roots[i]);
            if (fabs(difference.x) < fractal->tolerance
                && fabs(difference.y) < fractal->tolerance)
                return (put_color_to_pixel(fractal, fractal->x, fractal->y,
                        fractal->color * iterations / 2));
        }
    }
    put_color_to_pixel(fractal, fractal->x, fractal->y, 0x000000);
}

Would it be better to manually do the math operations, rather than using the <math.h> library.


Solution

  • You should start by computing the powers with multiplications, not using the pow function:

    static t_float2 next(t_float2 z)
    {
        t_float2    new;
        float       temp_deno;
        float       x2 = z.x * z.x;
        float       y2 = z.y * z.y;
        float       x4 = zx2 * zx2;
        float       y4 = zy2 * zy2;
    
        temp_deno = 3 * (x2 + y2) * (x2 + y2);
        new.x = (z.x * (x4 + 2 * x2 * y2 + y4) + y2 - x2) / temp_deno;
        new.y = (z.y * (x4 + 2 * x2 * y2 + y4) + 2 * z.x * z.y) / temp_deno;
        z.x -= new.x;
        z.y -= new.y;
        return z;
    }
    

    Then note that you can simplify the algebra by factoring (x2 + y2) * (x2 + y2) which is also x4 + 2 * x2 * y2 + y4:

    static t_float2 next(t_float2 z)
    {
        float x2 = z.x * z.x;
        float y2 = z.y * z.y;
        float temp_deno = 3 * (x2 + y2) * (x2 + y2);
        return (t_float2){
            z.x * 2 / 3 - (y2 - x2) / temp_deno,
            z.y * 2 / 3 - (2 * z.x * z.y) / temp_deno
        };
    }
    

    roots should be precomputed at compile time. In C you should just use constants:

        #define COS_PI_6  0.866025403784439  // sqrt(3) / 2
        static t_float2 roots[3] = {{ 1, 0 }, { -0.5, COS_PI_6 }, { -0.5, -COS_PI_6 }};