辛普森法求定积分

在求解计算几何或者概率等问题时，有时需要用到定积分，有些语言标准库没有求定积分的函数，好在自己写也不算太麻烦。原理不讲了，可以参考数值计算的书籍，直接上代码:

/*
 * calculate the integral(f(x) for low <= x <= high), divide into n section
 * n must be a POSITIVE and EVEN integer
 */
double simpson(double low, double high, double (*f)(double), int n) {
    double ans = f(low) + f(high);
    int p[2] = {2, 4}, i;
    high = (high - low) / n;
    low += high;
    for (i = 1; i < n; i++) {
        ans += f(low) * p[i & 1];
        low += high;
    }
    return ans * high / 3;
}

复杂度O(n)。调用simpson(1, 2, log, 10)得到0.38629340，和准确结果 相差1e-6左右。一般来说n越大结果越精确，当然计算时间也越长。