Festkomma-Arithmetik mal erklärt

Fixed point arithmetic explained

(Yet to be translated from German, sorry)

Hier einige Erläuterungen, wie man beim Implementieren von Programmen für Mikrocontroller mit den Zahlen umgeht um performanten Code zu erzeugen. Dazu gehört die auch der Umgang mit Festkomma-Arithmetik.

Wir Programmierer arbeiten ständig mit Zahlen und Datentypen - und sind uns dessen bewusst, dass Zahlen, die wir im Computer darstellen, begrenzt im Speicher und damit auch im Wertebereich sind.

Wenn wir nicht gerade eine Schleife durchiterieren oder eine Textlänge bestimmen wollen bleiben wir bei Programmen für einen handelsüblichen Computer meist bei double (64 bit) oder auch manchmal long double (128 bit, "Quadrupel") wenn's denn wirklich wichtig ist. Die Rechner sind schnell genug und haben auch einen (heute integrierten) mathematischen Co-Prozessor.

Bei Controllern liegt der Fall oft anders: Wir haben keinen schnellen Prozessor, (oftmals) keinen mathematischen Co-Prozessor für Fließkommazahlen, wenig Platz, und wahrscheinlich auch wenig Zeit bis das Ergebnis unserer Berechnungen fertig sein muss. Da versucht man Leistung abzuzwacken wo es nur geht. Man spart Platz indem keine unnötig großen Variablen verwendet werden, man versucht möglichst viel vorzuberechnen, man erstellt sich Lookup-Tabellen um prozessorintensive Rechnungen einzusparen, usw. Die Typen double und float werden dann unattraktiv und müssen short, int oder long weichen.

Aber was machen wir bei diesen Typen mit dem Komma? Wir denken uns das Komma an eine bestimmte Position. Anders gesagt: Wir skalieren eine Zahl hoch und ändern damit gewissermaßen die Einheit. Als würden wir von kg nach g skalieren (also drei Stellen im Zehnersystem). Allerdings machen wir dies im Binärsystem.

Festkommazahlen sind also nichts weiter als Ganzzahlen und haben die Datentypen char, short, int, long oder long long, und sie können mit oder ohne Vorzeichen sein, also signed oder unsigned (signed wird normalerweise weggelassen - int ist identisch mit signed int). Weil beim Rechnen mit Zahlen auch die Größe wichtig ist und die genannten Typen auf unterschiedlichen Architekturen unterschiedlich groß sein können möchte ich im Folgenden die Darstellungen int8_t/uint8_t, int16_t/uint16_t, usw. verwenden. Diese Typen sind normalerweise für die jeweilige Platform bereits definiert, z.B. in <stdint.h>, und sie werden vom Compiler richtig eingesetzt. Ich empfehle dringend solche Typen zu verwenden und gegebenenfalls selbst zu definieren wenn es keine Includedatei für die verwendete Architektur gibt.

Festkommazahlen - Das Taschenrechnerbeispiel im Zehnersystem

Ok, nun zum Komma. Wir halten uns erst mal ein paar Vergleiche aus unserem Zehnersystem, und übertragen diese dann in das Dualsystem - um dann festzustellen, dass einiges im Dualsystem sogar noch einfacher ist: Nehmen wir mal an wir haben einen Taschenrechner bei dem die Kommataste bzw. Punkttaste kaputt ist, und wollen dennoch damit rechnen. Dann stellen wir schon einige Sachen fest, die wir ins Dualsystem übernehmen können. Wir dabei noch an, dass der Rechner ein Display mit 10 Stellen hat.

Nehmen wir an wir wollen 0.815 + 7.04 rechnen (aber natürlich nicht im Kopf). Für uns kein Problem - wir verschieben das Komma um drei Stellen nach unten und denken es uns bei den dadurch entstehenden Ganzahlen bei der dritten Stelle. Das können wir dann eintippen: 815 + 7040 = 7855. Klar, wir sehen die Zahl 7855, aber wir wissen, dass es eigentlich 7.855 ist. Bei 0.815 - 0.007 gehen wir genau so vor. Wir erkennen hierdurch aber auch, dass das Ganze ein Problem aufwirft wenn wir wissen wo das Komma ist - z.B. dann, wenn wir jemand anders fragen sich eine Festkommazahl auszudenken und wir unsere erdachte hinzuaddieren wollen. Tippt er (wie im Beispiel) 815 ein und meint aber 81.5, dann müssten wir nur zwei Stellen hochschieben und die Zahl anders interpretieren (ich verwende für Stellen schieben mal das Symbol <<).

  Wirkliche       Fest-      Alle Stellen auf
   Zahlen         komma      dem Taschenrechner

   7.04 << 2    =  704          0000000704
  81.50 << 2    = 8150          0000008150
                + ----
                = 8854          0000008854
                    |                   |
                    -------------------------- Gedachtes Komma hier davor.

