fixed-point-Arithmetik und Vergleich
Curtis Newton
ich portiere gerade mal testweise einigen Code von floating-point zu
fixed-point-Arithmetik (der entsprechende Typ hei�t bei mir _iq) und
habe irgendwie einen Knoten im Hirn, wenn es um Vergleiche geht. Die
fixed-point-Variable wird dabei intern durch einen int32 repr�sentiert.
Die entsprechenden Funktionen zum multiplizieren, dividieren usw. habe
ich.
Ein Vergleich von _iq gr��er oder kleiner 0 ist ja klein Problem, da das
Vorzeichenbit bei int32 und _iq an der gleichen Stelle steht :-)
Wie bekomme ich aber schnell den Vergleich mit anderen Zahlen ungleich 0
hin? Beispiel:
_iq fpz=3.1234 (also wenn man _iq nach float umrechnen w�rde...)
int vz =3
Will ich jetzt _iq und vz vergleichen, m�sste ich ja _iq nach float
umrechnen und dann den Vergleich machen. Unsch�n, oder? Geht das besser?
Genauso beim Vergleich zwischen zwei _iq-Zahlen.
C.
Thomas Richter
Fixpoint ist ja nur eine Skalierung von Ganzzahlen. Beim Vergleich
zwischen fixpoint und float musst Du also entweder die Fixkommazahl in
eine Flie�kommazahl umwandeln (durch Division durch die Skalierung) oder
die Flie�kommazahl mit der Skalierung multiplizieren und dann vergleichen.
> Genauso beim Vergleich zwischen zwei _iq-Zahlen.
Dazu kannst Du die Integer-Repr�sentation direkt vergleichen, denn beide
Zahlen sind ja auf die gleiche Weise skaliert.
Gr��e,
Thomas
Curtis Newton
> Fixpoint ist ja nur eine Skalierung von Ganzzahlen. Beim Vergleich
> zwischen fixpoint und float musst Du also entweder die Fixkommazahl in
> eine Flie�kommazahl umwandeln (durch Division durch die Skalierung) oder
> die Flie�kommazahl mit der Skalierung multiplizieren und dann vergleichen.
>
>> Genauso beim Vergleich zwischen zwei _iq-Zahlen.
>
> Dazu kannst Du die Integer-Repr�sentation direkt vergleichen, denn beide
> Zahlen sind ja auf die gleiche Weise skaliert.
Ja, danke, logisch!
Man bekommt ja Probleme, wenn man eine klitzekleine FP-Zahl und eine
gro�e multiplizieren will. Die Rundungsfehler (hei�en die hier noch so?)
werden ja recht gro�. Gibt es einen Trick, wie man das trotzdem in der
gew�nschten Genauigkeit hinbekommt? Irgendwie sich mit mehreren
Multiplikationen zu der gro�en Zahl "hochhangeln"?
--
Bye
Thomas Richter
> Man bekommt ja Probleme, wenn man eine klitzekleine FP-Zahl und eine
> gro�e multiplizieren will. Die Rundungsfehler (hei�en die hier noch so?)
> werden ja recht gro�.
Nein, �berhaupt nicht. Die Multiplikation ist eher unkritisch.
�blicherweise wirst Du zur Skalierung der Fixkomma-Zahlen eine
Zweierpotenz verwenden, d.h. es muss lediglich die Mantisse der
Flie�kommazahl an die richtige Stelle geschoben werden. Nat�rlich fallen
dabei Bits irgendwo herunter, bzw. die Rechnung wird ungenau, aber nicht
ungenauer als beim Vergleich zweier Flie�kommazahlen, denn dabei
passiert nat�rlich genau dasselbe.
Kritisch bei Flie�kommazahlen sind eher Addition und Subtraktion durch
die Ausl�schung f�hrender Stellen, wodurch der "Schein" gr��erer
Genauigkeit als vorhanden entsteht.
> Gibt es einen Trick, wie man das trotzdem in der
> gew�nschten Genauigkeit hinbekommt? Irgendwie sich mit mehreren
> Multiplikationen zu der gro�en Zahl "hochhangeln"?
Nein, dadurch akkumulierst Du nur weitere Fehler.
Gute Einf�hrung zu dem ganzen w�re f�r mich Knuth, Band II:
Donald Knuth: The Art of Programming,
Vol II: Numerical and Seminumerical Algorithms.
Gr��e,
Thomas
Curtis Newton
> Curtis Newton schrieb:
>
>> Man bekommt ja Probleme, wenn man eine klitzekleine FP-Zahl und eine
>> gro�e multiplizieren will. Die Rundungsfehler (hei�en die hier noch so?)
>> werden ja recht gro�.
>
> Nein, �berhaupt nicht. Die Multiplikation ist eher unkritisch.
...Ich meinte auch Division (Gro�e FP/Kleine FP). Und das habe ich so
gel�st, indem ich nicht die gro�e mit der kleinen Zahl dividiere,
sondern erst ganz normal mit floats die (das?) Reziproke von der kleinen
Zahl ausrechne und dann mit der Reziproken multipliziere. Geht besser...
> Gute Einf�hrung zu dem ganzen w�re f�r mich Knuth, Band II:
>
> Donald Knuth: The Art of Programming,
> Vol II: Numerical and Seminumerical Algorithms.
Danke!
--
Bye
Thomas Richter
> Am Fri, 11 Dec 2009 13:58:36 +0100 schrieb Thomas Richter:
>
>> Curtis Newton schrieb:
>>
>>> Man bekommt ja Probleme, wenn man eine klitzekleine FP-Zahl und eine
>>> gro�e multiplizieren will. Die Rundungsfehler (hei�en die hier noch so?)
>>> werden ja recht gro�.
>> Nein, �berhaupt nicht. Die Multiplikation ist eher unkritisch.
>
> ...Ich meinte auch Division (Gro�e FP/Kleine FP).
Auch hier, eher unkritisch, nur langsam. Ausl�schung und
Genauigkeitsverlust ist eher ein Problem von Addition und Subtraktion.
In diesem besonderen Fall ist es noch weniger kritisch, denn Dein
Divisionsfaktor sollte eine Zweierpotenz sein.
> Und das habe ich so
> gel�st, indem ich nicht die gro�e mit der kleinen Zahl dividiere,
> sondern erst ganz normal mit floats die (das?) Reziproke von der kleinen
> Zahl ausrechne und dann mit der Reziproken multipliziere. Geht besser...
Wieso? Solange beides Flie�kommazahlen sind, ist der Algorithmus, der
*weniger* Operationen enth�lt, eindeutig im Vorteil. D.h. willst Du
*eine* Flie�kommazahl durch eine *andere* Flie�kommazahl dividieren, so
mache genau das und nichts anderes. Eine Operation weniger, die Fehler
erzeugt.
Willst Du ein riesiges Array von Flie�kommazahlen durch eine gemeinsame
Konstante dividieren, ist es in der Tat besser, mit dem inversen zu
multiplizieren. Allerdings weniger wegen der Genauigkeit, sondern wegen
der Geschwindigkeit.
Gr��e,
Thomas
Markus Schaub
> Willst Du ein riesiges Array von Flieï¿œkommazahlen durch eine gemeinsame
> multiplizieren. Allerdings weniger wegen der Genauigkeit, sondern wegen
> der Geschwindigkeit.
Das sollte doch wohl eher der Compiler entscheiden.
Markus
Thomas Richter
Vermutlich nicht. Natï¿œrlich darf der Compiler Code auf Basis der "as-if"
Regel ï¿œndern, dazu mï¿œsste er aber nachweisen, dass fï¿œr alle Elemente des
Arrays die Division exakt das gleiche Resultat ergibt wie die
Multiplikation mit dem (numerisch nicht exakten) Inversen. Bei
begrenzter Genauigkeit wird dies eher nicht der Fall sein.
Grￜￜe,
Thomas
Erich Fruehstueck
> Thomas Richter schrieb:
>> Willst Du ein riesiges Array von Fließkommazahlen durch eine gemeinsame
>> Konstante dividieren, ist es in der Tat besser, mit dem inversen zu
>> multiplizieren. Allerdings weniger wegen der Genauigkeit, sondern wegen
>> der Geschwindigkeit.
>
> Das sollte doch wohl eher der Compiler entscheiden.
Wie kann der das, wenn z.B. die Größe des Arrays erst zur Laufzeit
bekannt ist? Abgesehen davon, halte ich es nicht für gut, dass
zu viele Dinge vom Compiler entschieden werden. Das gibt nur zusätzliche
Fehlerquellen. Es ist unschön, wenn Rechenergebnisse, auch wenn sie im
Toleranzbereich der Fließkommagenauigkeit bleiben, vom Grad der
Optimierung abhängen.
Erich
--
EFEU 3.2 is released!
Get the open source from http://efeu.cybertec.at.
Stefan Reuther
Gerade bei IEEE-Floating-Point hat der Compiler da sich an gewisse
Regeln zu halten. Wï¿œhrend er "x/2.0" wahrscheinlich durchaus in "x*0.5"
umformen darf, darf er das bei "x/3.0" und "x*(1.0/3.0)" eher nicht.
Das hier:
#include <stdio.h>
int main() {
double a = 1.0 / 3.0;
double b = 77;
double c = b / 3.0;
double d = b * a;
printf("%llx %llx\n", *(long long*) &c, *(long long*) &d);
}
ergibt jedenfalls zwei Werte, die sich im LSB unterscheiden (gcc-3.4.4,
x86).
Stefan
Curtis Newton
>>>> Man bekommt ja Probleme, wenn man eine klitzekleine FP-Zahl und eine
>>>> gro�e multiplizieren will. Die Rundungsfehler (hei�en die hier noch so?)
>>>> werden ja recht gro�.
>>> Nein, �berhaupt nicht. Die Multiplikation ist eher unkritisch.
>>
>> ...Ich meinte auch Division (Gro�e FP/Kleine FP).
>
> Auch hier, eher unkritisch, nur langsam.
�h�, hmm, sorry, ich hab was vergessen zu erw�hnen. Mit klitzekleine und
gro�e meine ich was anderes bzw. hab was vergessen zu erw�hnen.
Die FP-Bibliothek, die ich benutze, erm�glicht die Wahl des "Kommas"
(logisch). Damit kann man sich zwischen h�herer Genauigkeit (und kleinen
Wertebereich) oder geringerer Genauigkeit (und gr��eren Wertebereich)
entscheiden. Und hier lag mein Problem:
zahl1 = ungenaue_zahl/genaue_zahl
Und wenn ich nicht dividiere sondern multipliziere
zahl2 = ungenaue_zahl*ungenaue_zahl
bin ich mit zahl2 n�her am Ergebnis der �quivalenten float-operation als
mit zahl1.
--
Bye
Thomas Richter
Tut mir leid, so ganz folgen kann ich Dir leider nicht. Du kannst bei
Fixkomma immer das "Komma" so verschieben, wie Du magst. Es betrifft
sowieso nur die Multiplikation oder Division, bzw. die korrekte
Skalierung des Resultates. Mir ist nicht klar, warum Du dazu eine
Bibliothek brauchst, Fixkommazahlen sind nur vorskalierte Integer-Zahlen.
Was die Division angeht, so verstehe ich nicht, weswegen diese trotz
genauerer Eingaben ein ungenaueres Resultat liefern sollte.
Gr��e,
Thomas
Markus Schaub
> Markus Schaub wrote:
>> Thomas Richter schrieb:
>>>Willst Du ein riesiges Array von Flieï¿œkommazahlen durch eine gemeinsame
>>>Konstante dividieren, ist es in der Tat besser, mit dem inversen zu
>>>multiplizieren. Allerdings weniger wegen der Genauigkeit, sondern wegen
>>>der Geschwindigkeit.
>>
>> Das sollte doch wohl eher der Compiler entscheiden.
>
> Gerade bei IEEE-Floating-Point hat der Compiler da sich an gewisse
> Regeln zu halten. Wï¿œhrend er "x/2.0" wahrscheinlich durchaus in "x*0.5"
> umformen darf, darf er das bei "x/3.0" und "x*(1.0/3.0)" eher nicht.
Ok, hab ich ï¿œbersehen. Ich nehme alles zurï¿œck und behaupte das Gegenteil :-).
Markus