Approximation durch Fixpunktrechnung

Walter T. #5802039
Lesenswert?
• ▲
▼ 
Hallo zusammen,

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

Direkt würde er so ausgewertet:
1
int32_t term(int32_t x, int32_t a, int32_t b)

2
{

3
    assert( b > a );

4
    assert( a > 0 );

5
    return (int64_t) x*a/b;

6
}


Das Ganze will ich beschleunigen durch eine Approximation durch eine 
Qn-Fixpunkt-Zahl. Der Fehler scheint minimal bei
mit
und wenn ich das richtig gerechnet habe, ist die Fehlerschranke

Habe ich das richtig gerechnet, oder ist irgendwo ein Denkfehler?
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
Johann L. Persönliche Seite #5802160
Lesenswert?
• ▲
▼ 
Wenn a und b konstant sind, genügt es doch, den Quotienten 1× zu 
berechnen, etwa so:

1
#include <stdint.h>

2
#include <stdbool.h>

3
#include <assert.h>

4


5
int32_t term (int32_t x, int32_t a, int32_t b)

6
{

7
    static bool have_val = false;

8
    static uint32_t val;

9
    if (!have_val)

10
    {

11
        assert (b > a);

12
        assert (a > 0);

13
        have_val = true;

14
        val = (((uint64_t) a << 32) / (uint32_t) b);

15
    }

16
        

17
    return ((int64_t) x * val) >> 32;

18
}


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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Walter T. #5802257
Lesenswert?
• ▲
▼ 
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.)
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren