Was ist Fixpointlogik und wie implementiert man sie?

http://www.mikrocontroller.net/articles/Festkommaarithmetik

Fixer schrieb:

> Nur wie implementiert man diese?

Weißt du doch schon längst.

Du willst Geldbeträge verrechnen. Du willst zb rechnen 2 Euro fufzich 
PLUS 3 Euro achtzig

    2.50
    3.80
  -------
    6.30

6 euro dreissig.

Und jetzt das ganze ohne Kommazahlen!
Was machst du?
Anstelle von 'in Euro' rechnest du 'in Cent'

2 euro fufzich sind 250 Cent
3 euro achtzig sind 380 Cent


    250
    380
   -----
    630

das Ergebnis sind also 630 Cent. Und das alles ohne Kommazahlen.

Was hast du gemacht?
Du hast deine Eurobeträge einfach mal 100 genommen um auf ganze Cent zu 
kommen. Du hättest auch mal 1000 nehmen können und hättest dann zb auf 
Zehntel-Cent gerechnet (was bei Prozentrechnung in Banken nicht ganz 
uninteressant ist). Und weil du weißt, dass du deine Ausgangsbeträge mal 
100 genommen hast, weißt du auch, dass du dir gedanklich immer zwischen 
der  Hunderterstelle und der Zehnerstelle das Komma vorstellen musst. 
Eben eine fixe (aber ansonsten nicht weiter wichtige) Position eines 
gedachten Kommas in den Zahlen. Um von den Cent wieder auf Euros zu 
kommen, wendest du die andere Richtung an: DIvision durch 100. 630 Cent 
sind 630/10 6 ganze Euros und 630%100 = 30 Cent, also 6.30 Euro

Niemand schreibt dir allerdings vor, dass dein Faktor 100 sein muss. Der 
kann genausogut 2 oder 4 oder 64 oder 128 oder etwas ganz anderes sein. 
Wie es dir gefällt.

PS: Aufpassen bei Multiplikationen und Divisionen! Aber das findest du 
auch alleine raus, was da abgeht.

Fixer schrieb:
> Soweit mein Vertändnis reicht, können damit z.B. Multiplikationen durch
> Shift-Operationen ersetzt werden, sofern man eine Fixpoint-Logik zur
> Basis 2 einsetzt. Nur wie implementiert man diese?

Das "Problem" dabei wäre, dass du dann keine fixe Anzahl an Kommastellen 
im Dezimalsystem hast und genau dies ist meist erwünscht (z.B. um einem 
Wert qauf einem Display anzuzeigen). Du hast dann eine fixe Anzahl an 
Kommastellen im Binärsystem. Multiplikationen könntest du natürlich 
nicht nur durch Schieben realisieren, welche Schiebeoperation ist 
äquivalent zu einer Multiplikation mit drei?

"Normale" Interpretation eines Bytes:
b7*2^7 + ... + b0*2^0

Deine Interpretation (Bsp.):
b7*2^5 + ... + b0*2^-2


Einen Vorteil sehe ich da jetzt nicht (heisst aber nicht, dass keiner da 
ist).


Nachtrag:
Natürlich wären die Anzahl Kommastellen dann auch im Dezimalsystem 
konstant. Man hat dann einfach nicht eine Auflösung von z.B. 0.01, 
sondern von z.B. 0.125, daher: "krumme" Werte.

Fixer schrieb:
> Also alles mal an einem Beispiel
> Wie würde denn mein Controller die folgende Rechnung ausführen, wenn ich
> z.B. folgendes möchte:

Die ganze Fragestellung ist verkorkst.

> double Zahl_1 = 0,924;
>
> uint16_t Zahl 2 = 5;
>
> double Ergebnis = Zahl_1 * Zahl_2; //richtige Lösung: 4,62


Befrag deinen Compiler, wie er das macht. Wenn der OPtimizer was drauf 
hat, dann rechnet der Compiler schon den Wert aus.

> Ich habe an dieser stelle keine Ahnung, wieviel Rechenkapazität für die
> Double-Werte drauf gehen. Es ist aber wohl in jedem Fall mehr als es
> sein müsste.

