Festkomma-Algorithmus

Tag zusammen,

ich versuche gerade ein Problem in C zu realisieren, bei dem es auf eine sehr sehr hohe Genauigkeit ankommt. Ich verwende bereits den Datentyp "long double". Das Ergebnis ist zwar etwas besser als bei "double", aber die Genauigkeit reicht immer noch nicht aus. Nun habe ich in einer Referenz gelesen dass sogenannte Festkomma-Algorithmen verwendet werden können, wenn die Genauigkeit von "long double" immer noch nicht ausreichen sollte.

Was sind Festkomma-Algorithmen? Ich habe bis jetzt noch kein Beispiel für einen gefunden. Ich hoffe ihr könnt mir helfen. Ein Beispiel wäre auch nciht schlecht.

Danke im voraus.

Das ist quasi ein neuer Datentyp, der das , an einer festen Stelle hat. Double hat in der Regel 80 Bit, in der Mantisse, Exponent und Vorzeichen untergebracht werden müssen. Fließkommaarithmetik war früher sehr langsam und man ist deshalb auf Festkomma umgestiegen, weil man (mit ein wenig umrechnen) mit normalen 16-Bit-Werten/Registern arbeiten konnte. Allerdings hat ein 16-Bit-Speicher natürlich nicht den Wertebereich einer Fließkommazahl. Es steht Dir aber natürlich frei, statt 16 Bit auch 256 Bit oder mehr zu verwenden. Dann mußt Du allerdings Operationen wie + - * / selbst programmieren.

Bsp.: 16 Bit => 0 - 65535.
Ich möchte 2 Nachkommastellen haben. => 1 = 100 => Du hast einen Wertebereich von nur noch 0 - 655,35, dafür aber 2 Nachkommastellen.

Alternativ könntest Du auch mit BCD-Ziffern rechnen. Dabei passen 2 Ziffern in ein Byte. Angenommen, Du brauchst 10 Vorkomma- und 10 Nachkommastellen, dann bräuchte die Zahl 10 Byte. Kannst DU natrülich beliebig ausbauen. Operationen wie + - * und / müssen auch hier programmiert werden.

Aber such mal im Web. Da sollte sich bestimmt eine Bibliothek finden, die genau das schon macht.

Hm...vielen Dank für die Erklärung. Nachdem ich das hier gelesen habe glaube ich garnicht mehr dass mir damit geholfen wäre.
Erstens: Ich muss trigonometrische Funktionen anwenden...und wenn ich schon die Grundrechenarten selbst implementieren muss, dann auch Sinus/Cosins etc. Das ist eindeutig zuviel des Guten.

Zweitens: ich müsste mir dann wohl auch eine Zahl Pi berechnen, die genauso exakt ist wie mein "neuer Datentyp". Puh!!!

Vielleicht kennt jemand einen Workaround. Das eigentliche Problem ist, aufs wesentliche reduziert, recht einfach. Also...ohne zu weit auszuholen:

Ich berechne einen diskreten Sinus ( sin(2*pi*f*t) ) zu Zeitpunkten t=k*Ts (Ts = 1/(2*f) ).
So...theoretischer Wert wäre Null. Aber die Werte die rauskommen sind definitiv ungleich Null, wenn auch in der Größenordnung 10^-15

Diese kleine Ungenauigkeit schaukelt sich im weiteren Verlauf meines Programmes dermaßen auf, dass sie nicht mehr vernachlässigbar ist. Hinzu kommt noch eine Ungenauigkeit von Ts, so dass insgesamt eine Drift der Sinus-Werte zustande kommt. Diese Differenz wird dann nochmal verstärkt wenn sie mein Programm durchlaufen. Kurz und knapp: Ich sollte Null bekommen, bekomme aber einen Wert > Null, und das ist extrem doof.
Und ich denke mal bei der Masse an Berechnungen wird auch ein 256Bit Register nicht ausreichen um den Fehler auf ein akzeptables Niveau zu drücken.

Hat jemand irgendwelche anderen Ideen um das in den Griff zu bekommen?

Vielleicht helfen Dir die Grundlagen über den Aufbau und der "Funktionsweise" von Fließkommaarithmetik weiter: http://de.wikipedia.org/wiki/Gleitkommazahl

Entweder Du kannst den Fehler durch mathematische Umformungen oder andere Berechnungsverfahren minimieren oder Du brauchst eine Library, die das Rechnen mit höherer Genauigkeit erlaubt. BigDecimal in Java stellt z.B. einen beliebig genauen Typ zur Verfügung. Allerdings stehen da auch nur die Grundrechenarten zur Verfügung. Alles andere müßte selbst implementiert werden.

Unter Linux kannst Du mit Perl das BigInt-Modul meines Freundes benutzen:

http://search.cpan.org/~tels/Math-BigInt-1.77/lib/Math/BigInt.pm

wenn du rechnungen mit hoher genauigkeit durchführen willst, nimm besser FORTRAN oder MATHLAB . beide sprachen können variablen beliebiger länge definieren.

MATHLAB? Noch nie gehört.
Oder meinst du MATLAB?
MATLAB benutze ich seit geraumer Zeit, aber dass man dort die Rechengenauigkeit beliebig hoch schrauben kann ist mit neu.

Für mein Problem stehen C/C++ und MATLAB zur Verfügung. kein Perl, kein FORTRAN, und schon garkein Linux an sich...leider.

Hallo,

angelslayer schrieb:

Hat jemand irgendwelche anderen Ideen um das in den Griff zu bekommen?

Zum Vergrößern anklicken....

Ja

