c - n 段求根算法的性能

Question

我编写了一个用于查找函数根的 n 部分算法。工作原理和二分法完全一样，只是把范围分成N等份。这是我的 C 代码:

/*
    Compile with: clang -O3 -o nsect nsect.c -Wall -DCOUNT=5000000 -DNSECT=? -funroll-loops
*/

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>

#define N 6

#ifndef COUNT
#error COUNT not defined!
#endif

#ifndef NSECT
#define NSECT 2
#endif

float polynomial[N];
float horner( const float poly[N], float x )
{
    float val = poly[N-1];
    for ( int i = N - 2; i >= 0; i-- )
        val = poly[i] + x * val;
    return val;
}

float f( float x )
{
    return horner( polynomial, x );
}

float nsect( float a, float b, const float eps_x )
{
    float fa = f( a );
    float fb = f( b );
    if ( fa == 0 ) return a;
    else if ( fb == 0 ) return b;
    else if ( fa * fb > 0 ) return 0;

    float x[NSECT];
    float fx[NSECT];

    while ( b - a > eps_x )
    {   
        x[0] = a;
        if ( ( fx[0] = f( x[0] ) ) == 0 ) return x[0];

        int found = 0;
        for ( int i = 0; i < NSECT - 1; i++ )
        {
            x[i + 1] = a + ( b - a ) * (float)( i + 1 ) / NSECT;
            if ( ( fx[i + 1] = f( x[i + 1] ) ) == 0 )
                return x[i + 1];
            else if ( fx[i] * fx[i + 1] < 0 )
            {
                a = x[i];
                b = x[i + 1];
                found = 1;
                break;
            }
        }

        if ( !found )
            a = x[NSECT - 1]; 

    }

    return ( a + b ) * 0.5f;
}

int main( int argc, char **argv )
{
    struct timeval t0, t1;
    float *polys = malloc( COUNT * sizeof( float ) * N );
    float *p = polys;
    for ( int i = 0; i < COUNT * N; i++ )
        scanf( "%f", p++ ); 

    float xsum = 0; // So the code isn't optimized when we don't print the roots
    p = polys;
    gettimeofday( &t0, NULL );
    for ( int i = 0; i < COUNT; i++, p += N )
    {
        memcpy( polynomial, p, N * sizeof( float ) );
        float x = nsect( -100, 100, 1e-3 );
        xsum += x;

        #ifdef PRINT_ROOTS
            fprintf( stderr, "%f\n", x );
        #endif
    }
    gettimeofday( &t1, NULL );

    fprintf( stderr, "xsum: %f\n", xsum );
    printf( "%f ms\n", ( ( t1.tv_sec - t0.tv_sec ) * 1e6 + ( t1.tv_usec - t0.tv_usec ) ) * 1e-3 );
    free( polys );
}

编辑:这是我用来编译代码的命令:clang -O3 -o nsect nsect.c -Wall -DCOUNT=5000000 -DNSECT=? -funroll-loops。 我在 i7-8700k 上运行了一切。

我决定测试不同 N 值的算法性能。该测试包括测量为 5,000,000 个 5 次多项式中的每一个找到范围 (-100;100) 中的任何根所需的时间。多项式是随机生成的，并且具有从 -5 到 5 的实数系数。多项式值是使用以下公式计算的霍纳法。

这些是我对每个 N(x=N，y=time [ms])运行代码 10 次得到的结果:

我对此处最坏情况性能的理解是，主 while 循环中要完成的工作量与 N 成正比。主循环需要 log_N(C)(其中 C > 1 是一个常数 - 初始搜索范围与请求精度的比率)迭代完全的。这产生以下等式:

该图看起来与我在上面用来大致匹配数据的紫色曲线非常相似:

现在，我有一些(希望是正确的)结论和问题:

• 首先，我的方法是否有效？
• 我想出的函数是否真的描述了操作次数与N之间的关系？
• 我认为这是最有趣的一个 - 我想知道是什么导致了 N=2 和所有其他人之间如此显着的差异？对于我的所有测试数据，我始终得到这种模式。

另外:

• 该函数的最小值在 e≈2.718... 中，它更接近 3 而不是 2。此外，f(3) < f(2) 成立.鉴于我得出的方程式是正确的，我认为这意味着三等分法实际上可能比二等分法更有效。这似乎有点违反直觉，但测量结果似乎承认了这一点。这是对的吗？
• 如果是这样，为什么与二分法相比，三分法似乎如此不受欢迎？

谢谢

Answer 1

我评论的是一般问题，而不是我不完全理解的特定代码。

假设在长度为 L 的区间内有一个已知的单根，并且所需的精度为 ε，您将需要 log(L/ε)/log(N) 个 segmentation 阶段。每个 segmentation 阶段都需要对函数进行 N-1 次评估(不是 N)，以确定 N 中哪个子区间包含根。

因此，忽略开销，总成本与 (N-1)/log(N) 成正比。这个比率的值是，从 N=2 开始:

1.44, 1.82, 2.16, 2.49, 2.79...

及更高。

因此，理论最优值是 N=2。这就是不使用三等分的原因。