Wie werden die Exponenten berechnet?

Question

Ich versuche, die asymptotische Laufzeit von einem meiner Algorithmen zu bestimmen, die Exponenten verwendet, aber ich bin nicht sicher, wie Exponenten programmatisch berechnet werden.

Ich bin auf der Suche speziell für die pow () Algorithmus für doppelte Genauigkeit verwendet, Gleitkommazahlen.

Answer 1

Ich habe eine Chance hat, bei fdlibm Implementierung zu suchen. Die Kommentare beschreiben den Algorithmus verwendet:

 *                    n
 * Method:  Let x =  2   * (1+f)
 *      1. Compute and return log2(x) in two pieces:
 *              log2(x) = w1 + w2,
 *         where w1 has 53-24 = 29 bit trailing zeros.
 *      2. Perform y*log2(x) = n+y' by simulating muti-precision
 *         arithmetic, where |y'|<=0.5.
 *      3. Return x**y = 2**n*exp(y'*log2)

, gefolgt von einer Auflistung aller Sonderfälle behandelt (0, 1, inf, nan).

Die intensivsten Abschnitte des Codes, nach all der Sonderfallbehandlung, beinhalten die log2 und 2** Berechnungen. Und es gibt keine Schleifen in einer von denen. So ist die Komplexität der Floating-Point-Primitiven ungeachtet, es sieht aus wie ein asymptotisch konstanten Algorithmus.

Gleitkommaoperationen Experten (von denen ich gehört nicht) sind willkommen zu kommentieren. : -)

Answer 2

Es sei denn, sie einen besseren Weg entdeckt haben, es zu tun, ich glaube, dass Richtwerte für Trig, logarithmische und exponentielle Funktionen (für eine exponentielles Wachstum und Verfall, zum Beispiel) werden unter Verwendung von Rechenregeln im Allgemeinen berechnet und Taylor-Serie Erweiterungen ein ungefähres Ergebnis genau innerhalb der gewünschten Genauigkeit zu erzeugen. (Siehe jedes Calculus Buch für Details zur Energie Serie, Taylor-Reihe, und Maclaurin Reihenentwicklungen von Funktionen.) Bitte beachten Sie, dass es schon eine Weile her, seit ich etwas davon habe, so konnte ich Ihnen nicht sagen, zum Beispiel, wie genau zu berechnen die Anzahl der Begriffe in der Serie müssen Sie umfassen garantiert einen Fehler, der klein genug vernachlässigbar in doppelter Genauigkeit Berechnung zu sein.

Zum Beispiel kann die Taylor / Maclaurin Serie Erweiterung für e ^ x ist dies:

      +inf [ x^k ]           x^2    x^3      x^4        x^5
e^x = SUM  [ --- ] = 1 + x + --- + ----- + ------- + --------- + ....
      k=0  [  k! ]           2*1   3*2*1   4*3*2*1   5*4*3*2*1

Wenn Sie alle Bedingungen (k von 0 bis unendlich) nehmen, diese Erweiterung ist genau und vollständig (kein Fehler).

Wenn Sie jedoch die Bedingungen bis ins Unendliche gehen alle nicht, aber Sie nach 5 Begriffen oder 50 Begriffen oder was auch immer sagen stoppen, produzieren Sie ein ungefähres Ergebnis, das von der tatsächlichen e unterscheidet ^ x Funktionswert durch einen Rest, der relativ leicht zu berechnen ist.

Die gute Nachricht für Exponentialgrößen ist, dass es schön und die Bedingungen seiner Polynomausdehnung sind ziemlich einfach konvergiert iterativ zu codieren, so dass Sie auf könnte (Wiederholung, KöNNTE - erinnern eine Weile) nicht einmal im Voraus berechnen muß gewesen, es ist, wie viele Begriffe, die Sie benötigen, um Ihre Fehler zu gewährleisten, sind weniger als Präzision, da Sie die Größe des Beitrags bei jeder Iteration testen und stoppen, wenn es nahe genug, um zu Null wird. In der Praxis ist, weiß ich nicht, ob diese Strategie sinnvoll ist oder nicht - ich versuche es müsste. Es gibt wichtige Details Ich habe lange über seit vergessen. Sachen wie:. Maschinengenauigkeit, Maschinenfehler und Rundungsfehler, etc.

Bitte beachten Sie, dass, wenn Sie nicht e verwenden ^ x, aber Sie tun, Wachstum / Zerfall mit einer anderen Basis wie 2 ^ x oder 10 ^ x, die sich annähernden Polynomfunktion ändert.

Answer 3

Die übliche Vorgehensweise, um eine an die b zu erhöhen, für eine ganze Zahl Exponent, so etwas wie das geht:

result = 1
while b > 0
  if b is odd
    result *= a
    b -= 1
  b /= 2
  a = a * a

Es ist in der Größe des Exponenten im allgemeinen logarithmisch. Der Algorithmus basiert auf der Invariante "a ^ b * result = a0 b0 ^", wobei a0 und b0 sind die Anfangswerte von a und b.

Für negative oder nicht ganzzahligen Exponenten, Logarithmen und Annäherungen und numerische Analyse benötigt werden. Die Laufzeit wird auf dem Algorithmus ab, das verwendet und welcher Präzision der Bibliothek für abgestimmt ist.

Edit:. Da scheint es ein gewisses Interesse zu sein, hier ist eine Version ohne die zusätzliche Multiplikation

result = 1
while b > 0
  while b is even
    a = a * a
    b = b / 2
  result = result * a
  b = b - 1

Answer 4

Wenn ich eine Funktion pow Targeting Intel schreiben, würde ich wieder exp2 (log 2 (x) * y). Intels Mikro für log2 ist sicherlich schneller als alles, was ich Code in der Lage sein würde, auch wenn ich mein erstes Jahr Kalkül und grad Schule numerische Analyse erinnern kann.

Answer 5

Sie können für die Berechnung der exp (n * ln (x)) verwenden x ⁿ . X und n können mit doppelter Genauigkeit sein, Gleitkommazahlen. Natürlicher Logarithmus und Exponentialfunktion berechnet werden Taylor Serie. Hier können Sie Formeln finden: http://en.wikipedia.org/wiki/Taylor_series