atan() 参考实现中奇怪的幂级数系数

问题描述 投票：0回答：1

glibc
（更准确地说，
libm
）和许多其他 C 库包含以下 
atan()
函数的软件实现（参见此处）：

/* s_atanf.c -- float version of s_atan.c.
 * Conversion to float by Ian Lance Taylor, Cygnus Support, [email protected].
 */

/*
 * ====================================================
 * Copyright (C) 1993 by Sun Microsystems, Inc. All rights reserved.
 *
 * Developed at SunPro, a Sun Microsystems, Inc. business.
 * Permission to use, copy, modify, and distribute this
 * software is freely granted, provided that this notice
 * is preserved.
 * ====================================================
 */

#if defined(LIBM_SCCS) && !defined(lint)
static char rcsid[] = "$NetBSD: s_atanf.c,v 1.4 1995/05/10 20:46:47 jtc Exp $";
#endif

#include <float.h>
#include <math.h>
#include <math_private.h>
#include <math-underflow.h>
#include <libm-alias-float.h>

static const float atanhi[] = {
  4.6364760399e-01, /* atan(0.5)hi 0x3eed6338 */
  7.8539812565e-01, /* atan(1.0)hi 0x3f490fda */
  9.8279368877e-01, /* atan(1.5)hi 0x3f7b985e */
  1.5707962513e+00, /* atan(inf)hi 0x3fc90fda */
};

static const float atanlo[] = {
  5.0121582440e-09, /* atan(0.5)lo 0x31ac3769 */
  3.7748947079e-08, /* atan(1.0)lo 0x33222168 */
  3.4473217170e-08, /* atan(1.5)lo 0x33140fb4 */
  7.5497894159e-08, /* atan(inf)lo 0x33a22168 */
};

static const float aT[] = {
  3.3333334327e-01, /* 0x3eaaaaaa */
 -2.0000000298e-01, /* 0xbe4ccccd */
  1.4285714924e-01, /* 0x3e124925 */
 -1.1111110449e-01, /* 0xbde38e38 */
  9.0908870101e-02, /* 0x3dba2e6e */
 -7.6918758452e-02, /* 0xbd9d8795 */
  6.6610731184e-02, /* 0x3d886b35 */
 -5.8335702866e-02, /* 0xbd6ef16b */
  4.9768779427e-02, /* 0x3d4bda59 */
 -3.6531571299e-02, /* 0xbd15a221 */
  1.6285819933e-02, /* 0x3c8569d7 */
};

static const float
one   = 1.0,
huge   = 1.0e30;

float __atanf(float x)
{
    float w,s1,s2,z;
    int32_t ix,hx,id;

    GET_FLOAT_WORD(hx,x);
    ix = hx&0x7fffffff;
    if(ix>=0x4c000000) {    /* if |x| >= 2^25 */
        if(ix>0x7f800000)
        return x+x;     /* NaN */
        if(hx>0) return  atanhi[3]+atanlo[3];
        else     return -atanhi[3]-atanlo[3];
    } if (ix < 0x3ee00000) {    /* |x| < 0.4375 */
        if (ix < 0x31000000) {  /* |x| < 2^-29 */
        math_check_force_underflow (x);
        if(huge+x>one) return x;    /* raise inexact */
        }
        id = -1;
    } else {
    x = fabsf(x);
    if (ix < 0x3f980000) {      /* |x| < 1.1875 */
        if (ix < 0x3f300000) {  /* 7/16 <=|x|<11/16 */
        id = 0; x = ((float)2.0*x-one)/((float)2.0+x);
        } else {            /* 11/16<=|x|< 19/16 */
        id = 1; x  = (x-one)/(x+one);
        }
    } else {
        if (ix < 0x401c0000) {  /* |x| < 2.4375 */
        id = 2; x  = (x-(float)1.5)/(one+(float)1.5*x);
        } else {            /* 2.4375 <= |x| < 2^66 */
        id = 3; x  = -(float)1.0/x;
        }
    }}
    /* end of argument reduction */
    z = x*x;
    w = z*z;
    /* break sum from i=0 to 10 aT[i]z**(i+1) into odd and even poly */
    s1 = z*(aT[0]+w*(aT[2]+w*(aT[4]+w*(aT[6]+w*(aT[8]+w*aT[10])))));
    s2 = w*(aT[1]+w*(aT[3]+w*(aT[5]+w*(aT[7]+w*aT[9]))));
    if (id<0) return x - x*(s1+s2);
    else {
        z = atanhi[id] - ((x*(s1+s2) - atanlo[id]) - x);
        return (hx<0)? -z:z;
    }
}
libm_alias_float (__atan, atan)

我了解该函数的工作原理，除了 

aT[]
数组中的值。实际工作发生在以下几行参数减少之后：

