Линейная интерполяция с плавающей запятой

Ответ 1

Несмотря на различия в точности, это выражение эквивалентно

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

Это 2 сложения/вычитания и 1 умножение вместо 2 сложения/вычитания и 2 умножения.

Ответ 2

Если вы используете микроконтроллер без 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-битной системе.

Ответ 3

Предполагая, что математика с плавающей точкой доступна, алгоритм OP является хорошим и всегда превосходит альтернативу a + f * (b - a) из-за потери точности, когда a и b значительно различаются по величине.

Например:

// OP 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

Ответ 4

Если вы кодируете микроконтроллер без операций с плавающей запятой, то лучше вообще не использовать числа с плавающей запятой и использовать fixed- точной арифметики.

Ответ 5

Если вы хотите, чтобы конечный результат был целым числом, возможно, будет быстрее использовать целые числа для ввода.

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));
}

Это делает два броска и одно умножение с плавающей точкой. Если приведение происходит быстрее, чем сложение/вычитание с плавающей запятой на вашей платформе, и если целочисленный ответ полезен для вас, это может быть разумной альтернативой.

Ответ 6

Он был написан Google раньше, однако это просто, и вы можете написать свой собственный, но почему? Когда это для вас.

new FloatEvaluator().evaluate(fraction, startValue, endValue)

Эта функция возвращает результат линейной интерполяции начальных и конечных значений, причем дробная часть представляет пропорцию между начальными и конечными значениями.