Verwende die GNU Bignum Bibliothek: http://www.swox.com/gmp/

Die Library verarbeitet nicht nur Integers sondern auch Floating-Point Zahlen.

Nic

Du könntest den Sinus sehr einfach mittels komplexer Multiplikationen erzeugen. Allerdings musst du dabei sicherstellen, dass der komplexe Zeiger durch die Rechenungenauigkeiten sich nie zu weit von seiner Soll-Länge (1) entfernt.
Du könntest auch eine genaue Lookup-Tabelle verwenden.
Kommt aber in erster Linie darauf an, was du danach mit dem Sinus vorhast

nic_power schrieb:

Verwende die GNU Bignum Bibliothek: http://www.swox.com/gmp/
Die Library verarbeitet nicht nur Integers sondern auch Floating-Point Zahlen.

Zum Vergrößern anklicken....

Werd ich morgen mal compilen und einbauen. Klingt ja nicht schlecht. Danke für den Tip. Arbitrary Precision heisst also das Schlagwort. Da muss man erstmal drauf kommen...*google anwerf*

cmddegi schrieb:

Du könntest auch eine genaue Lookup-Tabelle verwenden.

Zum Vergrößern anklicken....

Öhm...Aber die Lookup Table kann ich nur innerhalb der Genauigkeit meines Datentypes verwenden. Es bringt mir ja nix wenn mein Datentyp zB 16 Nachkommastellen verkraftet, die Lookup-Table aber 20 hat, oder die Werte die ich will erst ab der 17ten Stelle anfangen...
Verstehst du mein Problem? Vielleicht habe ich einfach nur nen Knoten im Kopf...ich hab auf jeden Fall erstmal zu wenig Nachkommastellen.

Was willst du denn nachher mit deinem Sinus machen? Möglicherweise kann man an der nachfolgenden Berechnung etwas verändern, damit die Genauigkeit nicht so hoch sein muss.

Nach der Sinus-Berechnung kommt noch eine Multiplikation, der Rest richtet sich dann lediglich nach dem Vorzeichen des Ergebnisses. Viel vereinfachen lässt sich da nicht. Es muss so implementiert werden, ansonsten geht der Bezug zum realen System verloren das simuliert werden soll.
Ausserdem: mir fiel gerade ein dass ein Lookup Table ohnehin ausscheidet. Später (wenn alles mal so läuft wie es soll) kommt nämlich noch eine Störungsgröße als Phase ins Argument des Sinus-Signals...das ganze muss dann nachgeregelt werden, etc etc...

Wie kommt denn das Aufschaukeln zustande?
Ansonsten mach dich mal hier schlau über die Vorteile der Festkomma-Arithmetik:
http://www.dspguide.com/ch4.htm
Hängt hauptsächlich vom erforderlichen Dynamikbereich ab, ob Festkomma für dein Problem geeignet ist.

cmddegi schrieb:

Wie kommt denn das Aufschaukeln zustande?

Zum Vergrößern anklicken....

Durch die Multiplikation und durch die Tatsache dass die gesamte Loop insgesamt 400 Millionen mal durchlaufen wird...vorerst. In jedem Durchgang wird dann ein Zwischenergebnis über 600mal aufsummiert, und dann ne Rückkopplung berechnet. Die Ungenauigkeit beruht zum einen auf dem Fehler den C macht wenn man ne Weile 2.5e-9 aufsummiert. Auf einmal ist das Ergebnis nämlich kein ganzzahliges Vielfaches mehr von 2.5e-9. Das fand ich recht beeindruckend, da es ja nur ne einfache Summe ist.
Aufgrund der Ungenauigkeit der Zeit kommt dann eine Drift des Abtastzeitpunktes des Sinus-Signals zustande, dementsprechend der Falsche Wert, der wieder mit einer Ungenauigkeit versehen wird, weil man ihn ja multipliziert, aufsummiert, und zurückkoppelt...
So...und ich bin ja nicht doof...hab mir heute für die Zeit eine genaue lookup-table gebastelt...in ner Datei...die Datei war über 6GB gross...der Rechenaufwand enorm...das Ergebnis nun ohne Drift, aber immer noch zu ungenau.

// der Fehler den ich im Moment mache (wird von mir momentan noch seperat von Hand durch eine andere Formel berechnet) ist in der Größenordnung 10^-13 ... 3-4 Zehnerpotenzen zu hoch! Ihr seht also dass das alles recht knifflig ist...kleiner Fehler, kleine Werte, und ein Soll-Fehler der noch viel viel kleiner ist...

Hmm..., Festkommazahlen haben dieses Problem bei der Aufsummierung nicht; durchaus möglich, dass das der richtige Weg für dich ist.
Hängt aber eben maßgeblich davon ab, ob die Zahlen sich in einem "relativ kleinen" Bereich bewegen. Wo der Bereich bezogen auf 0 liegt, ist dabei egal.

So...Fazit: es hat geklappt.
Ich habe nun ein brauchbares Ergebnis innerhalb des erlaubten Toleranzbereiches. Die verwendete Bibliothek habe ich im Internet gefunden. Für alle Interessierten, hier der Link zu einer Sammlung von High Precision Bibliotheken für unterschiedliche Programmiersprachen:
http://crd.lbl.gov/~dhbailey/mpdist/
Ich verwendet die Bibliothek "QD". Dabei hat es bereits ausgereicht die Rechengenauigkeit auf "dd_real" (double-double, 106 significand Bit)einzustellen. Als Alternative gäbe es noch "qd_real" (quad-double, 212 sigifificand Bit), die Rechenzeit geht dann aber extrem nach oben.