二分根查找分割故障

Question

我使用下面的代码来使用简单的二分法查找函数的根

#include <stdio.h>
#include <stdlib.h>

typedef float (*continous_function)(float);

static const float epsilon = 0.0000001;

#if __STDC__
static __inline float fabsf(float x)
{
        return x >=0 ? x : -1*x;
}
#else
#include <math.h>
#endif

float poly_1(float x)
{
        return x*x*x+2*x*x+3;
}

float poly_2(float x)
{
        return 2*x + 3;
}

float poly_3(float x)
{
        return 5*x*x*x*x*x+3*x*x*x+2*x+7;
}

static __inline void swap_in_place(float *a, float *b)
{
        float tmp = *a;
        *a = *b;
        *b = tmp;
}

float bisection_root(continous_function f, float a, float b)
{

        float neg = f(a);
        float pos = f(b);
        float c = 0.5 * (a + b);
        float mid;

        if (neg * pos > 0) {
                /* neg and pos should have different sizes */
                abort();
        }

        if (neg > 0) {
                /* Ensure f(a)=neg is negative */
                swap_in_place(&neg, &pos);
                swap_in_place(&a, &b);
        }

        mid = f(c);

        if (fabsf(mid) < epsilon) {
                return c;
        } else {
                if (mid > 0)
                        return bisection_root(f, a, c);
                else
                        return bisection_root(f, c, b);
        }

}

int main()
{
        {
                float a = -5;
                float b = 2;
                printf("Root of x^3+2*x^2+3 is %f\n", bisection_root(poly_1,a,b));
        }

        {
                float a = -2;
                float b = 0;
                printf("Root of 2*x+3 is %f\n", bisection_root(poly_2,a,b));
        }

        {
                float a = -1;
                float b = 0;
                printf("Root of 5*x^5+3*x^3+2*x+7 is %f\n", bisection_root(poly_3,a,b));
        }

        return 0;
}

该程序在windows xp (32位)上编译时，使用混合gcc造成分割错误.

当epsilon的十进制数减少时，可以避免分割错误。因此，我得出结论，分割错误与溢出有关。

我想知道为什么和如何发生这个错误，这样我就可以找到一种可靠的方法来设置epsilon或者修复可能导致问题的其他错误。

Answer 1

static const float epsilon = 0.0000001;

不需要有一个浮动，其多项式的值是从0到epsilon的距离。特别是，如果根为x的较大值，则多项式可能从小于-epsilon跳到一个浮点与其后继值之间的大于+epsilon。

在这种情况下，以及在其他许多情况下，您的算法将循环，因为您使用递归实现了它，而C编译器通常不保证尾调用优化，这个无限循环可能导致分段错误(当堆栈满时)。

无论使用递归还是简单的while循环，解决方案都适用于限制迭代次数。

注意:您应该阅读有关计算多项式的霍纳方案。