C语言 牛顿分形优化

h4cxqtbf  于 2023-08-03  发布在  其他
关注(0)|答案(3)|浏览(79)

我用C语言实现了牛顿分形。我想知道是否有人知道如何在不使用线程或多进程的情况下提高代码的效率。我试过展开while循环,但它没有做太多。我还尝试使用-o1-o2-o3进行编译,但效果不佳。如果你们有任何建议,请告诉我,谢谢。

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);
}

字符串
手动进行数学运算会比使用<math.h>库更好吗?

ia2d9nvy

ia2d9nvy1#

是的,对于小整数指数使用pow是一个坏主意(因为它的相对complex operation involving log,exp,*,/),简单地用*计算它要好得多。在此之上,您使用同一变量的多个幂并再次计算它们,您可以重用较低的幂,例如change:

x3 = pow(x,3);
x5 = pow(x,5);

字符串
进入:

x3 = x*x*x;
x5 = x3*x*x;


这将降低操作的数量。
在此之上,你计算一切一遍又一遍的每个像素...
我假设你的代码看起来像这样:

t_fractal fractal;
for (fractal.y=0;fractal.y<ys;fractal.y++)
 for (fractal.x=0;fractal.x<xs;fractal.x++)
  calculate_newton(&fractal);


而在calculate_newton(t_fractal *fractal)内部,你一遍又一遍地重新计算所有与x,y位置相关的东西...如果你有y循环外层,你可以计算所有的东西,每次y改变一次,而不是做xs次以上…为此,您应该将这些变量移动到fractal context/struct中
在某些情况下,您可以避免使用*来计算递增值的幂(但是,如果从性能方面看它有任何意义,则取决于所使用的计算体系结构),请参阅

了解如何执行此操作的详细信息。
最重要的是,如果你连续缩放/平移,你可以重用已经从前一帧计算的值,就像我在here for Mandelbrot中所做的那样
然而,如果没有并行性,这就是你所能做的一切...
使用并行性,除非你有很多核心CPU/计算机,否则它不会提高速度,使用GPU更好,请参阅:

在这里,你渲染一个覆盖你的视图的QUAD/矩形,并计算碎片着色器内的分形(对于GLSL来说,它或多或少是C语言,所以它与你已经拥有的没有太大区别)。

p1tboqfb

p1tboqfb2#

你应该从乘法开始计算幂,而不是使用pow函数:

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;
}

字符串
然后注意,你可以通过分解(x2 + y2) * (x2 + y2)来简化代数,它也是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应该在编译时预先计算。在C中,你应该只使用常量:

#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 }};

d6kp6zgx

d6kp6zgx3#

我的建议:

总成本中的一个关键因素是从每个起始点执行的迭代次数。回忆这些呢?我的意思是,对于每个处理的像素,保持迭代次数。但是在迭代时,当你到达一个已经处理过的像素时,假设剩余的迭代次数是相同的。
这是一个近似值,但无论如何都假定每个像素只有一种颜色。

相关问题