Approximation durch Fixpunktrechnung

[Walter T. (nicolas)]

Hallo zusammen,

ich habe einen (häufig genutzte) Term x*a/b mit konstanten Parametern a 
und b .

Direkt würde er so ausgewertet:

int32_t term(int32_t x, int32_t a, int32_t b)
{
    assert( b > a );
    assert( a > 0 );
    return (int64_t) x*a/b;
}

Das Ganze will ich beschleunigen durch eine Approximation durch eine 
Qn-Fixpunkt-Zahl. Der Fehler scheint minimal bei

$$\frac{x\cdot a}{b} \approx \left\lfloor{}\frac{a \cdot q_n}{2^n}\right\rfloor{}$$

mit

$$q_n = \left\lfloor{} \frac{2^n \cdot a}{b}\right\rfloor{}$$

und wenn ich das richtig gerechnet habe, ist die Fehlerschranke

$$e = \left\lfloor{} \frac{x\cdot a}{b}\right\rfloor{} - \left\lfloor{}\frac{a \cdot q_n}{2^n}\right\rfloor{} \\ \max\left|e\right| \leq{} 1 \text{ wenn } x, a, b < 2^n$$

Habe ich das richtig gerechnet, oder ist irgendwo ein Denkfehler?

[Pandur S. (jetztnicht)]

Ja. Festkommastellen anhaengen.

return (int64_t) 256*x*a/b;

resp

return (int64_t) 65536*x*a/b;

[Johann L. (gjlayde)]

Wenn a und b konstant sind, genügt es doch, den Quotienten 1× zu 
berechnen, etwa so:

#include <stdint.h>
#include <stdbool.h>
#include <assert.h>

int32_t term (int32_t x, int32_t a, int32_t b)
{
    static bool have_val = false;
    static uint32_t val;
    if (!have_val)
    {
        assert (b > a);
        assert (a > 0);
        have_val = true;
        val = (((uint64_t) a << 32) / (uint32_t) b);
    }
        
    return ((int64_t) x * val) >> 32;
}

Allerdings ist nicht klar, welche Probleme du zu umschiffen versuchst 
und auf welcher Plattform das laufen soll. Je nach Verwendung kann es 
daher besser sein, die Berechnung von val in eine eigene no-inline 
Funktion auszulagern (z.B. avr-gcc). Oder auf das static zu verzichten 
und den Compiler Constatnt Propagation von a und b durchführen zu 
lassen, falls die beiden Konstanten zur Compilezeit bekannt sind.

[Walter T. (nicolas)]

Johann L. schrieb:
> Wenn a und b konstant sind, genügt es doch, den Quotienten 1× zu
> berechnen,

Genau das ist mein Ziel.

Die Konstanten sind erst zur Laufzeit bekannt (Einstellparameter), aber 
nach der Initialisierung dauerhaft konstant.

Meine Frage bezog sich darauf, ob die Fehlerabschätzung stimmt, oder ob 
mir da ein Fehler unterlaufen ist. Und ob das eine günstige Näherung 
ost, oder ob man z.B. durch kaufmännisches Runden à la
qn = (2^n*a + b/2)/b den Fehler auf durchschnittlist 1/2 anstelle -0+1 
bringen kann.

(Letztere Idee kommt mir erst jetzt gerade - das probiere ich direkt mal 
aus.)