amiga-news ENGLISH VERSION
.
Links| Forum| Kommentare| News melden
.
Chat| Umfragen| Newsticker| Archiv
.

amiga-news.de Forum > Programmierung > Log Lookup Table [ - Suche - Neue Beiträge - Registrieren - Login - ]

-1- [ - Beitrag schreiben - ]

03.09.2004, 11:17 Uhr

bubblebobble
Posts: 707
Nutzer 		Hallo!

Ich möchte einen LookUp Table machen für
log(n), wobei n eine float zwischen 0 und 100.000.000 ist.

Problem ist nun, dass ich eine LookUp Table Größe
von ca 10.000 Einträgen machen will. Dadurch würde aber der Wertebreich
bei kleinen Zahlen sehr grob und bei großen Zahlen unnötig fein
aufgelöst.

Weiss jemand wie man das optimieren kann ?
Ich könnte noch linear interpolieren zwischen den Einträgen,
was das prinzipielle Problem aber nicht behebt.
--
Thilo Köhler, Author von:
HD-Rec, Samplemanager, ArTKanoid, Monkeyscript, Toadies, AsteroidsTR, TuiTED, PosTED, UDM, TKPlayer, TKUnpacker
Homepage: http://www.hd-rec.de



[ - Antworten - Zitieren - Direktlink - ]
03.09.2004, 13:13 Uhr

Solar
Posts: 3680
Nutzer 		Hmm... ich weiß nicht, aber bei floats bietet sich eine Lookup-Tabelle nicht wirklich an, oder?

Was spricht gegen die Standardfunktion log()?

[ - Antworten - Zitieren - Direktlink - ]
03.09.2004, 13:20 Uhr

Mad_Dog
Posts: 1944
Nutzer
Zitat:
Original von bubblebobble:

Ich möchte einen LookUp Table machen für
log(n), wobei n eine float zwischen 0 und 100.000.000 ist.

Problem ist nun, dass ich eine LookUp Table Größe
von ca 10.000 Einträgen machen will. Dadurch würde aber der Wertebreich
bei kleinen Zahlen sehr grob und bei großen Zahlen unnötig fein
aufgelöst.

Wenn Du float oder double nimmst, werden die Zahlen im IEEE 754 Format im Speicher abgelegt. Da gibt's keinen Unterschied bezüglich der Genauigkeit bei kleinen oder großen Zahlen. Der Wertebereich für IEEE 754 32 Bit bzw. 64 Bit ist konstant.



--

http://www.norman-interactive.com

[ Dieser Beitrag wurde von Mad_Dog am 03.09.2004 editiert. ]

[ - Antworten - Zitieren - Direktlink - ]
03.09.2004, 13:25 Uhr

Holger
Posts: 8116
Nutzer
Zitat:
Original von bubblebobble:
Weiss jemand wie man das optimieren kann ?
Ja, berechne einfach den Logarithmus und lasse den Lookup und das Interpolieren weg. Damit sparst Du zwei Speicherzugriffe und mehrere Rechenoperationen.

mfg
--
Good coders do not comment. What was hard to write should be hard to read too.

[ - Antworten - Zitieren - Direktlink - ]
03.09.2004, 14:12 Uhr

bubblebobble
Posts: 707
Nutzer 		Also vielleicht hab ich mich nicht klar ausgedrückt:

Ich weiss wie Floats aufgebaut sind.
Die Flaots bewegen sich zwischen 0 und 100.000.000.
Ich soll den logarithmus draus ziehen. Der *Wertebereich*
(NICHT der Definitionsbereich) sind bei einem normalen
Lookup Table schlecht aufgelösst wenn es sich um log handelt.
(ihr wiss ja wie eine Log Kurve aussieht. am Anfang steigts
noch, später immer langsamer).
log (1) = 0
log (10) = 1
log (100) = 2
log (1.000) = 3
log ( 90.000.000) = 7,95
log (100.000.000) = 8

Wenn mein Table 1000 Einteäge besitzt, dann muss ich 100.000er
Schritte im Table machen, dadurch ist der Wertebereich von 0-4 total futsch,
dafür von 4-8 sehr hoch aufgelösst.

Ich will einen Table machen, weil das ganze auf einem PDA
ohne FPU laufen soll. Ich habs mal getestet, ein Table ist
dort ca. 20mal so schnell wie ein log(n).



--
Thilo Köhler, Author von:
HD-Rec, Samplemanager, ArTKanoid, Monkeyscript, Toadies, AsteroidsTR, TuiTED, PosTED, UDM, TKPlayer, TKUnpacker
Homepage: http://www.hd-rec.de



[ - Antworten - Zitieren - Direktlink - ]
03.09.2004, 14:33 Uhr

thomas
Posts: 7718
Nutzer
Also, ich habe verstanden, du möchtest sowas haben:

double log10 (unsigned long n)
{
return (logtable[n]);
}

wobei sich n zwischen 0 und 100.000.000 bewegt und die logtable den entsprechenden Logarithmus zur Basis 10 enthält. Nur sind dir 800MB Tabelle zu viel.

Wie wär's mit sowas:

double log10 (unsigned long n)
{
if (n < 1000)
return (logtab1[n]);
if (n < 1000000)
return (logtab2[n/1000]);
/* 1000000 <= n <= 100000000 */
return (logtab3[n/1000000]);
}

(ist nur ein Beispiel, ob das mathematisch sinnvoll ist, darüber habe ich nicht nachgedacht).

Gruß Thomas

--
Email: thomas-rapp@web.de
Home: home.t-online.de/home/thomas-rapp/

[ - Antworten - Zitieren - Direktlink - ]
03.09.2004, 14:47 Uhr

bubblebobble
Posts: 707
Nutzer 		Einer der mich versteht ;-)
Ja, genau daran hatte ich auch schon gedacht.
Ist besser als nix, ich hoffe die If's machen mir
die Performance nicht wieder kaputt.
Aber auf sowas wirds wohl rauslaufen.

Danke für den Tip.

--
Thilo Köhler, Author von:
HD-Rec, Samplemanager, ArTKanoid, Monkeyscript, Toadies, AsteroidsTR, TuiTED, PosTED, UDM, TKPlayer, TKUnpacker
Homepage: http://www.hd-rec.de



[ - Antworten - Zitieren - Direktlink - ]
03.09.2004, 16:12 Uhr

Holger
Posts: 8116
Nutzer 		Ich kann Dir nur das hier anbieten:
code:
inline float FastLog10(float p_X) 
{ 
    // Retrieve a coarse log value from the exponent of the encoded float 
    int* const intX = reinterpret_cast<int*>(&p_X); 
    const int coarseLog2 = ((*intX >> 23) & 0xFF) - 127; 
    // Set the exponent to 1 
    *intX &= 0x007FFFFF; 
    *intX |= 0x3F800000; 
    // Improve the coarse log value using a quadratic approximation 
    // of log over the range [1, 2] 
    static const float A = -(1.0f / 3.0f); 
    static const float B = 2.0f; 
    static const float C = -(5.0f / 3.0f); 
    p_X = (((A * p_X) + B) * p_X) + C + static_cast<float>(coarseLog2); 
    // Convert log to base 10 and return 
    static const float LogBase10of2 = 0.30102999566398119521373889472449f; 
    return (p_X * LogBase10of2); 
    return p_X;
}
Für andere Logarithmen mußt Du ja nur den Faktor anpassen.

mfg
--
Good coders do not comment. What was hard to write should be hard to read too.

[ - Antworten - Zitieren - Direktlink - ]
03.09.2004, 20:24 Uhr

bubblebobble
Posts: 707
Nutzer
Zitat:
Original von Holger:
Ich kann Dir nur das hier anbieten:
code:
inline float FastLog10(float p_X) 
{ 
    // Retrieve a coarse log value from the exponent of the encoded float 
    int* const intX = reinterpret_cast<int*>(&p_X); 
 ....
    return (p_X * LogBase10of2); 
}
Für andere Logarithmen mußt Du ja nur den Faktor anpassen.

Das ist genial, aber läuft leider nicht unter eMbedded VisualC++.

