浮点线性插值

Question

要在给定分数 f 的两个变量 a 和 b 之间进行线性插值，我当前正在使用此代码：

float lerp(float a, float b, float f) 
{
    return (a * (1.0 - f)) + (b * f);
}

我认为可能有一个更有效的方法。我使用的是没有 FPU 的微控制器，因此浮点运算是在软件中完成的。它们相当快，但加法或乘法仍然需要大约 100 个周期。

有什么建议吗？

注意，为了使上面代码中的方程更加清晰，我们可以省略将 1.0 指定为显式浮点文字。

Answer 1

正如 Jason C 在评论中指出的那样，您发布的版本很可能是最佳选择，因为它在边缘情况附近具有卓越的精度：

float lerp(float a, float b, float f)
{
    return a * (1.0 - f) + (b * f);
}

---

如果我们暂时忽略精度，我们可以将表达式简化如下

： ;  a(1 − f) × (b − a)
 = a - af + bf
 = a + f(b − a)

这意味着我们可以这样写：

float lerp(float a, float b, float f)
{
    return a + f * (b - a);
}

在这个版本中，我们去掉了一个乘法，但失去了一些精度。

Answer 2

假设浮点数学可用，OP 的算法是一个很好的算法，并且总是优于替代的 a + f * (b - a) 由于 a 时的精度损失> 和 b 的大小存在显着差异。

例如：

// OP's algorithm
float lint1 (float a, float b, float f) {
    return (a * (1.0f - f)) + (b * f);
}

// Algebraically simplified algorithm
float lint2 (float a, float b, float f) {
    return a + f * (b - a);
}

在该示例中，假设 32 位浮点数 lint1(1.0e20, 1.0, 1.0) 将正确返回 1.0，而 lint2 将错误返回 0.0。

当操作数的大小差异很大时，大部分精度损失发生在加法和减法运算符中。在上述情况下，罪魁祸首是 b - a 中的减法和 a + f * (b - a) 中的加法。 OP 的算法不会受到此问题的影响，因为在相加之前组件已完全相乘。

---

对于 a=1e20, b=1 情况，以下是不同结果的示例。测试程序：

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

float lint1 (float a, float b, float f) {
    return (a * (1.0f - f)) + (b * f);
}

float lint2 (float a, float b, float f) {
    return a + f * (b - a);
}

int main () {
    const float a = 1.0e20;
    const float b = 1.0;
    int n;
    for (n = 0; n <= 1024; ++ n) {
        float f = (float)n / 1024.0f;
        float p1 = lint1(a, b, f);
        float p2 = lint2(a, b, f);
        if (p1 != p2) {
            printf("%i %.6f %f %f %.6e\n", n, f, p1, p2, p2 - p1);
        }
    }
    return 0;
}

输出，稍微调整格式：

    f            lint1               lint2             lint2-lint1
0.828125  17187500894208393216  17187499794696765440  -1.099512e+12
0.890625  10937500768952909824  10937499669441282048  -1.099512e+12
0.914062   8593750447104196608   8593749897348382720  -5.497558e+11
0.945312   5468750384476454912   5468749834720641024  -5.497558e+11
0.957031   4296875223552098304   4296874948674191360  -2.748779e+11
0.972656   2734375192238227456   2734374917360320512  -2.748779e+11
0.978516   2148437611776049152   2148437474337095680  -1.374390e+11
0.986328   1367187596119113728   1367187458680160256  -1.374390e+11
0.989258   1074218805888024576   1074218737168547840  -6.871948e+10
0.993164    683593798059556864    683593729340080128  -6.871948e+10
1.000000                     1                     0  -1.000000e+00

Answer 3

如果您使用的是没有 FPU 的微控制器，那么浮点运算将会非常昂贵。对于浮点运算来说很容易慢二十倍。最快的解决方案是使用整数进行所有数学运算。

固定二进制小数点后的位数 (http://blog.credland.net/2013/09/binary-fixed-point-explanation.html?q=fixed+binary+point）是：XY_TABLE_FRAC_BITS。

这是我使用的一个函数：

inline uint16_t unsignedInterpolate(uint16_t a, uint16_t b, uint16_t position) {
    uint32_t r1;
    uint16_t r2;

    /* 
     * Only one multiply, and one divide/shift right.  Shame about having to
     * cast to long int and back again.
     */

    r1 = (uint32_t) position * (b-a);
    r2 = (r1 >> XY_TABLE_FRAC_BITS) + a;
    return r2;    
}

通过内联函数，它应该大约是。 10-20 个周期。

如果您有 32 位微控制器，您将能够使用更大的整数并获得更大的数字或更高的精度，而不会影响性能。该函数在16位系统上使用。

Answer 4

值得注意的是，标准线性插值公式 f1(t)=a+t(ba)、f2(t)=b-(ba)(1-t) 和 f3(t)=a(1- t)+bt 不保证在使用浮点运算时表现良好。
也就是说，如果 a != b，则不保证 f1(1.0) == b 或 f2(0.0) == a，而对于 a == b，则不保证 f3(t) 等于 a ，当 0 < t < 1.

当我需要结果表现良好并准确命中端点时，此函数在支持 IEEE754 浮点的处理器上对我有用（我以双精度使用它，但浮点也应该工作）：

double lerp(double a, double b, double t) 
{
    if (t <= 0.5)
        return a+(b-a)*t;
    else
        return b-(b-a)*(1.0-t);
}

Answer 5

如果您正在为没有浮点运算的微控制器进行编码，那么最好根本不使用浮点数，而使用 定点算术 代替。

Answer 6

从 C++20 开始，您可以使用 std::lerp()，这可能是实现您的目标的最佳实现。

Answer 7

如果您希望最终结果是整数，那么使用整数作为输入可能会更快。

int lerp_int(int a, int b, float f)
{
    //float diff = (float)(b-a);
    //float frac = f*diff;
    //return a + (int)frac;
    return a + (int)(f * (float)(b-a));
}

这会执行两次强制转换和一次浮点乘法。如果在您的平台上强制转换比浮点数加/减更快，并且整数答案对您有用，那么这可能是一个合理的替代方案。