Das ist der falsche Ansatz.
Wenn du etwas rechnen musst, dann musst du es rechnen. Die Frage ist 
nicht, wie lange dauert es, sondern die Frage lautet: Habe ich die Zeit 
dafür?

> Nun würde ich die Rechnung durch Fixpointarithmetik beschleunigen
> versuchen
>
> Vorgehen also:
>
> Zahl_1 *=1000;
>
> ...
> Ergebnis = 924*5; // = 4620

Fixpoint bringt dir nur dann wirklich was, wenn das komplette Programm 
auf Fixpoint umgearbeitet wird, wie zb ein PID Regler. Wegen einer 
einzelnen Rechnung macht man kein Fixpoint. Denn da braucht die 
Multiplikation mit 1000 und das anschliessende Umarbeiten auf Integer 
schon mehr Zeit, als dir die ursprüngliche Rechnung gekostet hätte.

> Helfen könnte ich mir nur durch einen Shift

Vergiss bitte dieses Shiften.
Dein Compiler weiß schon wann er welche Multiplikationen oder DIvisionen 
durch Shifts ersetzen kann. Das ist nichts was dich groß kümmern müsste. 
Compiler machen das seit 50 Jahren routinemässig.

Karl Heinz Buchegger schrieb:

> Fixpoint bringt dir nur dann wirklich was, wenn das komplette Programm
> auf Fixpoint umgearbeitet wird, wie zb ein PID Regler. Wegen einer
> einzelnen Rechnung macht man kein Fixpoint. Denn da braucht die
> Multiplikation mit 1000 und das anschliessende Umarbeiten auf Integer
> schon mehr Zeit, als dir die ursprüngliche Rechnung gekostet hätte.


In deinem Fall müsste man also erst mal der Frage nachgehen, wo 
eigentlich die 0,924 herkommen und warum die nicht von Haus aus schon 
entsprechend auf Fixpoint gepimpt wurden.
Die 0.924 stammen vielleicht aus einer anderen Rechnung, die dann 
ebenfalls schon Fixpoint gemacht werden muss. Und deren Argumente kommen 
auch irgendwo her und müssen ebenfalls ins Fixpoint Schema gebracht 
werden. Und so zieht sich die Fixpoint Arithmetik durchs komplette 
Programm. Lediglich dort wo Ein/Ausgaben gemacht werden erfolgt die 
Konvertierung auf benutzerlesbare Form (wenn überhaupt)

Fixer schrieb:

> Ergebnis = 946*5 = 4730;

wieso *5
Auch 5 muss ins Fixpoint Format geholt werden!

   946 * 5000 = 4730000

das durch 1024 (wegen der Multiplikation) -> 4619

4619 ist also dein Fixpoint Ergebnis

Das entspricht

  4619 / 1024   = 4
  4619 % 1024   = 523

also 4 Ganze PLUS 523/1024-tel
also 4.51074...

So gewaltig unterschiedlich ist das nicht zu 4.620

Fixer schrieb:
> Der Compiler weiß wohlmöglich wann eine Division und wann eine
> Shift-Operation sinnvoler ist...aber der Prozessor weiß dies zur
> Laufzeit ganz gewiss nicht.

Der Prozessor arbeitet das ab, was ihm der Compiler generiert.

 Schreibst du

    uint16_t  a, b;

    a = b / 1024;

dann kannst du deinen A. darauf verwetten, dass der Compiler die 
Division durch entsprechende Shifts ersetzt, WENN das auf der 
Zielhardware schneller ist.

> Ich schreibe doch eine Funktion, die zur Laufzeit Werte erhält. Der
> Compiler kann wohl nicht abschätzen, wann diese Werte ein Shiften
> erlauben und wann nicht.

Dasselbe gilt aber auch für dich.
Entweder du kennst den Wert durch den du dividierst schon während das 
Programm geschrieben wird, dann kannst DU als Programmierer entsprechend 
austauschen. Wenn DU aber den Wert kennst, dann kennt ihn auch der 
Compiler. Und dessen Optimizer hat noch ein paar Tricks mehr drauf, als 
du dir vorstellen kannst und er kennt auch alle Nebenbedingungen und 
auch, ob auf der Hardware vielleicht eine Divisionshardware vorhanden 
ist aber kein Barrelshifter und daher Dividieren tatsächlich schneller 
ist als Schieben.

> Ist es nicht so, dass eine Funktion, die nur eine einzige nicht aus der
> Zweierpotenz stammende Division durchführen könnte, den Compiler bereits
> dazu zwingt, im Controller stets einen "normalen" Divisionsalgorithmus
> zu durchlaufen und damit eben ein Shiften unmöglich macht?

Natürlich (unter anderem).
Aber genau das gleiche glit ja auch für dich. Wie willst du denn eine 
allgemeine Division

    a = b / c;

durch Shift ersetzen, wenn du nichts über c weißt? Dein Ersatz beruht 
darauf, dass du weißt, dass du schreiben wirst

    a = b / 1024;

nur dann kannst du (wenn noch ein paar Nebenbedingungen stimmen, wie zb. 
dass das keine Float Division sein darf), diese Division durch eien 
Shift ersetzen. Aber: Das weiß doch auch der Compiler! Steht doch im 
Programmtext, dass du durch 1024 dividieren willst!

Karl Heinz Buchegger schrieb:
> Auch 5 muss ins Fixpoint Format geholt werden!
>
>    946 * 5000 = 4730000
>
> das durch 1024 (wegen der Multiplikation) -> 4619
>
> 4619 ist also dein Fixpoint Ergebnis
>
> Das entspricht
>
>   4619 / 1024   = 4
>   4619 % 1024   = 523
>
> also 4 Ganze PLUS 523/1024-tel
> also 4.51074...


Hallo Karl Heinz,
wenn Du jetzt die urprüngliche 5 auch mit 1024 multiplizierst kommst Du 
auf

   946 * 5120 = 4843520

Nach deinen restlichen richtigen Umrechnungsschritten kommt an Ende

   4,619140625

raus.

> So gewaltig unterschiedlich ist das nicht zu 4.620

Stimmt :-)

Karl Heinz Buchegger schrieb:
> wieso *5
>
> Auch 5 muss ins Fixpoint Format geholt werden!
>
>    946 * 5000 = 4730000
>
> das durch 1024 (wegen der Multiplikation) -> 4619
>
> 4619 ist also dein Fixpoint Ergebnis

Nein! Eine Multiplikation mit einer ganzen Zahl kann ganz normal 
ausgeführt werden:

0.946 * 5 = 4.73
946 * 5 = 4730

Nur wenn jetzt z.B. mit 5.5 Multipliziert werden soll, muss man den 
Umweg machen. Und dann nicht durch 1024, sondern duch 1000 teilen 
(ausser man nimmt den dadurch entstehenden Fehler zu Gunsten der 
Geschwindigkeit in Kauf).

Steffen N. schrieb:

> wenn Du jetzt die urprüngliche 5 auch mit 1024 multiplizierst kommst Du
> auf

Autsch.
Ja, da hast du recht. Da hab ich nicht aufgepasst.
Drum ist es besser, wenn der Rechner sich um das Kleinvieh kümmert :-)

be stucki schrieb:
> Karl Heinz Buchegger schrieb:
>> wieso *5
>>
>> Auch 5 muss ins Fixpoint Format geholt werden!
>>
>>    946 * 5000 = 4730000
>>
>> das durch 1024 (wegen der Multiplikation) -> 4619
>>
>> 4619 ist also dein Fixpoint Ergebnis
>
> Nein! Eine Multiplikation mit einer ganzen Zahl kann ganz normal
> ausgeführt werden:

Ja, wenn man im Vorfeld weiß, dass man eine ganze Zahl hat. Weil sich 
die Umwandlung nach Fixpoint und die nachfolgende Korrektur des 
Ergebnisses herauskürzt.

> Umweg machen. Und dann nicht durch 1024, sondern duch 1000 teilen

kommt drauf an, mit welchem Faktor man Fixpoint rechnet.
Bei 10-er Potenzen ergeben sich für uns Menschen schöne Abkürzungen die 
sich durch Verschieben des Kommas auf dem Papier leicht rechnen lassen. 
Für den Rechner sieht die Sache aber anders aus.
VOn daher ist ein Fixpoint-Faktor der eine 2-er Potenz ist, schon 
sinnvoll. Und natürlich muss man dann auch wieder durch diesen 
dividieren.

