0

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

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

此程序在使用 mingw gcc 在 windows xp（32 位）上编译时会导致分段错误。

当小数位数epsilon减少时，可以避免分段错误。因此，我得出结论，分段错误与溢出有关。

我想知道此错误发生的原因和确切方式，以便我可以找到一种可靠的方法来设置 epsilon 或修复可能导致问题的其他错误。

4

1 回答 1

1 
static const float epsilon = 0.0000001;

不需要有一个浮点数，其多项式的值epsilon与 0 相距甚远。特别是如果根是 的较大值x，则多项式可能会从小于-epsilon到大于+epsilon一个浮点数与其后继.

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

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

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

于 2015-03-24T12:26:59.147 回答