Namenskonventionen

Wir müssen dem Kind also einen Namen geben - im Kommentar des Quelltextes. Es gibt zwei dominante Notationen dafür:

Wir können "eine 8.2 - Zahl" sagen, denn wir haben 8 Vorkommastellen und 2 Nachkommastellen.
Wir können "eine 10-Stellen-Zahl Q2" sagen, denn unsere Zahl hat 10 Stellen und das Komma sitzt bei (d.h. vor) der zweiten Stelle.

Addieren / Subtrahieren

Und mit diesem Beispiel haben wir schon die erste Regel für's Rechnen mit Festkommazahlen:

Wir müssen zum Addieren/Subtrahieren die Zahlen so verschieben, dass das Komma an der selben Stelle sitzt. Sonst verrechnen wir Kraut mit Rüben und erhalten das entsprechende Ergebnis. Ein wenig theoretischer betrachtet müssen wir auch zwei Brüche auf den selben Nenner bringen bevor wir sie addieren können.

Die zweite Sache ist auch schnell erdacht: Wenn ich 5000000000 und du 5000000000 eintippen, egal wo das Komma sitzt, dann fehlt uns eine Stelle auf dem Display. Unsere 10 Stellen reichen nur dann aus, wenn wir vereinbaren entweder generell Zahlen kleiner als 5000000000 einzugeben oder wir einigen uns z.B. auf "kleiner 4000000000" und "kleiner 6000000000":

Beim Addieren/Subtrahieren kann sich die benötigte Anzahl an Gesamtstellen um eins erhöhen. Wir müssen den Wertebereich der Eingabezahlen im Auge behalten. Bei der Art, wie der Taschenrechner negative Zahlen berechnet gilt das auch fürs Subtrahieren, auch wenn es auf den ersten Blick nicht ersichtlich ist. Das "Overflow-Problem" ist sehr wahrscheinlich vom Programmieren mit Ganzzahlen schon bekannt. Wir haben hier für den "Notfall" allerdings noch ein Trumpf im Ärmel: Wenn beide Eingabezahlen 10 Stellen haben, dann können wir sie beide eins nach unten schieben bevor wir addieren. Dann fällt uns allerdings eine Nachkommastelle weg, d.h. wir verlieren an Auflösung. Auch müssen wir uns merken, dass sich das Komma verschoben hat. Es gibt Situationen, in denen diese Methode Anwendung findet. Wenn's geht nimmt man sich aber lieber ein Display mit mehr Stellen.

Multiplizieren

Nun zum Multiplizieren: Wir wollen 1.5 * 5.5 rechnen. Wieder kein Problem, wir schieben eins hoch und erhalten 15 * 55 (also Q1 * Q1) - Ergebnis ist 825. Unser Komma ist ja an der ersten Stelle, also 82.5 ... Mist, das stimmt nicht. Das Komma hat sich selbst eine Stelle hochgeschoben. Wir können das mit verschiedenen Kommapositionen durchgehen und werden immer feststellen, dass sich beim Multiplizieren die Kommastellen addieren. D.h. für Q4 * Q2 erhalten wir eine Q6-Zahl.

Beim Multiplizieren zweier Festkommazahlen addieren sich die Kommapositionen.

Und auch hier schauen wir auf den Wertebereich - was vom Programmieren wohl schon bekannt ist. Holen wir den Extremfall und rechnen 9999999999 * 9999999999. Das sind fast 10000000000 * 10000000000, also fast 100000000000000000000. Das bedeutet wir brauchen fast 21 Stellen - also 20 Stellen - um das Ergebnis zu fassen. Deshalb verwenden wir bei den Datentypen im Controller auch zum Zwischenspeichern des Ergebnisses den nächstgrößeren Datentyp. Oder anders gesagt herum können wir nur Zahlen multiplizieren, die zusammen 10 Stellen haben.

Beim Multiplizieren verdoppeln sich die Gesamtstellen der Zahl.