Karl Heinz Buchegger schrieb:
> VOn daher ist ein Fixpoint-Faktor der eine 2-er Potenz ist, schon
> sinnvoll. Und natürlich muss man dann auch wieder durch diesen
> dividieren.

Natürlich, du hast reucht. Ich hab nicht das geschrieben, was ich 
gedacht hatte...


Aus eingenem Interesse:
Es kann ja vorkommen, dass das als Zwischenschritte sehr grosse Zahlen 
entstehen, die nicht mehr im grössten Datentyp gehalten werden können. 
Gibt es da eine Möglichkeit, dies zu umgehen?

Haeufig ueberschaetzt man die Anforderungen. wenn ich zB einen 
Kalibrationsfaktor fuer eine Thermoelemente Temperatur brauche, und der 
soll 0.1% Schritte ermoeglichen. Dann lass ich fuer einen Wert um Eins, 
die Benutzer einen Wert von zB 700.. 1400 eingeben, mit dem wird 
multipliziert, und nachher implizit durch 1024 geteilt, sprich 10bit 
nach rechts. Sowas reicht auch umd einen Stromsensor, Shunt oder so an 
einen Display anzupassen.

be stucki schrieb:

> Aus eingenem Interesse:
> Es kann ja vorkommen, dass das als Zwischenschritte sehr grosse Zahlen
> entstehen, die nicht mehr im grössten Datentyp gehalten werden können.
> Gibt es da eine Möglichkeit, dies zu umgehen?

Da gibts nur eines:
Vorher abschätzen bzw. festlegen, in welchem Zahlenbereich operiert 
wird. Gerade im Embedded Bereich gelingt das ja relativ gut. Ein AVR-ADC 
liefert nun mal nichts größeres als 1023, bzw. haben Sensoren limitierte 
Wertebereiche.


Was auch des öfteren hilft:
Gleichungen nicht naiv implementieren sondern erst mal auf dem Papier 
komplett anschreiben und dann rigoros umformen bzw. Kürzen und erst mal 
auf dem Papier vereinfachen.


Oder:
Die Dinge umdrehen. Sich überlegen, ob man etwas wirklich ausrechnen 
muss. Zb Spannungen. Anstatt den Wert vom ADC in eine Spannung 
umzurechnen und die dann mit Grenzwerten zu vergleichen, kann man auch 
die Grenzwerte im Vorfeld in ADC Einheiten umrechnen. Dann wird eben der 
ADC Wert überhaupt nicht mehr umgerechnet sondern nur noch verglichen. 
Das Ergebnis ist dasselbe ... nur für den µC einfacher zu erreichen.

M. N. schrieb:
> Nimm mal 'richtige' Zahlen für Dein Beispiel:
>
> double Zahl_1 = 0,924846283874872;
Und was soll diese "richtige Zahl" dann Physikalisch darstellen? Nur 
weil man Speicher verbraten will, muss man kein float oder double 
nehmen.
Wenn Zahl_1 eine Spannung darstellt, dann hat die letzte Stelle 
Femto-Volt. Da rauscht ein 1-Ohm Widerstand mehr.
Sehr beliebt ist auch z.B. einen Radumfang beim Roboter auf 8 Stellen 
nach dem Komma anzugeben - dass dann die letzte Stelle im 
Angström-Bereich liegt ist natürlich wichtig. So kann man auch 
Fettfinger auf dem Rad in die Wegberechnung einfließen lassen. 
Dummerweise wird sich selbst ein Stahlrad bei einer Belastung mit 100g 
soweit "abplatten", dass die letzten 3 Stellen nicht mehr stimmen.

Wer genau mit Festkomma rechnen will (muss) nimmt signed long mit 
1µV/Bit oder 1nA/Bit. Damit ist mit einer Long-Variablen eine Spannung 
von -/+2100V und ein Strom von -/+2.1A darstellbar. Kraftwerker oder 
Elektronenphysiker dürfen andere Skalierungen verwenden.