6
Sind sie nur mit einem Brute-Force-Ansatz herausgefunden oder gibt es einen Algorithmus dabei?Wie werden Logarithmen programmiert?
A
Antwort
14
Die Implementierung einer Funktion wie dem natürlichen Logarithmus in einer anständigen mathematischen Bibliothek hält den Fehler unter einem ulp (Einheit der kleinsten Genauigkeit). Das Ziel des Implementierers einer mathematischen Bibliotheksfunktion ist es, eine optimale Annäherung zu finden, die die gewünschte Genauigkeit mit so wenig Berechnungen wie möglich erreicht. Taylor-Serien sind typischerweise eine schlechte Wahl, weil viel zu viele Terme benötigt werden, um die gewünschte Genauigkeit zu erreichen.
Die typischen Waffen der Wahl sind, den Bereich von allen darstellbaren reellen Zahlen auf eine sehr kleine Region zu reduzieren und dann eine optimale Approximation zu verwenden, die eine genaue Approximation der gewünschten Funktion über diesen engen Bereich liefert. Die typischen Waffen der Wahl für diese optimale Annäherung sind ein Polynom oder ein rationales Polynom (Verhältnis von zwei Polynomen). Die Implementierung enthält nur die Polynomkoeffizienten. Diese Koeffizienten werden durch eine Optimierungstechnik wie den Remes-Exchange-Algorithmus konstruiert.
Im Falle des natürlichen Logarithmus gibt es eine einfache Möglichkeit, die Reichweite zu reduzieren. Reelle Zahlen sind nahezu universell in Form einer Mantisse und einem Exponenten dargestellt wird: x = m * 2 p, wo p eine ganze Zahl und m liegt zwischen 1 und 2. So log (x ) = log ( m) + p * log (2). Der letzte Term, p * log (2), ist nur eine Multiplikation mit einer bekannten Konstante. Das Problem reduziert sich somit auf den Logarithmus einer Zahl zwischen 1 und 2 (oder zwischen 1/2 und 1). Eine weitere Entfernungsreduktion kann unter Verwendung der Tatsache, dass √2 logarithmisch in der Mitte von [1,2] ist, vorgenommen werden. Daher ist alles, was benötigt wird, eine Möglichkeit, den Logarithmus einer Zahl zwischen 1 und √2 zu berechnen. Dies geschieht typischerweise mit einem rationalen Polynom. Das Verhältnis eines Polynompolynoms zweiter Ordnung zu einer dritten Ordnung funktioniert dafür ziemlich gut.
+4
.5 ULP ist ein ehrgeiziges Ziel; es ist das gleiche wie korrekt gerundet, was bedeutet, dass die darstellbare Zahl, die dem mathematisch genauen Ergebnis am nächsten ist, zurückgegeben werden muss. Das CRlibm-Projekt (http://lipforge.ens-lyon.fr/www/crlibm/) versucht dies zu tun, aber es ist unvollständig (z. B. werden inverse hyperbolische Funktionen nicht bereitgestellt). Faithful Rounding (weniger als 1 ULP) ist ein erreichbareres Ziel und typische Bibliotheken erlauben Fehler von mehreren ULP. Rationale Funktionen werden vermieden, da die Aufteilung auf gemeinsame Prozessoren langsam ist. Z. B. könnte eine Tangente eine rationale Funktion verwenden, aber Sinus und Logarithmus verwenden einfache Polynome. –
+0
Guter Kommentar. 0,5 ULP ist übermäßig ehrgeizig.In Bezug auf rationale Polynome gegenüber einfachen: Rationale können besser sein, wenn die Verringerung des Grades die erhöhten Kosten einer Division gegenüber einer Multiplikation mehr als ausgleicht. Ich habe mehrere Implementierungen von 'log' gefunden, die ein rationales Polynom verwenden. Log ist eine sehr nette Funktion bis hin zur Approximation. Die Worst-Case-Fehler treten bei Zahlen in der Nähe von Eins auf, und selbst hier kann der Fehler innerhalb eines ULP gehalten werden. –
+1
Reduzierung der Bereich [1,0, produziert 2,0) große Fehler in der Nähe von log (0.999 ...), als David Hammen kommentiert. Die Implementierungen Ich kenne vermeiden, dieses Problem zu einem Bereich durch die Reduzierung, die 1,0 im Innern, wie [2/3, 4/3) oder [sqrt (0,5), sqrt (2.0)) hat. In der Programmierung gibt es nur ein paar zusätzliche Anweisungen: if (m> constant) {p + = 1; m * = 0,5;} –
2
Es gibt mehrere Möglichkeiten, Logarithmen zu berechnen. Siehe this.
+5
-1. Sie werden nicht "hauptsächlich durch Taylor-Serien-Approximationen berechnet". –
+0
Ich habe die Antwort aktualisiert, um das nicht mehr zu sagen. – Oleksi
+1
Während dieser Link die Frage beantworten kann, ist es besser, die wesentlichen Teile der Antwort hier aufzunehmen und den Link als Referenz zur Verfügung zu stellen. Nur-Link-Antworten können ungültig werden, wenn sich die verknüpfte Seite ändert. - [Aus Bewertung] (/ review/low-quality-posts/18788146) – Syfer
"Brute Force" und "Algorithmus" schließen sich nicht gegenseitig aus, Ihre Frage stellt eine falsche Dichotomie dar. Und die Antwort ist, JA, es gibt einen Algorithmus dabei. –
Ah, ich bin albern, weil ich vergessen habe, dass rohe Gewalt eigentlich ein Algorithmus ist. Vielen Dank. – Taffer
"Brute Force" ist eine Eigenschaft von Algorithmen, bei der Sie mehr Rechenleistung anwenden, um mit weniger Nachdenken davonzukommen (was Sie hätten verwenden können, um einen weniger brutalen Algorithmus zu finden). – starblue