Weil auch die Nachkommastellen entsprechend wachsen (weil sich das Komma ja verschiebt) wird hier öfter mal zurückgeschoben bis die gewünschte Nachkommagenauigkeit erreicht ist. Dazu später mehr wenn wir im Dualsystem sind.

Dividieren

Dividieren ist eigentlich nichts anderes als Multiplizieren mit einem Kehrwert, d.h. a / b == a * (1/b). Damit können wir uns herleiten was mit der Kommastelle passiert: (a=1000.055) / (b=100.1). Das echte Ergebnis ist 9.99056. Wir stellen das jetzt mal als unterschiedlichen Q-Zahlen dar, nämlich a=1000055 Q3, b=1001 Q1. Dann teilen wir: 1000055/1001 = 999. Das muss Q2 sein. Eigentlich is es auch klar - wir rechnen 1/b, also 1/Q1, also eins durch eine Zahl, die wir zuvor mal 10 genommen haben. Das ergibt eine Zahl, die um den Faktor 10 kleiner ist, also Q-1. Dann multiplizieren wir a*b und die Stellen addieren sich wie üblich beim Multiplizieren: (Q3) * (Q-1), uns das ist Q2, was wir in unserem Ergebnis sehen.

Beim Dividieren werden die Kommapositionen voneinander subtrahiert: Zähler minus Nenner.

Jetzt kommt noch eine kleine Trickserei in Spiel, denn wir können hier mehr Genauigkeit herausholen. Keiner verbietet uns die Stellen des Displays "bis zum Anschlag" zu nutzen. D.h. Wir können auch a = 1000.055 = 1000055000 Q6 sagen und bei b = 100.1 = 1001 Q1 belassen. Dann erhalten wir beim Dividieren 999055, und das Komma sitzt bei Q(6-1), also an der fünften Stelle. Das entspricht 9.99055 - und es ist drei Stellen genauer als unser Ergebnis davor.

Keiner verbietet uns die Genauigkeit zu erhöhen, indem wir den Zähler höher schieben als in den Ganzzahlbereich. Der Wertebereich, also die Anzahl der Stellen des Displays, muss das allerdings zulassen.

Exponential

Wir können uns schon denken wo das endet. Um pow(a,b) zu rechnen müssen wir b mal a mit sich selbst multiplizieren. D.h. theoretisch benötigten wir b Anzeigen nebeneinander um das Ergebnis darstellen zu können. Die Kommastelle von a verschiebt sich b mal nach oben. Warum also dieser Abschnitt?: Wegen dem nächsten Abschnitt ...

Multiplikation von Zahlen zwischen -1 und 1

Es gibt einige Situationen, bei denen man zwei Zahlen zwischen 0 und 1 hat. Die können wir multiplizieren und bleiben (real) im Bereich von 0 und 1. Die Zahl wird lediglich kleiner. Wenn wir sie auf unserem Display als Q10-Zahlen darstellen erhalten wir als Ergebnis eine Q20-Zahl. Und wenn wir jetzt damit zufrieden sind, dass wir nur die ersten 10 Nachkommastellen nehmen und den Rest z.b. runden, dann können wir so oft multiplizieren wie wir wollen. Nach jeder Multiplikation schieben wir einfach die Zahl um 10 Stellen zurück, so dass das Komma wieder an der 10ten Stelle sitzt. Bei negativen Zahlen ist das logischerweise genau so (auch wenn wir diese bei unserem Display mal ausgeblendet haben).

Wir können Zahlen zwischen -1 und 1 beliebig oft multiplizieren, indem wir die Kommastelle wieder zurück schieben. Wir verlieren dadurch aber an Genauigkeit - damit müssen wir dann leben.

Festkommazahlen - jetzt im Dualsystem und in C

Die oben genannten Beispiele aus dem Dezimalsystemsystem lassen sich eins zu eins bzw. "zehn zu zwei" übertragen. Die Stellen des Taschenrechners sind die Bits, und eine Kommataste haben wir bei den Integer-Datentypen auch nicht. Statt einer Zehnerstelle schieben wir eine Zweierstelle. Wiederholen wir die Kernpunkte und ergänzen sie mit ein paar "Tricks" (Die Beispiele kommen darunter):

Verschieben des Kommas wird realisiert durch Bitschiebeoperation, wobei jedes nach links geschobene Bit die Zahl um den Faktor 2 skaliert. Jedes rechtsgeschobene Bit impliziert eine Skalierung um den Faktor 0.5.
Beim Addieren und Subtrahieren zweier Festkommazahlen muss die Position des Kommas durch Schieben in Deckung gebracht werden.
Zum sicheren Addieren/Subtrahieren darf die Summe der Bitlänge beider Eingabewerte die Bitlänge der Ergebnisvariablen minus eins nicht überschreiten.
Beim Multiplizieren addieren sich die Kommapositionen beider Zahlen.
Beim Multiplizieren ergibt sich die Anzahl benötigter Bits, um das Ergebnis zu speichern, aus der Summe der Bitlängen beider Eingabezahlen.
Beim Dividieren wird die Kommaposition des Divisors von der Kommaposition des Dividenden subtrahiert.
Die Genauigkeit der Division kann auf einfache Weise erhöht werden, in dem der Dividend so weit wie möglich hochgeschoben wird. Dabei verschiebt sich auch die Kommaposition mit. Komplexere Algorithmen (z.B. SRT) erlauben eine automatische Festkommadivision mit möglichst hoher Auflösung.
Zahlen können durch Rechtsschieben um N schnell dividiert werden, wenn der Divisor der Zahl 2^N entspricht.

Nun zu den Beispielen. Wir bedienen uns dreier Hilfsfunktionen fp(), print_fp() und print_header, sowie einem Makro DUMP. Die Rechnungen sind in main().

fp() übergeben wir eine Fließkommazahl value und die Kommastelle Q. Alles was die Funktion tut ist die Fließkommazahl mal 2^Q zu nehmen und in eine Ganzzahl umzuformen. Die geben wir als int32_t, auch wenn wir in main kleinere Zahlen verwenden.
print_fp() schreibt uns einfach eine schöne Zeile mit den Infos: Variablenname, Kommastelle, Größe des Datentyps, Zahlenwert als Dezimalzahl, als Hexzahl, als Dualzahl, und als Fließkommazahl wenn man die Kommastelle berücksichtigt. Aufgrund von reiner Faulheit schlagen wir darum noch das Makro DUMP, welches den Funktionsaufruf nochmals verkürzt.
print_header() schreibt uns nur eine Trennzeile bzw. Kopfzeile fürs aktuelle Thema. "No magic here".

#include <stdio.h>
#include <stdint.h>
 
/**
 * Generate a fixed point value for this example
 */
int32_t fp(double value, int8_t Q)
{ return (int32_t) (value * (1 << Q)); }
 
/**
 * Dump a fixed point number
 */
#define DUMP(VAR, Q) print_fp(#VAR, VAR, Q, (8*sizeof(VAR)))
void print_fp(const char* name, int32_t value, int8_t Q, uint8_t sz)
{
  int8_t i;
  printf("%5s (Q%2d, %2d bit) = %5d |  %04Xh  |  ", name, Q, sz, value, value);
  for(i=16-sz; i>=0; i--) printf(" ");
  for(i=sz-1; i>=0; i--) printf("%1d%s", (value>>i)&1, (i%4 || !i) ? "" : "");
  printf("b  |  %10.05f\n", (double) value / (double)(Q>0?(1<<Q):(1>>(-Q))));
}
 
/**
 * Print a head line
 */
void print_header(const char * s)
{
  printf("\n----------------------------------------------------------\n");
  printf("%s\n", s);
  printf("----------------------------------------------------------\n");
}
 
 
/**
 * And here we go.
 */
