algorithm - que - Interpolación lineal de punto flotante.

que es coma flotante en informatica

Question

Para hacer una interpolación lineal entre dos variables b dada 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 probablemente hay una forma 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 aún así es como 100 ciclos para sumar o multiplicar.

¿Alguna sugerencia?

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

Answer 1

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

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 lanzamientos y un flotador se multiplica. Si una conversión es más rápida que una suma / resta flotante en su plataforma, y ​​si una respuesta de entero es útil para usted, esta podría ser una alternativa razonable.

Answer 2

Si está codificando un microcontrolador sin operaciones de punto flotante, entonces es mejor no usar números de punto flotante y, en su lugar, usar aritmética de punto fijo .

Answer 3

Si está en un microcontrolador sin una FPU, el punto flotante será muy costoso. Fácilmente podría ser veinte veces más lento para una operación de punto flotante. La solución más rápida es simplemente hacer todas las matemáticas usando números 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í hay una función que uso:

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 en línea debe ser aprox. 10-20 ciclos.

Si tiene un microcontrolador de 32 bits, podrá usar enteros más grandes y obtener números más grandes o más precisos sin comprometer el rendimiento. Esta función fue utilizada en un sistema de 16 bits.

Answer 4

Sin tener en cuenta las diferencias de precisión, esa expresión es equivalente a

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

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

Answer 5

Suponiendo que la matemática de punto 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 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 que los flotadores de 32 bits lint1(1.0e20, 1.0, 1.0) devolverán correctamente 1.0, mientras que lint2 devolverá incorrectamente 0.0.

La mayoría de las pérdidas de precisión se encuentran 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 suma en a + f * (b - a) . El algoritmo de OP no sufre de esto debido a que los componentes se multiplican completamente antes de la adición.

Para el caso a = 1e20, b = 1 , aquí hay 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;
}

Salida, ligeramente ajustada para el formateo:

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