Er meckert schon, dass nach "inline" kein "(" käme.
komisch. Ich habe es dann direkt eingebaut, weil
ich es nur einmal brauche. Aber dann hat er bei
"reinterpret_cast" gemeckert.
Kann das jemand etwas umschreiben, dass es einfacher für
den Compiler ist ?

Aber man könnte folgendes draus machen:
Ich lese den Exponenten aus der Float raus, das geht
ja schnell. Und daraufhin entscheide ich den Lookup
Table, und mache 8 Tables (wenn der höchste exponent 8 ist).

Danke für die Tips soweit.
--
Thilo Köhler, Author von:
HD-Rec, Samplemanager, ArTKanoid, Monkeyscript, Toadies, AsteroidsTR, TuiTED, PosTED, UDM, TKPlayer, TKUnpacker
Homepage: http://www.hd-rec.de



[ - Antworten - Zitieren - Direktlink - ]
03.09.2004, 21:03 Uhr

bubblebobble
Posts: 707
Nutzer 		@Holger:
Weist du wie ich A, B und C anpassen muss, wenn der
log zwischen [1,100.000.000] liegt und nicht zwischen [1, 2] ?
Ansonsten hab ich das nun am Laufen, evtl. ist es nicht ganz optimal
weil ich diese Super-tricks wie "reinterpret" etc. weggelassen habe,
aber es ist immerhin noch 6mal so schnell wie ein echter log10().

Jetzt werde ich evtl. statt der Verfeinerung mit A, B und C
mehrere Lookup Tables machen.
--
Thilo Köhler, Author von:
HD-Rec, Samplemanager, ArTKanoid, Monkeyscript, Toadies, AsteroidsTR, TuiTED, PosTED, UDM, TKPlayer, TKUnpacker
Homepage: http://www.hd-rec.de



[ - Antworten - Zitieren - Direktlink - ]
05.09.2004, 13:13 Uhr

Holger
Posts: 8116
Nutzer
Zitat:
Original von bubblebobble:
@Holger:
Weist du wie ich A, B und C anpassen muss, wenn der
log zwischen [1,100.000.000] liegt und nicht zwischen [1, 2] ?
Überhaupt nicht.
Du hast den Algorithmus nicht verstanden.
float Zahlen liegen in der Form m * 2 ^ n vor, wobei m zwischen 1 und 2 liegt. Deshalb ist der logarithmus zur Basis 2

n + ln2 m

Und es muß nur der Logarithmus für Werte zwischen 1 und 2 approximiert werden, da Mantisse und Exponent aus der float-Zahl mittels einfache integer-Bitoperationen extrahiert werden kann.
Zitat:
Ansonsten hab ich das nun am Laufen, evtl. ist es nicht ganz optimal
weil ich diese Super-tricks wie "reinterpret" etc. weggelassen habe,...
reinterpret_cast ist genau das, was ein herkömmlicher pointer-cast unter C auch macht, nur daß man damit auch deklariert, daß genau dieses Verhalten gewollt ist.

mfg
--
Good coders do not comment. What was hard to write should be hard to read too.

[ - Antworten - Zitieren - Direktlink - ]
05.09.2004, 13:41 Uhr

bubblebobble
Posts: 707
Nutzer
Zitat:
Du hast den Algorithmus nicht verstanden.
float Zahlen liegen in der Form m * 2 ^ n vor, wobei m zwischen 1 und 2 liegt. Deshalb ist der logarithmus zur Basis 2

n + ln2 m
Ja, habs dann auch gesehen. Vielen Dank nochmal für diesen
Algorithmus, funktioniert prächtig. Ich hab noch eine Version
gemacht, die nur den Exponenten nimmt, das ist 100mal schneller
als log10 auf dem PDA. Das reicht teilweise sogar von der Genauigkeit her, da mein Zahlenbereich ja recht gross ist.

Gibt es irgendeine Quelle woher dieser Algorithmus stammt ?
Ist zwar mehr oder weniger Mathematik, aber ich muss ja sicher
gehen, da ich es in einer Diplomarbeit verwende.
Vor allem eine Quelle für die Approximation wäre hilfreich.
--
Thilo Köhler, Author von:
HD-Rec, Samplemanager, ArTKanoid, Monkeyscript, Toadies, AsteroidsTR, TuiTED, PosTED, UDM, TKPlayer, TKUnpacker
Homepage: http://www.hd-rec.de



[ - Antworten - Zitieren - Direktlink - ]
13.09.2004, 18:16 Uhr

Holger
Posts: 8116
Nutzer 		Den Code habe ich auch nur aus einem Diskussionsforum zum Thema Audioprogrammierung. Aber wie Du selbst feststellst, ist alles bis auf die Approximation trivial.
Für die in dem Code enthaltene Berechnung konnte ich keine Quelle finden, wenn Du eine rechtlich sichere benötigst, kann Du eine andere Approximation aus der Taylor Reihe herleiten. Diese Reihe ermöglicht Polynome beliebigen Grades, je höher, desto genauer. Für den 2. Grad gilt:
ln(x)~=(x-1)-(x-1)²/2
Das kann man umstellen zu ½(2(x-1)-(x-1)²)=½(x-1)(2-(x-1))
=½(x-1)(3-x)
Um vom natürlichen Logarithmus zur Basis 2 zu kommen, muß man noch durch ln(2) teilen, das kann man mit ½ zusammenfassen zu:

(x-1)(3-x)*0.72134752044448

Ändere also im Code
code:
static const float A = -(1.0f / 3.0f); 
    static const float B = 2.0f; 
    static const float C = -(5.0f / 3.0f); 
    p_X = (((A * p_X) + B) * p_X) + C + static_cast<float>(coarseLog2);
zu
code:
p_X = (p_X-1)*(3-p_X)*0.72134752044448 + static_cast<float>(coarseLog2);

Dann hast Du einen nachvollziehbaren Algorithmus.

mfg

PS: Ich hoffen, es hat sich jetzt kein Fehler eingeschlichen...
--
Good coders do not comment. What was hard to write should be hard to read too.

[ Dieser Beitrag wurde von Holger am 13.09.2004 editiert. ]

[ - Antworten - Zitieren - Direktlink - ]
14.09.2004, 06:25 Uhr

Solar
Posts: 3680
Nutzer 		Wer es genauer haben will als eine grobe Annäherung, dem sei Cody & Waite empfohlen - "Software Manual for the Elementary Functions". Kostet eine ganze Stange Geld, bietet aber sehr gutes Material.

[ - Antworten - Zitieren - Direktlink - ]
14.09.2004, 10:49 Uhr

bubblebobble
Posts: 707
Nutzer 		@Holger

Vielen Dank. Das war mir sehr hilfreich.
(und lehrreich :look: )
--
Thilo Köhler, Author von:
HD-Rec, Samplemanager, ArTKanoid, Monkeyscript, Toadies, AsteroidsTR, TuiTED, PosTED, UDM, TKPlayer, TKUnpacker
Homepage: http://www.hd-rec.de



[ - Antworten - Zitieren - Direktlink - ]
01.10.2004, 13:37 Uhr

bubblebobble
Posts: 707
Nutzer
Zitat:
Original von Holger:
Das kann man umstellen zu ½(2(x-1)-(x-1)²)=½(x-1)(2-(x-1))
=½(x-1)(3-x)
Um vom natürlichen Logarithmus zur Basis 2 zu kommen, muß man noch durch ln(2) teilen, das kann man mit ½ zusammenfassen zu:

(x-1)(3-x)*0.72134752044448

Ändere also im Code
code:
static const float A = -(1.0f / 3.0f); 
    static const float B = 2.0f; 
    static const float C = -(5.0f / 3.0f); 
    p_X = (((A * p_X) + B) * p_X) + C + static_cast<float>(coarseLog2);
zu
code:
p_X = (p_X-1)*(3-p_X)*0.72134752044448 + static_cast<float>(coarseLog2);

Die Approximation mit dem Tylorpolynom für ln x habe ich nachvollzogen,
das funktioniert auch. Aber in deinem Codebeispiel wird eine andere
Aproximation gemacht, wie du siehst ergibt dich nicht das Polynom
1/2(x-1)(3-x)
sondern
1/3(x-1)(5-x)
hm...
Wo kommt das denn her ? Die letztere Version ist 10mal genauer im
Druchschnitt. Es wird auch nicht mit ln 2 Dividiert, deshalb müsste
das so eine Art Taylor Polynom direkt für log10 sein. Ich kann das
aber nicht herleiten. Evtl. ist das kein Taylor Polynom sondern was
anderes, was nur so ähnlich aussieht ?

