我一直在研究。net反汇编和GCC源代码,但似乎在任何地方都找不到sin()和其他数学函数的实际实现…他们似乎总是在引用别的东西。

有人能帮我找到他们吗?我觉得不太可能运行C语言的所有硬件都支持三角函数,所以一定有软件算法,对吧?


我知道有几种方法可以计算函数,并且为了好玩,我写了自己的例程来使用泰勒级数计算函数。我很好奇生产语言是如何做到这一点的,因为我的所有实现总是慢几个数量级,尽管我认为我的算法非常聪明(显然不是)。


当前回答

计算正弦/余弦/正切其实很容易通过代码使用泰勒级数来实现。自己写一个只需5秒钟。

整个过程可以用这个方程来概括:

下面是我为C语言写的一些例程:

double _pow(double a, double b) {
    double c = 1;
    for (int i=0; i<b; i++)
        c *= a;
    return c;
}

double _fact(double x) {
    double ret = 1;
    for (int i=1; i<=x; i++) 
        ret *= i;
    return ret;
}

double _sin(double x) {
    double y = x;
    double s = -1;
    for (int i=3; i<=100; i+=2) {
        y+=s*(_pow(x,i)/_fact(i));
        s *= -1;
    }  
    return y;
}
double _cos(double x) {
    double y = 1;
    double s = -1;
    for (int i=2; i<=100; i+=2) {
        y+=s*(_pow(x,i)/_fact(i));
        s *= -1;
    }  
    return y;
}
double _tan(double x) {
     return (_sin(x)/_cos(x));  
}

其他回答

无论何时这样一个函数被求值,那么在某种程度上很可能有:

内插的值表(用于快速,不准确的应用程序-例如计算机图形) 收敛于期望值的级数的计算——可能不是泰勒级数,更可能是基于像克伦肖-柯蒂斯这样的奇异正交。

如果没有硬件支持,那么编译器可能会使用后一种方法,只发出汇编代码(没有调试符号),而不是使用c库——这让您在调试器中跟踪实际代码变得很棘手。

在GNU libm中,sin的实现依赖于系统。因此,您可以在sysdeps的适当子目录中找到每个平台的实现。

一个目录包含一个由IBM贡献的C语言实现。自2011年10月以来,这是在典型的x86-64 Linux系统上调用sin()时实际运行的代码。它显然比汇编指令中的f_f快。源代码:sysdeps/ieee754/dbl-64/s_sin.c,查找__sin (double x)。

这段代码非常复杂。没有一种软件算法在整个x值范围内尽可能快且准确,因此库实现了几种不同的算法,它的第一项工作是查看x并决定使用哪种算法。

When x is very very close to 0, sin(x) == x is the right answer. A bit further out, sin(x) uses the familiar Taylor series. However, this is only accurate near 0, so... When the angle is more than about 7°, a different algorithm is used, computing Taylor-series approximations for both sin(x) and cos(x), then using values from a precomputed table to refine the approximation. When |x| > 2, none of the above algorithms would work, so the code starts by computing some value closer to 0 that can be fed to sin or cos instead. There's yet another branch to deal with x being a NaN or infinity.

这段代码使用了一些我以前从未见过的数值技巧,尽管据我所知,它们可能在浮点专家中很有名。有时几行代码需要几段文字来解释。例如,这两条线

double t = (x * hpinv + toint);
double xn = t - toint;

(有时)用于将x减小到接近0的值,该值与x相差π/2的倍数,特别是xn × π/2。这种没有划分或分支的方式相当聪明。但是没有任何评论!


旧的32位版本的GCC/glibc使用fsin指令,这对于某些输入是非常不准确的。有一篇精彩的博客文章用两行代码说明了这一点。

fdlibm在纯C中实现sin要比glibc简单得多,而且注释很好。源代码:fdlibm/s_sin.c和fdlibm/k_sin.c

它如何做到这一点的本质在于杰拉德·惠特利的《应用数值分析》节选:

当你的软件程序要求计算机获取一个值时 或者,你有没有想过它是如何得到 如果它能计算的最强大的函数是多项式? 它不会在表中查找这些并进行插值!相反, 计算机逼近除多项式以外的所有函数 一个多项式,可以精确地给出值。

