Effiziente Umsetzung des natürlichen Logarithmus (ln) und Potenzierung
Im Grunde bin ich auf der Suche für die Umsetzung von log()
und exp()
Funktionen in der C-Bibliothek <math.h>
. Ich arbeite mit 8-bit-mikrocontroller (OKI 411 und 431). Ich brauche zu berechnen Mittlere Kinetische Temperatur. Die Voraussetzung ist, dass wir sollten in der Lage sein zu berechnen, MKT so schnell wie möglich und mit so wenig code wie möglich Speicher. Der compiler kommt mit log()
und exp()
Funktionen in <math.h>
. Aber durch den Aufruf einer Funktion und die Verknüpfung mit der Bibliothek bewirkt, dass die code-Größe zu erhöhen, um 5 Kilobyte, die nicht in die Mikro, mit der wir arbeiten (OKI 411), weil der code bereits verbraucht ~12 Kb des verfügbaren ~15K code-Speicher.
Die Umsetzung, die ich Suche, sollten Sie nicht verwenden Sie eine andere C-Bibliothek von Funktionen (wie pow(), sqrt() etc.). Dies ist, da alle Bibliotheks-Funktionen sind verpackt in einer Bibliothek und selbst wenn eine Funktion aufgerufen wird, wird der linker bringt ganze 5K-Bibliothek, um code-Speicher.
BEARBEITEN
Sollte der Algorithmus korrekt bis zu 3 dezimal stellen.
vergaß hinzuzufügen. danke für die Erinnerung. ich habe bearbeitet Sie meine Frage. 🙂
Auch, was sind die input-und output numerische Formate? Fixed-point wie 8.8? Es klingt wie Sie davon profitieren würde durch die Speicherung ein offset relativ zu 273 Kelvin, d.h. Celsius.
der Eingang/Ausgang ist nicht, keine Sorge. was meinst du mit 'bias relativ zu 273K'?
Da die 273 ist eine große Anzahl im Verhältnis zum Wert der Temperatur in Celsius, Sie können Holen Sie mehr Präzision aus dem gleichen bits durch die Speicherung Celsius statt Kelvin. Tatsächlich, das zeigt, warum der Eingang/Ausgang ist ein Anliegen. Als Alexei erwähnt, Temperaturbereich wirkt sich auf die Wahl der Formel.
InformationsquelleAutor Donotalo | 2012-03-21
Du musst angemeldet sein, um einen Kommentar abzugeben.
Die Taylor-Reihe für e^x konvergiert extrem schnell, und Sie können optimieren Sie Ihre Implementierung mit der Genauigkeit, die Sie benötigen. (http://en.wikipedia.org/wiki/Taylor_series)
Die Taylor-Reihe für log ist nicht so schön...
ln
werden im Bereich [0.94, 0.98]. ich denke, taylor-Reihe ist gut genug für die Angleichung fürln
zu.Ich bin spät zur party hier. Just bewusst sein, dass der Bereich, den Sie angegeben haben, ist in der "nicht nett" Teil der Taylor-Reihe für den natürlichen Logarithmus: en.wikipedia.org/wiki/Natural_logarithm#Series
InformationsquelleAutor dsharlet
Mithilfe der Taylor-Reihe ist nicht die einfachste weder der Schnellste Weg, dies zu tun. Die meisten professionellen Implementierungen verwenden die approximation Polynome. Ich werde Ihnen zeigen, wie Sie zur Erzeugung einer in Ahorn (es ist ein computer-algebra-Programm), mit dem Remez-Algorithmus.
3 Ziffern Genauigkeit führen Sie die folgenden Befehle in Maple:
Seine Antwort ist das folgende Polynom:
Mit dem maximalen Fehler von: 0.000061011436
Generierten wir ein Polynom, das entspricht ln(x), jedoch nur innerhalb des [1..2] - Intervall. In größeren Abständen ist nicht klug, denn das würde die maximalen Fehler sogar noch mehr. Stattdessen tun die folgende ZERLEGUNG:
Also zuerst die höchste Potenz von 2, die ist noch kleiner als die Anzahl (Siehe: Was ist der Schnellste/effizienteste Weg, um die höchste bit (msb) in eine Ganzzahl in C?). Diese Zahl ist eigentlich die Basis-2-Logarithmus. Teilen Sie mit diesem Wert, dann ist das Ergebnis wird in der 1..2-Intervall. Am Ende werden wir hinzufügen müssen, um die n*ln(2) um das Endergebnis.
Einer Beispiel-Implementierung für zahlen >= 1:
Obwohl, wenn Sie planen, es zu benutzen nur in der [1.0, 2.0] Intervall, dann ist die Funktion wie:
Ich würde schätzen,] 0; 1] ein weiteres Polynom, und verwenden Sie eine if/else-Anweisung, um zu entscheiden, welche zu verwenden. Dies ist, dass polynomyal (für diese geringe Genauigkeit):
-8.6731532+(129.946172+(-558.971892+(843.967330-409.109529*x)*x)*x)*x
Eigentlich kann man finden, warum diese nicht ausgewählt, da die richtige Antwort. + mit etwas Suche findet man bereit zu gehen Umsetzung im Mathematik-Sonne-Bibliothek Implementierung (Sonnenmassen).
InformationsquelleAutor Crouching Kitten
Würden einfache Tabelle mit interpolation zwischen den Werten Ansatz arbeiten? Wenn die Bereiche von Werten sind begrenzt (was wahrscheinlich ist für Ihren Fall - ich bezweifle, dass die gemessenen Temperaturen haben große Auswahl) und eine hohe Genauigkeit ist nicht erforderlich, es kann funktionieren. Sollte leicht zu testen auf normalen Maschine.
Hier ist eines von vielen Themen auf dem Tisch Repräsentation von Funktionen: Berechnung vs. lookup-Tabellen für Sinus-Leistung?
Es möglicherweise noch eine option, um zu versuchen (auch nicht für die benötigte Präzision) - beide exp/ln-Funktionen sind kontinuierlich, so müssen Sie möglicherweise viel weniger Punkte für die erforderliche Genauigkeit des Ergebnisses. Ich sehe nicht die Temperatur direkt als argument der exp/ln in der Formel, so dass die aktuellen Bereiche für die Argumente sind anders - es ist schwer vorherzusagen, wenn die sparse-Tabelle funktionieren würde.
InformationsquelleAutor Alexei Levenkov
Wenn Sie nicht brauchen, floating-point Mathematik für irgendetwas anderes, können Sie berechnen eine Ungefähre Bruch-Basis-2-log-ziemlich leicht. Starten Sie durch die Verlagerung Ihres Wert nach Links, bis es 32768 oder höher und speichern Sie die Anzahl der Zeiten, die Sie haben, dass in
count
. Dann wiederholen Sie einige Male (je nach Ihren gewünschten Skalierungsfaktor):Wenn die obige Schleife wiederholt sich 8 mal, dann den Logarithmus zur Basis 2 von der Zahl count/256. Wenn Sie zehn mal, Graf/1024. Wenn elf, Anzahl/2048. Effektiv, diese Funktion funktioniert durch die Berechnung der ganzzahlige Potenz-von-zwei-Logarithmus von n**(2^Wiederholungen), jedoch mit dazwischenliegenden Werten skaliert, um zu vermeiden, überlauf.
Hat dieser Algorithmus einen Namen haben?
Ich kenne keine Namen für Sie. Ich entwickelte es, wenn ich zur Messung der RC-Zeitkonstante einer Schaltung zwei ADC-Messwerten, die eine bekannte mal abgesehen (compute log jeweils zu Lesen, und nehmen Sie die skalierten reziproken der Unterschied), aber ich wäre schockiert, wenn ich war der erste, der diesen Ansatz. Um zu sehen, was der Algorithmus tut, kann es hilfreich sein, zu überlegen, was passieren würde, wenn es verwendet eine beliebige Präzision Ganzzahlen und statt der Verschiebung n direkt 16 bits jedes mal, verlagerte sich der 32768 Links um 16 bits.
Das Ziel der Funktion ist dann zu finden, den Wert von
count
so, dass wennn0
ist der Anfangswertn
,n0**rounds * 2**count
wäre im Bereich2**(16*rounds-1) and
2**(16*Runden)-1`.Im Falle Sie sind sich nicht bewusst, der Grund für das erneute Interesse in diese Antwort: space.stackexchange.com/questions/30952/...
InformationsquelleAutor supercat
Zusätzlich zu Hocken Kätzchens Antwort, die mir inspiration, können Sie bauen eine pseudo-rekursiv (bei den meisten 1-self-call) Logarithmus zu vermeiden, mit Polynomen. In pseudo-code
Dies ist ziemlich effizient und präzise, da auf [1; 2) die taylor-Reihe konvergiert VIEL schneller, und wir erhalten so eine Zahl 1 <= < 2 mit dem ersten Aufruf der ln, wenn unser Eingang ist positiv, aber nicht in diesem Bereich.
Finden Sie 'b' als unbiased exponent aus den Daten in der float x, und a ' aus der Mantisse des float x (a ist genau die gleiche float x, aber jetzt mit exponent biased_0 eher als exponent biased_b). LN2 sollte gehalten werden, der als makro in hexadecimal floating point notation IMO. Sie können auch http://man7.org/linux/man-pages/man3/frexp.3.html.
Auch, der trick
für "Speicher-casting" double, unsigned long, sondern als "Wert-casting", ist sehr nützlich zu wissen beim Umgang mit float-Speicher-Weise, als bitweise Operatoren werden Warnungen oder Fehler vom compiler abhängig.
- 1
bei der Taylor-expansion? Das problem, das ich sehe, ist, dass die Mantisse ist eine ganze Zahl, und nicht in der[1; 2)
Bereich, und diefrexp
eigentlich macht einige Berechnungen zu normalisieren, die Wert.Dies ist eine vereinfachte version meines Codes, ich habe einige Optimierungen praktisch. - die y = x - 1 <=> ln(1 + y) = ln(x) wird verwendet, um den Anruf taylor_expansion als ln(1 + y) = ln(x) = taylor(y) = y - y^2/2 + y^3/3... Es ist nur eine einfache Implementierung, aber es ist wahr, es könnte ein wenig verwirrend auf den ersten.
- Ich habe auch eine else if (1.9 <= x < 2) return ln(x * 2 / 3) + ln (3/2); - Klausel, um zu verhindern, dass die zahlen sehr nahe an Ihrer Decke von der Funktion der Zeit aus (versuchen Sie, den Algorithmus mit einem Wert 1e+23 (die näher an 9.9999999999999 e+22), sehen Sie, ohne dieses kleine Update sind einige Fälle apocalyptically langsam. Beachten Sie, dass ich immer 2/3 und ln(3/2) als makro-hexadezimal Fließkomma-Konstanten.) Gotta get das Protokoll zu konvergieren ! x)
- für frexp, ich gehe hausgemacht: =>
u64 extract = *(u64*)(&d)
; =>norm = (extract & (0x8000000000000000 | 0xFFFFFFFFFFFFF)) | 0x3FF0000000000000;
undd = *(double*)(&norm);
für meine normalisierten Bruchteil (exp == 0) =>exp = ((extract << 1) >> 53) - 1023
für meine exponent. Sie können prüfen, ob andere spezielle Werte, die beim starten der log (ie, +inf gibt +inf, 1. gibt 0 zurück., etc). Beachten Sie, dass => dienen zu bedeuten ein \n in meinem Kommentar Klartext hier xdInformationsquelleAutor Tristan Duquesne