Hilfe bei Vorüberlegungen für eine LUT

[sergej (Gast)]

Hallo,
ich habe folgendes problem:
Ich möchte ich LUT machen und die soll möglichst klein sein.
Mein Inhalt sind Festkommazahlen von 0-90. ich möchte eine Genauigkeit 
von 0,1 erreichen.

jetzt weiss ich, dass ich für die mantisse 7 bit brauche. Aber wie lege 
ich jetzt die bit für die nachkommastellen fest?

ich könnte jetzt sagen mit 0.000111 bekomme ich 0,109375 hin, mit 6 bit 
sieht das schon ok aus. Aber ist das auch die beste Lösung? das muss ja 
irgendwie mathematisch zu errechnen sein

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

sergej schrieb:
> Aber wie lege ich jetzt die bit für die nachkommastellen fest?
Naja ganz einfach:
Mit 1 Bit kannst du 1/2 (=0,5) darstellen. Mit 2 Bit kannst du 1/4 
darstellen, also 0,25. Mit 3 Bit kannst du 1/8 darstellen. Du willst 
aber mindestens 1/10. Also brauchst du 4 Bit. Damit kannst du bis auf 
1/16, also 0,0625 auflösen.  Mit weniger Bits geht es nicht. Und auf 
der anderen Seite kommst du auch mit vielen Bits niemals(!) ganz genau 
auf 0,1 oder 0,2. Das wird in den allermeisten Fällen immer ein 
0,20004021 (oder so ähnlich) sein...

Dann müsstest du das Ergebnis in 1/10 Einheiten in einen Integer 
abspeichern. Also z.B. statt 123,4 Metern einfach mit 1234 Dezimetern 
rechnen. So würde ich das machen. Denn damit bin ich immer auf den 
Zehntel Meter genau und verschenke nicht einige Bits...

Und was ist jetzt de Unterschied zwischen "deiner" und "meiner" 
Darstellungsweise? Ich habe mein Zahlensystem auf Dezimeter ausgelegt 
und habe so im Kopf eine "Kommaverschiebung" gemacht. Mein Komma ist im 
Kopf fest um den Faktor 10 verschoben.
Und du musst deine Meter mit Binärzahlen irgendwie Dezimal teilen...

[Sergej (Gast)]

Ah na klar, hab gestern vor lauter Bäumen den Wald nicht mehr gesehen, 
ist ja völlig klar :-D

Bezüglich der kommaverschiebung hast du natürlich recht, die gibt es bei 
mir auch nur im Kopf und ohne irgendwelche divisionen^^. Ich musste aber 
die Länge für mein Datenwort festlegen und da war ich mir recht unsicher

[Wolfgang A. (Gast)]

sergej schrieb:
> Mein Inhalt sind Festkommazahlen von 0-90. ich möchte eine Genauigkeit
> von 0,1 erreichen.

D.h. du möchtest den Zahlenbereich von 0/10 bis 900/10 in deine Tabelle 
packen. Mit 10bit hättest du den Bereich 0..1024 zur Verfügung. Wenn das 
Arbeiten mit der Tabelle fix gehen soll, tust du also gut daran, zwei 
Byte pro Eintrag vorzusehen, wenn Speicherplatz absolut knapp ist, 
kannst du natürlich auch anfangen die jeweils 10Bit kompakter abzulegen.

Stellt sich natürlich die Frage, warum du mit Festkommazahlen arbeiten 
möchtest und nicht einfach deinen Bereich geeignet umnormierst.

[foo (Gast)]

sergej schrieb:
> Mein Inhalt sind Festkommazahlen von 0-90. ich möchte eine Genauigkeit
> von 0,1 erreichen.

Das sind gut 900 verschiedene Werte und dafür braucht man 10 Bit.

[Johann L. (gjlayde)]

Die Frage kann man mit den gegebenen Informationen nicht beantworten:

Es ist eine Funktion f(x) zu approximieren, wozu Stützstellen f_i (in 
einer Nachguck-Tabelle abgelegt) verwendet werden sollen.  Werden die 
f_i mit N Bits Nachkommastellen dargestellt, dann lässt sich der dadurch 
entstehende Fehler Δf nach oben abschätzen durch

$$\Delta f = |f_i - f(x_i)| \leqslant 2^{-N-1}$$

unter der Annahme, dass die Werte f_i an den Stellen x_i mit einer 
hinreichend großen Genauigkeit vorberechnet wurden und zur nächsten 
darstellbaren Festkommazahl gerundet sind.

Zur Berechnung von f(x) wird das nächste x_i aufgesucht und das 
zugehörige f_i statt f(x) verwendet.  Bei äquidistanten Stützstellen 
kann man immer erreichen, dass |x - x_i| <= Δx/2 ist wenn Δx der Abstand 
der Stützstellen ist.  Damit ergibt sich als Abschätzung für den Fehler

$$\begin{align}|f(x)-f_i|&\leqslant\Delta{}f+|f(x)-f(x_i)|\\&\leqslant \Delta{}f+|f'(\zeta)|\cdot\Delta x/2\qquad\text{mit}\quad|\zeta-x_i|\leqslant\Delta{}x/2\\&\leqslant\Delta{}f+\sup|f'|\cdot\Delta{}x/2\end{align}$$

Die erste Abschätzung folgt aus der Dreiecksungleichung; die zweite wenn 
man f um x_i in eine Taylorreihe entwickelt und die Entwicklung nach dem 
0. Glied abbricht und eine Restgliedabschätzung nach Schlömlich vornimmt 
(unter der Annahme, dass f differenzierbar ist).  Die dritte Abschätzung 
schätzt den Betrag der Ableitung gegen das Supremum der Ableitung im 
tabellierten Intervall ab.

In den Fehler geht also nicht nur die Darstellung der Festkommazahlen 
ein, sondern — oh Wunder — auch der Abstand der Stützstellen und 
Eigenschaften der zu tabellierenden Funktion.

In deinem Falle willst du erreichen, dass

$$\Delta f + \sup|f'|\cdot\Delta x/2 \quad\stackrel!\leqslant\quad 0.1$$

Falls die so erhaltenen fehlerbehafteten Werte in Rechnungen eingehen, 
dann ist natürlich noch deren Konditionierung zu berücksichtigen und der 
o.g. Fehler so zu gestalten, dass nach der Berechnung der Fehler 
kleiner als 0.1 ist.

Ein sinnvolles Layout einer Nachguck-Tabelle ist so beschaffen, dass

$$2\Delta f \approx \Delta x\,\sup|f'|$$

Wenn Δf winzig klein gemacht wird durch sehr viele Nachkommastellen, 
aber zu wenig Stützstellen vorhanden sind, ist das offenbar 
Verschwendung.  Ditto wenn die Stützstellen sehr dicht sind und dadurch 
immer ein Haufen aufeinander folgende Tabelleneinträge den selben Wert 
haben weil mit zu geriner Genauigkeit gespeichert.

Am einfachsten ist natürlich wenn f eine konstante Funktion ist: dann 
ist sup|f'| = 0.  Ebenfalls einfach sind Sinus, Cosinus und 
Arcus(co)tangens wegen sup|sin'| = 1.

Wenn du also z.B. sin in [0,pi/2] (d.h. 0° bis 90°) tabellieren willst, 
sollten die Stützstellen nicht weiter als 0.1 (bzw. ca 5.7°) voneinander 
entfernt sein und die Tabelleneinträge mindestens 4 Nachkommastellen 
haben.  Für die Tabelle genügen 17 Einträge; jeweils in Abständen von 
pi/32 bzw. 90°/16.

Dabei bin ich davon ausgegangen, dass eine 2-er Potenz für die 
Einteilung einfacher ist als z.B. eine Einteilung in 12 Intervalle, die 
bei 4 Bits ebenfalls ausreichend ist.  Das hat aber nur rechentechnische 
Gründe beim Auffinden des Stützpunktes, evtl. sind auch 12 Stützstellen 
günstiger da 90°/12 = 7.5° ein halbwegs runder Wert ist.

Zu beachten ist, dass die obige Abschätzung i.d.R nicht scharf ist, d.h. 
auch mit weniger Bits bzw. größeren Abständen bleibt man u.U. unter dem 
gewünschten Fehler.

[Wolfgang A. (Gast)]

Statt hier in die Tiefen einer exakten mathematischen Beschreibung 
abzutauchen, ohne über die nötigen Informationen zu verfügen, wäre 
vielleicht erstmal eine etwas genauere Beschreibung des Problems und 
Hintergrundinformation dazu hilfreich.

[Possetitjel (Gast)]

Johann L. schrieb:

> Ein sinnvolles Layout einer Nachguck-Tabelle ist so
> beschaffen, [...]

Sehr hübsch!

Und jetzt alles nochmal für die Hermite-Interpolation :)

SCNR