上面要提到的几点是,一些算法实际上是从表中插值的,尽管只是在前几次迭代中。还要注意它是如何提到计算机利用近似多项式而没有指定哪种类型的近似多项式。正如本文中其他人指出的那样,在这种情况下,切比雪夫多项式比泰勒多项式更有效。

切比雪夫多项式,正如在另一个答案中提到的,是函数和多项式之间的最大差异尽可能小的多项式。这是一个很好的开始。

在某些情况下,最大误差不是你感兴趣的,而是最大相对误差。例如,对于正弦函数,x = 0附近的误差应该比较大的值小得多;你想要一个小的相对误差。所以你可以计算sinx / x的切比雪夫多项式,然后把这个多项式乘以x。

Next you have to figure out how to evaluate the polynomial. You want to evaluate it in such a way that the intermediate values are small and therefore rounding errors are small. Otherwise the rounding errors might become a lot larger than errors in the polynomial. And with functions like the sine function, if you are careless then it may be possible that the result that you calculate for sin x is greater than the result for sin y even when x < y. So careful choice of the calculation order and calculation of upper bounds for the rounding error are needed.

例如,sinx = x - x^3/6 + x^5 / 120 - x^7 / 5040…如果你天真地计算sinx = x * (1 - x^2/6 + x^4/120 - x^6/5040…),那么括号中的函数是递减的,如果y是x的下一个大的数字,那么有时siny会小于sinx。相反,计算sinx = x - x^3 * (1/6 - x^2/ 120 + x^4/5040…),这是不可能发生的。

例如,在计算切比雪夫多项式时,通常需要将系数四舍五入到双倍精度。但是,虽然切比雪夫多项式是最优的,但系数舍入为双精度的切比雪夫多项式并不是具有双精度系数的最优多项式!

For example for sin (x), where you need coefficients for x, x^3, x^5, x^7 etc. you do the following: Calculate the best approximation of sin x with a polynomial (ax + bx^3 + cx^5 + dx^7) with higher than double precision, then round a to double precision, giving A. The difference between a and A would be quite large. Now calculate the best approximation of (sin x - Ax) with a polynomial (b x^3 + cx^5 + dx^7). You get different coefficients, because they adapt to the difference between a and A. Round b to double precision B. Then approximate (sin x - Ax - Bx^3) with a polynomial cx^5 + dx^7 and so on. You will get a polynomial that is almost as good as the original Chebyshev polynomial, but much better than Chebyshev rounded to double precision.

Next you should take into account the rounding errors in the choice of polynomial. You found a polynomial with minimum error in the polynomial ignoring rounding error, but you want to optimise polynomial plus rounding error. Once you have the Chebyshev polynomial, you can calculate bounds for the rounding error. Say f (x) is your function, P (x) is the polynomial, and E (x) is the rounding error. You don't want to optimise | f (x) - P (x) |, you want to optimise | f (x) - P (x) +/- E (x) |. You will get a slightly different polynomial that tries to keep the polynomial errors down where the rounding error is large, and relaxes the polynomial errors a bit where the rounding error is small.

所有这些将使您轻松地获得最多0.55倍于最后一位的舍入误差,其中+,-,*,/的舍入误差最多为0.50倍于最后一位。

盲汉回答的改进版代码

#define EPSILON .0000000000001
// this is smallest effective threshold, at least on my OS (WSL ubuntu 18)
// possibly because factorial part turns 0 at some point
// and it happens faster then series element turns 0;
// validation was made against sin() from <math.h>
double ft_sin(double x)
{
    int k = 2;
    double r = x;
    double acc = 1;
    double den = 1;
    double num = x;

//  precision drops rapidly when x is not close to 0
//  so move x to 0 as close as possible
    while (x > PI)
        x -= PI;
    while (x < -PI)
        x += PI;
    if (x > PI / 2)
        return (ft_sin(PI - x));
    if (x < -PI / 2)
        return (ft_sin(-PI - x));
//  not using fabs for performance reasons
    while (acc > EPSILON || acc < -EPSILON)
    {
        num *= -x * x;
        den *= k * (k + 1);
        acc = num / den;
        r += acc;
        k += 2;
    }
    return (r);
}