int main(int argc, char** argv)
{
  // ADD //////////////////////////////////////////////////////////////////////
  //
  //  a (Q 2,  8 bit) =    10 |  000Ah  |           00001010b  |     2.50000
  // aa (Q 4,  8 bit) =    40 |  0028h  |           00101000b  |     2.50000
  //  b (Q 4,  8 bit) =    52 |  0034h  |           00110100b  |     3.25000
  //  c (Q 4,  8 bit) =    92 |  005Ch  |           01011100b  |     5.75000
  print_header(" c = (a + b)");
  int8_t  a = fp( 2.5 , 2);  // a (Q2) = 10
  int8_t  b = fp( 3.25, 4);  // b (Q4) = 52
  int8_t aa = a << 2;        // a shifted up to get Q4 as well
  int8_t  c = (a << 2) + b;  // c (Q4) = a (Q4) + b (Q4)
  DUMP(a, 2);
  DUMP(aa, 4);
  DUMP(b, 4);
  DUMP(c, 4);
 
 
  // SUBSTRACT ////////////////////////////////////////////////////////////////
  //
  //  d (Q 1,  8 bit) =   123 |  007Bh  |           01111011b  |    61.50000
  //  e (Q 4,  8 bit) =    40 |  0028h  |           00101000b  |     2.50000
  //  f (Q 1,  8 bit) =   118 |  0076h  |           01110110b  |    59.00000
 
  print_header(" f = (d - e)");
  int8_t  d = fp( 61.5, 1);  // d (Q1) = 123
  int8_t  e = fp(  2.5, 4);   // e (Q4) = 40
  int8_t  ee = e >> 3;        // e to Q1 because we cannot shift d up without overflow
  int8_t  f  = d - (e >> 3);  // f (Q1) = d (Q1) - e (Q1)
  DUMP(d, 1);
  DUMP(e, 4);
  DUMP(f, 1);
 
 
  // MULTIPLY ////////////////////////////////////////////////////////////////
  //
  //  g (Q 6,  8 bit) =    70 |  0046h  |           01000110b  |     1.09375
  //  h (Q 4,  8 bit) =    40 |  0028h  |           00101000b  |     2.50000
  //  i (Q10, 16 bit) =  2800 |  0AF0h  |   0000101011110000b  |     2.73438
 
  print_header(" i = (g * h)");
  int8_t  g = fp(1.094, 6);  // g (Q6) = 70
  int8_t  h = fp(  2.5, 4);  // h (Q4) = 40
  int16_t i = g * h;         // i (Q10) = g (Q6) * h (Q4)
  DUMP(g, 6);
  DUMP(h, 4);
  DUMP(i, 10);
 
 
  // DIVIDE //////////////////////////////////////////////////////////////////
  //
  //  j (Q 4, 16 bit) =   468 |  01D4h  |   0000000111010100b  |    29.25000
  //  k (Q 5, 16 bit) =    80 |  0050h  |   0000000001010000b  |     2.50000
  //  l (Q 0, 16 bit) =    11 |  000Bh  |   0000000000001011b  |    11.00000
  // jj (Q10, 16 bit) = 29952 |  7500h  |   0111010100000000b  |    29.25000
  //  m (Q 5, 16 bit) =   374 |  0176h  |   0000000101110110b  |    11.68750
  //
  //  --> Real result 29.25000/2.50000 = 11.70000
 
  print_header(" m = l = (j / k)");
  int16_t  j = fp(29.3, 4);  // j (Q4) = 468
  int16_t  k = fp( 2.5, 5);  // k (Q5) = 80
  int16_t  l = (j << 1) / k; // j (Q4->Q5) / k (Q5) --> 5 (Q0), quite inaccurate
  int16_t jj = (j << 6);     // jj (Q4->Q10)
  int16_t  m = (j << 6) / k; // j (Q4->Q10) / k (Q5)
  DUMP(j, 4);
  DUMP(k, 5);
  DUMP(l, 0);
  DUMP(jj, 10);
  DUMP(m, 5);
  printf("\n     --> Real result %5.5f/%5.5f = %5.5f", ((double)(j)/(1<<4)),
       ((double)(k)/(1<<5)), (((double)(j)/(1<<4)))/(((double)(k)/(1<<5))));
 
 
  // RECIPROCAL: 1 / n //////////////////////////////////////////////////////
  //
  //    n (Q 3, 16 bit) =   426 |  01AAh  |   0000000110101010b  |    53.25000
  //  one (Q15, 16 bit) = 32767 |  7FFFh  |   0111111111111111b  |     0.99997
  //    o (Q12, 16 bit) =    76 |  004Ch  |   0000000001001100b  |     0.01855
  //    p (Q28, 32 bit) =5041041| 4CEB91h |10011001110101110010001b    0.01878
 
  print_header(" p = o = 1 / n");
  int16_t  n = fp(53.32, 3);
  int16_t one= (1<<((8*sizeof(int16_t)-1)))-1;  // This is 0.99997 = 32767 Q15
  int16_t  o = one / n;                         // Q(15-3)
  int32_t  p = 0x7fffffff / n;                  // 1 Q31 / n (Q3) = p (Q28)
  DUMP(n, 3);
  DUMP(one, 15);
  DUMP(o, 15-3);
  DUMP(p, 31-3);
 
  ///////////////////////////////////////////////////////////////////////////
 
  return 0;
}

GIT repositories

Services

GNU octave web interface