--
Thilo Köhler, Author von:
HD-Rec, Samplemanager, ArTKanoid, Monkeyscript, Toadies, AsteroidsTR, TuiTED, PosTED, UDM, TKPlayer, TKUnpacker
Homepage: http://www.hd-rec.de



[ - Antworten - Zitieren - Direktlink - ]
01.10.2004, 16:08 Uhr

bubblebobble
Posts: 707
Nutzer 		@Holger:

ln(x) ~= 1/2(x-1)(3-x)
scheint eine Approximation für ln(x) zu sein, wärend

ld(x) ~= 1/3(x-1)(5-x) (?)
wohl eine Appromixation für ld(x) ist. (Logatihmus Dualis,
also zur Basis 2).

Kannst du das bestätigen ?
Die zweite Variante ist dabei wesentlich genauer,
ca. um den Faktor 10. Ich kann leider kein Taylor Polynom
finden oder herleiten was auf das herauskommt.

--
Thilo Köhler, Author von:
HD-Rec, Samplemanager, ArTKanoid, Monkeyscript, Toadies, AsteroidsTR, TuiTED, PosTED, UDM, TKPlayer, TKUnpacker
Homepage: http://www.hd-rec.de



[ - Antworten - Zitieren - Direktlink - ]
02.10.2004, 17:27 Uhr

Holger
Posts: 8116
Nutzer
Zitat:
Original von bubblebobble:
@Holger:

ln(x) ~= 1/2(x-1)(3-x)
scheint eine Approximation für ln(x) zu sein, wärend

ld(x) ~= 1/3(x-1)(5-x) (?)
wohl eine Appromixation für ld(x) ist. (Logatihmus Dualis,
also zur Basis 2).

Kannst du das bestätigen ?
Natürlich, deshalb mußt Du ja bei der oberen Variante durch ln(2) teilen, bei der unteren nicht.
Zitat:
Die zweite Variante ist dabei wesentlich genauer,
ca. um den Faktor 10.
Konnte ich nicht beobachten. Die Genauigkeit hing hauptsächlich von der Genauigkeit der Konstante ab. Bei den meisten Prozessoren spielt es für die Performance keine Rolle, ob die Zwischenrechnungen in float oder double stattfinden, deshalb kann man dafür double verwenden.
Zitat:
Ich kann leider kein Taylor Polynom finden oder herleiten was auf das herauskommt.
Deshalb habe ich ja auch die Taylor-Variante angeboten, weil ich nicht weiß, wie die erste Variante hergeleitet wurde.

mfg
--
Good coders do not comment. What was hard to write should be hard to read too.

[ - Antworten - Zitieren - Direktlink - ]
02.10.2004, 21:52 Uhr

bubblebobble
Posts: 707
Nutzer 		Naja, die Genauigkeit hängt eigentlich viel mehr von der
Approximations Formel ab.

Beispiel:

ln(x) ~= 1/2(x-1)(3-x) , x aus (0,2]

Dann wäre ln(2) ~= 1/2 * 1 * 1 = 0.5
Tatsächlich ist aber ln(2) = 0.693...

ABER nach dieser Formel:
ld(x) ~= 1/3(x-1)(5-x)
ld(2) ~= 1/3 * 1 * 3 = 1
ld(2) = 1

Da ist es wurscht ob ich mit Float oder Double rechne.
Ich hab das über ein paar Tausend Testdaten laufen lassen, und
die Approximation des Log Dualis war 10 mal genauer, also eine
Dezimalstelle besser. Deshalb würde ich gerne diese Formel
benutzen, aber da es eine Diplomarbeit ist muss ich das natürlich
irgendwie fundieren können.
Schade dass du nicht mehr weisst woher das ist. Ein Taylor Polynom
scheint es nicht zu sein, jedenfalls kann ich es nicht herleiten.
Trotzdem vielen Dank für deine Hilfe!


