互补误差函数 erfcf() 的可向量化实现

2023-11-23

互补误差函数,erfc,是与标准正态分布密切相关的特殊函数。它经常用于统计学和自然科学(例如扩散问题),其中需要考虑该分布的“尾部”,并使用误差函数,erf,因此不适合。

ISO C99 标准数学库中提供了互补误差函数,如下所示:erfcf, erfc, and erfcl;这些随后也被 ISO C++ 采用。因此,可以在该库的开源实现中轻松找到源代码,例如glibc.

然而,许多现有的实现本质上是标量,而现代处理器硬件是面向 SIMD 的(要么是显式的,如 x86 CPU,要么隐式的,如 GPU)。出于性能原因,非常需要可矢量化的实现。这意味着需要避免分支,除非作为选择分配的一部分。同样,没有指出表的广泛使用,因为并行查找通常效率低下。

如何构建单精度函数的高效可向量化实现erfcf()?准确度,如测量ulp,应该与 glibc 的标量实现大致相同,其最大误差为 3.12575 ulps(通过详尽的测试确定)。可以假设融合乘加 (FMA) 的可用性,因为所有主要处理器架构(CPU 和 GPU)目前都提供它。在处理浮点状态标志和errno可以忽略,非正规数、无穷大和 NaN 应根据 ISO C 的 IEEE 754 绑定进行处理。


在研究了各种方法之后,最合适的方法是以下论文中提出的算法:

M. M. Shepherd and J. G. Laframboise, "Chebyshev Approximation of (1 + 2 x) exp(x2) erfc x in 0 ≤ x < ∞." Mathematics of Computation, Volume 36, No. 153, January 1981, pp. 249-253 (online copy)

The basic idea of the paper is to create an approximation to (1 + 2 x) exp(x2) erfc(x), from which we can compute erfcx(x) by simply dividing by (1 + 2 x), and erfc(x) by then multiplying with exp(-x2). The tightly bounded range of the function, with function values roughly in [1, 1.3], and its general "flatness" lend itself well to polynomial approximation. Numerical properties of this approach are further improved by narrowing the approximation interval: the original argument x is transformed by q = (x - K) / (x + K), where K is a suitably chosen constant, followed by computing p (q), where p is a polynomial.

由于 erfc -x= 2 - erfcx,我们只需要考虑区间[0, ∞],通过这个变换映射到区间[-1, 1]。对于 IEEE-754 单精度,erfcf()消失(变为零)x> 10.0546875,所以只需要考虑xε [0, 10.0546875)。对于这个范围,K 的“最佳”值是多少?我知道没有任何数学分析可以提供答案,论文根据实验建议 K = 3.75。

人们可以很容易地确定,对于单精度计算,9 次极小极大多项式近似足以满足该一般附近的各种 K 值。使用 Remez 算法系统地生成此类近似值,K 在 1.5 和 4 之间以 1/16 的步长变化,观察到 K = {2, 2.625, 3.3125} 时的近似误差最低。其中,K = 2 是最有利的选择,因为它有助于非常准确地计算 (x-K)/(x+ K),如图所示这个问题.

值 K = 2 且输入域为x建议有必要使用变体4我的答案,然而,一旦可以通过实验证明,较便宜的变体 5 在这里达到了相同的精度,这可能是由于近似函数的斜率非常浅q> -0.5,这会导致参数出现任何错误q大约减少十倍。

由于计算erfc()除了初始近似之外,还需要后处理步骤,显然这两种计算的精度都必须很高,才能获得足够准确的最终结果。必须使用纠错技术。

One observes that the most significant coefficient in the polynomial approximation of (1 + 2 x) exp(x2) erfc(x) is of the form (1 + s), where s < 0.5. This means we can represent the leading coefficient more accurately by splitting off 1, and only using s in the polynomial. So instead of computing a polynomial p(q), then multiplying by the reciprocal r = 1 / (1 + 2 x), it is mathematically equivalent but numerically advantageous to compute the core approximation as p(q) + 1, and use p to compute fma (p, r, r).

通过计算初始商可以提高除法的准确性q从倒数r,计算残差e = p+1 - q* (1 + 2x)在 FMA 的帮助下,然后使用e应用修正q = q + (e * r),再次使用 FMA。

