Gleitkomma-lineare Interpolation

Question

eine lineare Interpolation zwischen zwei Variablen zu tun a und b gegeben ein Bruch f, ich bin derzeit mit diesem Code:

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

Ich denke, es ist wahrscheinlich eine effizientere Art und Weise tun. Ich benutze einen Mikrocontroller ohne FPU, so dass Fließkommaoperationen in Software ausgeführt werden. Sie sind ziemlich schnell, aber es ist immer noch so etwas wie 100 Zyklen hinzuzufügen oder zu multiplizieren.

Irgendwelche Vorschläge?

n.b. Aus Gründen der Übersichtlichkeit in der Gleichung im obigen Code können wir die Angabe 1.0 als explizites Fließkomma-Literal weglassen.

Answer 1

aus Unterschieden in der Präzision Ohne Berücksichtigung, ist, dass die Expression entspricht

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

Das sind 2 Additionen/Subtraktionen und 1 Multiplikation anstelle von 2-Addition/Subtraktionen und Multiplikationen 2.

Answer 2

Wenn Sie einen Mikrocontroller ohne Gleitkommaoperationen codieren, sollten Sie keine Gleitkommazahlen verwenden und stattdessen fixed-point arithmetic verwenden.

Answer 3

Wenn das Endergebnis eine Ganzzahl sein soll, kann es auch schneller sein, Ganzzahlen für die Eingabe zu verwenden.

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

Dies macht zwei Güsse und einen Schwimmer multiplizieren. Wenn eine Umwandlung schneller als ein Float ist, addieren/subtrahieren Sie sie auf Ihrer Plattform, und wenn eine ganzzahlige Antwort für Sie nützlich ist, könnte dies eine sinnvolle Alternative sein.

Answer 4

Wenn Sie auf einem Mikrocontroller ohne FPU sind, dann wird Floating Point sehr teuer sein. Könnte für eine Fließkommaoperation leicht zwanzigmal langsamer sein. Die schnellste Lösung besteht darin, die ganze Mathematik mit Ganzzahlen zu berechnen.

Die Anzahl der Stellen nach dem festen Binärpunkt (http://blog.credland.net/2013/09/binary-fixed-point-explanation.html?q=fixed+binary+point) ist: XY_TABLE_FRAC_BITS.

Hier ist eine Funktion, die ich verwende:

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

Mit der Funktion inlined es ca. sein sollte. 10-20 Zyklen.

Wenn Sie einen 32-Bit-Mikrocontroller haben, können Sie größere Ganzzahlen verwenden und größere Zahlen oder mehr Genauigkeit erhalten, ohne die Leistung zu beeinträchtigen. Diese Funktion wurde für ein 16-Bit-System verwendet.

Answer 5

Vorausgesetzt, Fließkomma-Mathematik ist verfügbar, der OP-Algorithmus ist ein guter und ist immer besser als die Alternative a + f * (b - a) aufgrund Präzisionsverlust, wenn und b deutlich in der Größenordnung unterscheiden.

Zum Beispiel:

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

In diesem Beispiel 32-Bit vorausgesetzt schwimmt lint1(1.0e20, 1.0, 1.0) korrekt 1,0 zurück, während lint2 falsch 0,0 zurück.

Die Mehrheit der Genauigkeitsverlust ist in den Additions- und Subtraktionsoperatoren, wenn die Operanden signifikant in der Größenordnung unterscheiden. Im obigen Fall sind die Täter die Subtraktion in b - a und die Addition in a + f * (b - a). Der Algorithmus des OP leidet darunter nicht, da die Komponenten vor der Addition vollständig multipliziert werden.

---

Für die a = 1E20, b = 1 Fall, hier ist ein Beispiel für unterschiedliche Ergebnisse. Prüfprogramm:

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

Ausgang, leicht für die Formatierung eingestellt:

 
    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