--
Thilo Köhler, Author von:
HD-Rec, Samplemanager, ArTKanoid, Monkeyscript, Toadies, AsteroidsTR, TuiTED, PosTED, UDM, TKPlayer, TKUnpacker
Homepage: http://www.hd-rec.de



[ - Antworten - Zitieren - Direktlink - ]
03.10.2004, 13:07 Uhr

Holger
Posts: 8116
Nutzer
Zitat:
Original von bubblebobble:
Naja, die Genauigkeit hängt eigentlich viel mehr von der
Approximations Formel ab.

Beispiel:

ln(x) ~= 1/2(x-1)(3-x) , x aus (0,2]

Dann wäre ln(2) ~= 1/2 * 1 * 1 = 0.5
Tatsächlich ist aber ln(2) = 0.693...
Wieso betrachtest Du für die Analyse der Genauigkeit des Algorithmus nicht auch den den Algorithmus, den Du verwendest?
Der verwendete Algorithmus zerlegt nunmal die IEEE-FP Zahl, bevor Du approximierst, und dann ist es vollkommen uninteressant, wie ungenau die Formel für den Wert 2 ist, da die Matisse _immer_ in [1, 2[ liegt, das heißt für die Zahl 2 ist die Mantisse 1.

Da ln(1) = 0 und beide Formeln EXAKT auf dieses Ergebnis kommen, bleibt nur der Exponent aus Deiner Floating-Point Zahl übrig, EXAKT 1.
Zitat:
Ich hab das über ein paar Tausend Testdaten laufen lassen, und
die Approximation des Log Dualis war 10 mal genauer, also eine
Dezimalstelle besser.
Das sehe ich da oben irgendwie nicht, Du vergleichst einen natürlichen Logarithmus mit einem zur Basis zwei für eine in Bezug auf den eigentlichen Algorithmus irrelevanten Zahl. Wie Du den Begriff Genauigkeit definierst, will ich da schon gar nicht wissen. Eine solche Genauigkeitsbetrachtung ist vollkommener Unsinn, wenn Du bereits im vorhinein eine nichtzutreffende Annahme zur Grundlage machst. Es ist vollkommen egal, wie genau ein Teil ist, Du willst schließlich das Endergebnis haben, das war log10, und das war bei meinen Testreihen stellenweise sogar _genauer_ als die andere Variante. Abgesehen davon, hast Du von Zahlenbereichen gesprochen, bei denen der Exponent so hoch ist, daß Du sogar mit dem Gedanken gespielt hast, die Approximation ganz wegzulassen. Da frage ich mich schon, wieso Du Dich jetzt an so minimale Abweichungen stößt. Schließlich ist die max. Abweichung von ca. 0.2 _absolut_, das heißt unabhängig von der Größenordnung des Endergebnisses.

mfg
--
Good coders do not comment. What was hard to write should be hard to read too.

[ - Antworten - Zitieren - Direktlink - ]
23.11.2004, 11:37 Uhr

bubblebobble
Posts: 707
Nutzer 		Also die Approximation mit

ln x =~ 1/2(x-1)(3-x)

ist ein Taylorpolynom, das ist einfach.

ld x =~ 1/3(x-1)(5-x)

ist vermutlich KEIN Taylorpolynom. Es könnte
evtl. ein Chebysev Polynom sein. Kennst sich da jemand aus und kann
das bestätigen oder sogar herleiten ?
Das wäre mir eine riesen Hilfe!

--
Thilo Köhler, Author von:
HD-Rec, Samplemanager, ArTKanoid, Monkeyscript, Toadies, AsteroidsTR, TuiTED, PosTED, UDM, TKPlayer, TKUnpacker
Homepage: http://www.hd-rec.de



[ - Antworten - Zitieren - Direktlink - ]

-1- [ - Beitrag schreiben - ]


amiga-news.de Forum > Programmierung > Log Lookup Table [ - Suche - Neue Beiträge - Registrieren - Login - ]


.
Impressum | Datenschutzerklärung | Netiquette | Werbung | Kontakt
Copyright © 1998-2024 by amiga-news.de - alle Rechte vorbehalten.
.