Exponentiation has error magnification properties, therefore computation of e-x2 must be performed carefully. The availability of FMA trivially allows the computation of -x2 as a double-float shigh:slow. ex is its own derivative, so one can compute eshigh:slow as eshigh + eshigh * slow. This computation can be combined with the multiplication of the previous intermediate result r to yield r = r * eshigh + r * eshigh * slow. By use of FMA, one ensures that the most significant term r * eshigh is computed as accurately as possible.

将上述步骤与一些处理异常情况和负参数的简单选择相结合,得到以下 C 代码:

float my_expf (float);

/* Compute complementary error function.
 *
 * Based on: M. M. Shepherd and J. G. Laframboise, "Chebyshev Approximation of 
 * (1+2x)exp(x^2)erfc x in 0 <= x < INF", Mathematics of Computation, Vol. 36,
 * No. 153, January 1981, pp. 249-253.
 *
 * maximum error: 2.65184 ulps
 */  
float my_erfcf (float x)
{
    float a, d, e, p, q, r, s, t;

    a = fabsf (x);
    
    /* Compute q = (a-2)/(a+2) accurately. [0, 10.0546875] -> [-1, 0.66818] */
    p = a + 2.0f;
    r = 1.0f / p;
    q = fmaf (-4.0f, r, 1.0f);
    t = fmaf (q + 1.0f, -2.0f, a); 
    e = fmaf (-a, q, t); 
    q = fmaf (r, e, q); 
    
    /* Approximate (1+2*a)*exp(a*a)*erfc(a) as p(q)+1 for q in [-1, 0.66818] */
    p =             -0x1.a4a000p-12f;  // -4.01139259e-4
    p = fmaf (p, q, -0x1.42a260p-10f); // -1.23075210e-3
    p = fmaf (p, q,  0x1.585714p-10f); //  1.31355342e-3
    p = fmaf (p, q,  0x1.1adcc4p-07f); //  8.63227434e-3
    p = fmaf (p, q, -0x1.081b82p-07f); // -8.05991981e-3
    p = fmaf (p, q, -0x1.bc0b6ap-05f); // -5.42046614e-2
    p = fmaf (p, q,  0x1.4ffc46p-03f); //  1.64055392e-1
    p = fmaf (p, q, -0x1.540840p-03f); // -1.66031361e-1
    p = fmaf (p, q, -0x1.7bf616p-04f); // -9.27639827e-2
    p = fmaf (p, q,  0x1.1ba03ap-02f); //  2.76978403e-1

    /* Divide (1+p) by (1+2*a) ==> exp(a*a)*erfc(a) */
    d = fmaf (2.0f, a, 1.0f);
    r = 1.0f / d;
    q = fmaf (p, r, r); // q = (p+1)/(1+2*a)
    e = fmaf (fmaf (q, -a, 0.5f), 2.0f, p - q); // residual: (p+1)-q*(1+2*a)
    r = fmaf (e, r, q);

    /* Multiply by exp(-a*a) ==> erfc(a) */
    s = a * a; 
    e = my_expf (-s);
    t = fmaf (-a, a, s);
    r = fmaf (r, e, r * e * t);

    /* Handle NaN, Inf arguments to erfc() */
    if (!(a < INFINITY)) r = x + x;

    /* Clamp result for large arguments */
    if (a > 10.0546875f) r = 0.0f;
    
    /* Handle negative arguments to erfc() */
    if (x < 0.0f) r = 2.0f - r; 

    return r;
}

/* Compute exponential base e. Maximum ulp error = 0.86565 */
float my_expf (float a)
{
    float c, f, r;
    int i;

    // exp(a) = exp(i + f); i = rint (a / log(2))
    c = 0x1.800000p+23f; // 1.25829120e+7
    r = fmaf (0x1.715476p+0f, a, c) - c; // 1.44269502e+0
    f = fmaf (r, -0x1.62e400p-01f, a); // -6.93145752e-1 // log_2_hi
    f = fmaf (r, -0x1.7f7d1cp-20f, f); // -1.42860677e-6 // log_2_lo
    i = (int)r;
    // approximate r = exp(f) on interval [-log(2)/2,+log(2)/2]
    r =             0x1.694000p-10f;  // 1.37805939e-3
    r = fmaf (r, f, 0x1.125edcp-07f); // 8.37312452e-3
    r = fmaf (r, f, 0x1.555b5ap-05f); // 4.16695364e-2
    r = fmaf (r, f, 0x1.555450p-03f); // 1.66664720e-1
    r = fmaf (r, f, 0x1.fffff6p-02f); // 4.99999851e-1
    r = fmaf (r, f, 0x1.000000p+00f); // 1.00000000e+0
    r = fmaf (r, f, 0x1.000000p+00f); // 1.00000000e+0
    // exp(a) = 2**i * exp(f);
    r = ldexpf (r, i);
    if (!(fabsf (a) < 104.0f)) {
        r = a + a; // handle NaNs
        if (a < 0.0f) r = 0.0f;
        if (a > 0.0f) r = INFINITY;
    }
    return r;
}

我用我自己的实现expf()在上面的代码中将我的工作与expf()不同计算平台上的实现。但任何实施expf()其最大误差接近 0.5 ulp 应该可以很好地工作。如上图,即使用时my_expf(), my_erfcf()最大错误为 2.65184 ulps。

提供了一个可向量化的expf()如果可用,上面的代码应该可以毫无问题地进行矢量化。我用英特尔编译器 13.1.3.198 进行了快速检查。我打电话给my_erfcf()在循环中添加#include <mathimf.h>,替换了对my_expf()打电话给expf(),然后使用这些命令行开关进行编译:

/Qstd=c99 /O3 /QxCORE-AVX2 /fp:precise /Qfma /Qimf-precision:high:expf /Qvec_report=2

英特尔编译器报告该循环已矢量化,我通过检查反汇编的二进制代码进行了双重检查。

Since my_erfcf()仅使用倒数而不是完全除法,可以使用快速倒数实现,前提是它们提供几乎正确舍入的结果。对于在硬件中提供快速单精度倒数近似的处理器,可以通过将其与三次收敛的 Halley 迭代相结合来轻松实现。针对 x86 处理器的此方法的(标量)示例是:

/* Compute 1.0f / a almost correctly rounded. Halley iteration with cubic convergence */
float fast_recipf (float a)
{
    __m128 t;
    float e, r;
    t = _mm_set_ss (a);
    t = _mm_rcp_ss (t);
    _mm_store_ss (&r, t);
    e = fmaf (r, -a, 1.0f);
    e = fmaf (e, e, e);
    r = fmaf (e, r, r);
    return r;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

互补误差函数 erfcf() 的可向量化实现 的相关文章

随机推荐

  • Rails 5 db:重置不起作用

    我想重置 Rails 5 项目的数据库 但是rails db reset命令不起作用 错误信息 Permission denied unlink internal C sites5 dawnrebirth db development sq
  • 在 div 中包围希伯来语和英语文本

    我正在尝试在段落中的希伯来语和英语句子周围添加跨度标签 例如 那么 到底怎么样了 会变成 span so span span span span all whats up span span span 我一直在尝试使用正则表达式 但它只是删
  • 将html模板文件合并到一个JS文件中

    我有 HTML 模板文件 下划线模板语法 这些文件以 HTML 格式保存 因此很容易编辑 IDE 语法突出显示 我不想用ajax获取它们 而是将它们全部组合起来并将它们包含为js file 使用 GULP 作为我的任务运行程序 我希望它能以
  • 如何限制通过 cin 输入的字符数?

    我希望限制用户可以输入的字符数 使用cin 例如 我可能希望将其限制为两个字符 我该怎么做 我的代码如下所示 cin gt gt var 您可以使用setw cin gt gt setw 2 gt gt var http www cplus
  • NSPredicate iPhone 3.2 SDK核心数据“IN子句”NSInvalidArgumentException异常

    我有一个收藏Calendar对象并希望通过它们来查询它们service id财产 我在 iPhone 3 2 SDK 上使用 Core Data 和 sqlite calendars是一个 NSArray 结果NSFetchRequest
  • 谁最终决定什么是通用类型?

    我有这个功能 public static T2 MyFunc
  • 在 Plone 构建设置中查找需求规格

    我有一个 Plone 网站 大约 4 2 4 从version txt在根目录中 我想更新到最新版本 我发现这个操作方法 截至目前 4 3 4 我继承了过多的固定版本 这些版本没有记录并且可能已经过时 当评论我的versions cfg u
  • 如何设置 JSplitPane-Divider 折叠/展开状态?

    我有一个带有 JSplitPane 的 JFrame 它是 OneTouchExpandable 我想记住 JFrame 上 JSplitPane 的最后一个分隔符位置 并在重新打开 JFrame 时恢复位置 它工作得很好 但如果用户通过
  • 使用存储库的工作单元模式中的依赖项注入

    我想创建一个工作单元类 以类似的方式包装存储库this 我遇到的问题是尝试通过用 IRepository 接口替换示例中的通用存储库来实现依赖项注入 在链接文章的 uow 中 他们使用 getter 来检查存储库是否已实例化 如果没有则实例
  • npm install puppeteer 显示权限被拒绝错误

    我无法安装puppeteer作为项目依赖项 我尝试重新安装节点 有人知道如何解决这个问题吗 运行 Ubuntu 17 10 x64 sudo apt get purge nodejs curl sL https deb nodesource
  • 新手势 - 从左向右滑动 - 作为旧应用程序中 UINavigationController 中“后退”按钮的快捷方式

    iOS 7 采用了一种新手势 即在屏幕上从左向右滑动作为 UINavigationController 中 后退 按钮的快捷方式 我的应用程序似乎没有免费获取此行为 我需要做什么才能让我的 iOS 应用程序 在 Xcode 4 6 3 中为
  • Android Camera2 API 显示处理后的预览图像

    新的 Camera 2 API 与旧的有很大不同 向管道的用户部分显示操纵的相机帧让我感到困惑 我知道有很好的解释使用 Android L 和 Camera2 API 处理相机预览图像数据但显示帧仍然不清楚 我的问题是 在经过一些处理后 在
  • 用传单绘制特定国家的地图

    我想使用该包leaflet用R绘制特定国家的地图 如意大利 西班牙等 我用函数检查了基本示例setView 我尝试为纬度和经度的 arg 给出两个值的向量 m lt leaflet gt addTiles gt Add default Op
  • NUMA 获取当前节点/核心

    我在 Linux 上使用 libnuma 我的线程应该知道它们正在运行的节点 核心 是否有可能以某种方式获取当前线程的节点 核心 我已经浏览了文档 但没有找到这样的功能 我找到了这个解决方案 include
  • 限制完成时的 IntelliJ IDEA 导入建议

    当我输入需要导入的类的名称时 IntelliJ 会亲切地弹出一个建议列表 然而 大多数时候 这些建议是我永远不想导入的东西 尤其是偶然的 比如java awt 有没有办法防止我永远不会导入的包出现在完成列表中 我已经搜索了这些选项 但没有找
  • 使用 MPI_Bcast 进行 MPI 通信

    我正在尝试使用 MPI Bcast 将消息从根节点广播到所有其他节点 然而 每当我运行这个程序时 它总是在开始时挂起 有人知道这是怎么回事吗 include
  • Cassandra 中的高基数和低基数

    我不断遇到这些术语 high cardinality and low cardinality in Cassandra 我不明白它们到底是什么意思 它们对查询有什么影响以及首选是什么 请举例说明 因为这样很容易理解 X 的基数只不过是组成
  • 使用 powershell 将路径永久添加到 Windows 似乎不起作用

    我跟着这个程序为了使用 powershell 永久添加 SumatraPDF 的路径 链接中的最后几个命令旨在检查路径是否确实已添加 当我使用以下命令访问路径时 get itemproperty path Registry HKEY LOC
  • ggplot2:将不连续的持续时间绘制为条形图

    我使用 ggplot 将各种事件绘制为事件开始的日期 x 轴 和开始时间 y 轴 的函数 数据 代码如下 date lt c 2013 06 05 2013 06 05 2013 06 04 2013 06 04 2013 06 04 20
  • 互补误差函数 erfcf() 的可向量化实现

    互补误差函数 erfc 是与标准正态分布密切相关的特殊函数 它经常用于统计学和自然科学 例如扩散问题 其中需要考虑该分布的 尾部 并使用误差函数 erf 因此不适合 ISO C99 标准数学库中提供了互补误差函数 如下所示 erfcf er