定点的 2 次幂近似

目前，我正在使用一个小型查找表和线性插值，它非常快且足够准确（最大误差小于 0.001）。然而我想知道是否有一个更快的近似值。

由于指数的整数部分可以通过位移位来提取和计算，因此近似值只需在 [-1,1] 范围内工作 我试图找到切比雪夫多项式，但对于低阶多项式无法达到良好的精度。我猜我可以忍受 0.01 左右的最大误差，但我没有接近这个数字。高阶多项式不是一种选择，因为它们比我当前的基于查找表的解决方案效率低得多。

由于没有说明具体的定点格式，我将演示使用表查找的可能替代方案s15.16定点运算，相当常用。基本思想是分割输入a成不可分割的一部分i和小数部分f，使得f在 [-0.5,0.5] 中，然后使用极小极大多项式近似exp2(f)在 [-0.5, 0.5] 上并根据i.

可以使用 Mathematica、Maple 或 Sollya 等工具生成极小极大近似。如果这些工具均不可用，则可以使用 Remez 算法的自定义实现来生成极小极大近似值。

应使用霍纳方案来评估多项式。由于使用定点算术，多项式的求值应在中间步骤中将操作数缩放至最大可能范围（即没有溢出），以优化计算的精度。

下面的 C 代码假设应用于有符号整数数据类型的右移会导致算术移位运算，因此负操作数会被适当移位。这是not由 ISO C 标准保证，但根据我的经验，它可以与各种工具链一起正常工作。在最坏的情况下，内联汇编可用于强制生成所需的算术右移指令。

测试的输出包含在fixed_exp2()下面的实现应该如下所示：

testing fixed_exp2 with inputs in [-5.96484, 15)
max. rel. err = 0.000999758

这表明区间 [-5.96484, 15) 内的输入满足所需的 0.001 误差界限。

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <math.h>

/* compute exp2(a) in s15.16 fixed-point arithmetic, -16 < a < 15 */
int32_t fixed_exp2 (int32_t a)
{
    int32_t i, f, r, s;
    /* split a = i + f, such that f in [-0.5, 0.5] */
    i = (a + 0x8000) & ~0xffff; // 0.5
    f = a - i;   
    s = ((15 << 16) - i) >> 16;
    /* minimax approximation for exp2(f) on [-0.5, 0.5] */
    r = 0x00000e20;                 // 5.5171669058037949e-2
    r = (r * f + 0x3e1cc333) >> 17; // 2.4261112219321804e-1
    r = (r * f + 0x58bd46a6) >> 16; // 6.9326098546062365e-1
    r = r * f + 0x7ffde4a3;         // 9.9992807353939517e-1
    return (uint32_t)r >> s;
}

double fixed_to_float (int32_t a)
{
    return a / 65536.0;
}

int main (void)
{
    double a, res, ref, err, maxerr = 0.0;
    int32_t x, start, end;

    start = 0xfffa0900;
    end = 0x000f0000;
    printf ("testing fixed_exp2 with inputs in [%g, %g)\n",  
            fixed_to_float (start), fixed_to_float (end));

    for (x = start; x < end; x++) {
        a = fixed_to_float (x);
        ref = exp2 (a);
        res = fixed_to_float (fixed_exp2 (x));
        err = fabs (res - ref) / ref;
        if (err > maxerr) {
            maxerr = err;
        }
    }
    printf ("max. rel. err = %g\n", maxerr);
    return EXIT_SUCCESS;
}