punto de interpolación lineal

Question

flotante para hacer una interpolación lineal entre dos variables a y b dado una fracción f, actualmente estoy usando este código:

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

Creo que hay probablemente una manera más eficiente de hacerlo. Estoy usando un microcontrolador sin una FPU, por lo que las operaciones de punto flotante se realizan en el software. Son razonablemente rápidos, pero todavía es algo así como 100 ciclos para agregar o multiplicar.

¿Alguna sugerencia?

n.b. para mayor claridad en la ecuación del código anterior, podemos omitir la especificación de 1.0 como un literal explícito de coma flotante.

Answer 1

Haciendo caso omiso de las diferencias en la precisión, que la expresión es equivalente a

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

Eso es 2 adiciones/restas y 1 de multiplicación en lugar de 2 Adición/restas y 2 multiplicaciones.

Answer 2

Si está codificando para un microcontrolador sin operaciones de punto flotante, entonces es mejor no usar números de coma flotante, y usar fixed-point arithmetic en su lugar.

Answer 3

Si desea que el resultado final sea un número entero, podría ser más rápido usar enteros para la entrada también.

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

Esto hace dos moldes y un flotador se multiplican. Si un elenco es más rápido que un flotante, sumar/restar en su plataforma, y ​​si una respuesta entera le resulta útil, esta podría ser una alternativa razonable.

Answer 4

Si se encuentra en un microcontrolador sin una FPU, el punto flotante va a ser muy caro. Podría ser fácilmente veinte veces más lento para una operación de coma flotante. La solución más rápida es hacer todas las matemáticas usando enteros.

El número de lugares después del punto binario fijo (http://blog.credland.net/2013/09/binary-fixed-point-explanation.html?q=fixed+binary+point) es: XY_TABLE_FRAC_BITS.

Aquí es una función que utilizo:

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

Con la función inline que debería ser aprox. 10-20 ciclos.

Si tienes un microcontrolador de 32 bits, podrás usar enteros más grandes y obtener números más grandes o más precisión sin comprometer el rendimiento. Esta función se usó en un sistema de 16 bits.

Answer 5

Suponiendo que la matemática de coma flotante está disponible, el algoritmo de OP es bueno y siempre es superior a la alternativa a + f * (b - a) debido a la pérdida de precisión cuando a y b difieren significativamente en magnitud.

Por ejemplo:

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

En ese ejemplo, suponiendo 32 bits flota lint1(1.0e20, 1.0, 1.0) devolverá correctamente 1,0, mientras que lint2 se incorrectamente volver 0.0.

La mayoría de la pérdida de precisión se produce en los operadores de suma y resta cuando los operandos difieren significativamente en magnitud. En el caso anterior, los culpables son la resta en b - a, y la adición en a + f * (b - a). El algoritmo de OP no sufre de esto debido a que los componentes se multiplican por completo antes de la suma.

---

Para el a = 1e20, b = 1 caso, aquí es un ejemplo de resultados diferentes. Programa de prueba:

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

de salida, ligeramente ajustado para el formato:

 
    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