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

Question

Чтобы выполнить линейную интерполяцию между двумя переменными a и b с учетом доли f, я сейчас использую этот код:

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

Я думаю, что, возможно, есть более эффективный способ сделать это. Я использую микроконтроллер без FPU, поэтому операции с плавающей запятой выполняются программно. Они достаточно быстрые, но это все равно что 100 циклов, чтобы добавить или умножить.

Есть предложения?

n.b. для ясности в уравнении в приведенном выше коде мы можем не указывать 1.0 в качестве явного литерала с плавающей точкой.

Answer 1

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

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

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

Answer 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-битной системе.

Answer 3

Предполагая, что математика с плавающей точкой доступна, алгоритм 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 4

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

Answer 5

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

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

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

Answer 6

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