z = x*x;
w = z*z;
/* break sum from i=0 to 10 aT[i]z**(i+1) into odd and even poly */
s1 = z*(aT[0]+w*(aT[2]+w*(aT[4]+w*(aT[6]+w*(aT[8]+w*aT[10])))));
s2 = w*(aT[1]+w*(aT[3]+w*(aT[5]+w*(aT[7]+w*aT[9]))));
if (id<0) return x - x*(s1+s2);
/* ... */

如果我们在最后一行进行乘法和减法，我们就得到

atan()
的幂级数：
x - 1/3 * x^3 + 1/5 * x^5 - 1/7 * x^7 ...
。然而，
aT[]
数组中的系数与幂级数的系数不同：

第一个与预期一致，因为它是最接近 

1/3
的浮点数。接下来的值越来越偏离预期值，每一个都比前一个多，直到最后一个，预计为 
1/23
（如果截断为浮点精度则为 
4.347826e-2
），但实际上是 
1.6285819933e-02
。

为什么系数与预期值偏差如此之大？这是一个数学技巧，可以缓解幂级数必须在某个点（在本例中为 

x^23
）中止这一事实吗？

c glibc ieee-754 atan
1个回答
0
投票

正如评论中已经提到的，系数是多项式极小极大近似的系数 P，这里 atan(x) = x - x · P(x2)。这样的近似值 min 最大化了特定近似区间 [a, b) 上的 maximum 误差，这里是 [0, 7/16)。

多项式极小极大近似具有特定的性质。对于次数为 n 的多项式，差分函数 d(x) = f(x) - P(x) 具有 n+2 极值，并且相邻极值具有相反的符号。这就是所谓的等振荡特性。 a 和 b 处各有一个极值。一般来说，极小极大近似的系数必须以数值方式确定。最常用的程序称为 Remez 算法 1, 2，由苏联数学家 Evgeny Remez 提出。像 Mathematica 或 Maple 这样的软件包有这方面的设施，开源 Sollya 工具。

基本思想很简单：选择 n+2 值 xi 并建立 n+2 方程 P(xi) ± d = f(xi)，其中d 的符号在连续的 i 之间交替。这会产生 n+2 未知数中的 n+2 方程组：n+1 系数加上 d。然后的任务是选择初始的 xi 集并对其进行操作，直到 d 最小化。虽然数学上存在一种独特的极小极大近似，但数值过程将提供可以任意接近的近极小极大近似。强烈建议以比系数目标精度高得多的精度执行这些中间计算。

当我使用 20 世纪 90 年代初用 C 编写的 Remez 算法的自定义实现生成十次多项式近似值（以相对误差作为误差标准）时，会产生以下系数：

  3.3333334327e-01f, /* 0x3eaaaaab */
 -2.0000000298e-01f, /* 0xbe4ccccd */
  1.4285714924e-01f, /* 0x3e124925 */
 -1.1111110449e-01f, /* 0xbde38e38 */
  9.0908870101e-02f, /* 0x3dba2e6e */
 -7.6918721199e-02f, /* 0xbd9d8790 */
  6.6610343754e-02f, /* 0x3d886b01 */
 -5.8333244175e-02f, /* 0xbd6eeed7 */
  4.9759168178e-02f, /* 0x3d4bd045 */
 -3.6510344595e-02f, /* 0xbd158bdf */
  1.6265589744e-02f, /* 0x3c853f6a */

这与问题代码中使用的系数集非常接近。应该注意的是，10次多项式在这里是多余的，因为这可以提供具有相对误差的近似值< 1e-17, that is, sufficient for an IEEE-754 double-precision implementation. The reason for this is presumably that the code shown was derived from a 

double
实现
atan()
。

对于使用映射到 IEEE-754 

atanf()
的计算来实现 
float
，4
 次多项式就足够了：
binary32


static const float aT[] = {
  3.3333304524e-01f, /* 0x3eaaaaa1 */
 -1.9997754693e-01f, /* 0xbe4cc6ea */
  1.4229640365e-01f, /* 0x3e11b626 */
 -1.0490779579e-01f, /* 0xbdd6d9e6 */
  5.8191072196e-02f  /* 0x3d6e59c3 */
};



1
 E. Remes，“在近似多项式的连续逼近过程中。” Comptes rendus hebdomadaires des séances de l'Académie des sciences，198，1934 年 1 月至 6 月，pp。 2063-2065（在 1934 年 6 月 4 日的会议上提出）。

2
 Eugène Remes，“关于 Tchebichef 多项式近似的计算效果。” Comptes rendus hebdomadaires des séances de l'Académie des sciences，199，1934 年 7 月至 12 月，pp。 337-340（在 1934 年 7 月 23 日的会议上提出）。
    
	

    

    


  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.