Ist 2 ** x schneller zu berechnen als exp (x)?

12

Vergib die Naivität, die offensichtlich wird, wenn ich diese Frage stelle, sowie die Tatsache, dass ich sie stelle.

Mathematiker verwenden normalerweise da es die einfachste / schönste Basis in der Theorie ist (aufgrund von Kalkül). Aber Computer scheinen alles in Binärform zu tun, ist es also schneller, auf einer Maschine zu rechnen als ?exp2**xMath::exp(x)

Isomorphismen
quelle
7
Über was für eine Nummer sprichst du? Ganzzahl von beliebiger Größe? Gleitkomma fester Größe? Gleitkomma mit beliebiger Genauigkeit?
Gilles 'SO - hör auf böse zu sein'
@ Gilles Es ist ein guter Punkt. Ich wusste nicht, dass der Unterschied wichtig war.
Isomorphismen
3
Ich habe auf einigen Casio-Taschenrechnern gesehen, dass Log und Potenz einer Nicht-E-Zahl viel langsamer sind als ln / exp
phuclv
2
Haben Sie versucht, beide zu steuern und zu sehen, was schneller ist, um zu riskieren, stumpf zu sein? Oder sprichst du von Geschwindigkeit in einem Komplexitätssinn? O(f(n))
Jmite
1
Die Sprache ist verantwortlich für die Auswahl des schnellsten Weges und wird einen guten Job machen. Nur für den Fall, dass die größtmögliche Geschwindigkeit erforderlich ist und Messungen ergeben haben, dass dies für die Leistung relevant ist, sollten Sie sich über
solche Dinge

Antworten:

18

Da dies CS und nicht Stackoverflow ist, gehe ich davon aus, dass Sie eine Frage zur numerischen Analyse und (um die Dinge einfach zu halten) insbesondere zum Gleitkomma nach IEEE-754 stellen. In diesem Fall hängt die Antwort auf Ihre Frage teilweise davon ab, was Sie mit "einfacher" meinen, und teilweise von den Details des Systems.

Keine modernen CPUs, die mir bekannt sind, verfügen über einen eingebauten Befehl, der genau das tut, was Sie entweder für die -Operation (die wir im Folgenden als ihren üblichen Namen in C bezeichnen) oder für 2 x ( ) erwarten . Sie werden beide mit Bibliotheksfunktionen implementiert.exexp2xexp2

Wie bei allen numerischen Methoden für transzendentale Operationen sind einige Sonderfälle zu berücksichtigen:

exp(NaN) = NaN
exp(+Inf) = +Inf
exp(-Inf) = 0

Es gibt jedoch eine andere Sache, die das Problem etwas weniger kompliziert macht: Die nützliche Domäne ist ziemlich klein. Unterläuft für binary32, exp(x)wenn oder so, und überläuft, wenn x > 88,7 oder so. Ungewöhnlich für transzendentale Operationen können wir auch den subnormalen Fall ignorieren, da nicht zu unterscheiden ist, ob subnormal ist. All dies gilt auch für die Domain, mit der Ausnahme, dass sich die Domain geringfügig unterscheidet.x<104x>88.7exp(x)1.0xexp2

Ihre Intuition ist richtig, da die meisten Implementierungen berechnen . Die Kosten für diese Multiplikation mit 1ex=2x/ln2 ist im Vergleich zum Rest des Rechnens trivial. Eine typische Methode verwendet eine vorberechnete Tabelle mitKElementen:1ln2exp2K

exp2(x)=2n×T[j]×P(y)

wobei der ganzzahlige Teil von x ist , enthält die Tabelle T Werte von 2 j / K für alle j im Bereich [ 0 , K ) , und P ist eine polynomielle Annäherung an 2 x (für binär32 ist ein Viertel ausreichend) im Bereich [ 0 , 1nxT2j/Kj[0,K)P2x. Der2n-Teil ist billig, da er nur den Exponenten manipuliert. Tist eine Nachschlagetabelle. SoPist wahrscheinlich der teure Teil der Operation zu sein.[0,1K)2nTP

Ich möchte der Vollständigkeit halber darauf hinweisen, dass Intel x86-FPUs eine Anweisung enthalten f2xm1, die für x im Bereich [ - 1 , 1 ] berechnet . Auf einer modernen CPU ist dies jedoch ein ziemlich teurer und nicht in Pipelines zusammengefasster Befehl, und Sie werden dringend davon abgeraten, ihn zu verwenden. Wie das Intel Optimization Reference Manual in Abschnitt 3.8.5 zu Recht feststellt:2x1x[1,1]

Obwohl x87 transzendentale Anweisungen unterstützt, kann die Implementierung der transzendentalen Funktion in der Softwarebibliothek in vielen Fällen schneller sein.

Bearbeiten: Es wurde in den Kommentaren darauf hingewiesen, dass ich einige der neuen Terminologie in IEEE 754-2008 erklären sollte. Ein Teil der Sprache hat sich seit 1985 und 1987 geändert, und die meisten Leute kennen den alten Jargon weitaus besser.

Die Ausdrücke "binary32" und "binary64" sind die neuen Bezeichnungen für 32-Bit- und 64-Bit-Gleitkommazahlen, die der alte Standard "single" bzw. "double" nannte.

Der Ausdruck "subnormale Zahl" ersetzt den vorherigen Ausdruck "denormalisierte Zahl" oder "denormalisierte Zahl" .

Pseudonym
quelle
Wenn Sie "subnormal" sagen, meinen Sie eindeutig nicht "subgaußisch". meinst du "schlechter als [ein typischer Maßstab]"?
Isomorphismen
2
@isomorphismes Hier bezieht sich 'subnormal' darauf, wie Floats implementiert werden. Siehe denormale Zahlen auf Wikipedia.
Paul Manta
Übrigens habe ich die "typische Methode" nur ein wenig vereinfacht. Es ist möglich, exp2 () und exp () mit ulp-Genauigkeit zu implementieren, indem nur eine kleine (und leicht verständliche) Erweiterung der hier vorgestellten Methode verwendet wird. Eine Erläuterung der kleinen, leicht verständlichen Erweiterung würde jedoch wahrscheinlich die doppelte Länge von die Antwort!
Pseudonym
6

2**x2x<<1 << x

Gartenkopf
quelle
4
nicht wirklich. x vielleicht ein Gleitkomma-Typ
phuclv
1
x
Wenn xes sich nicht um eine Ganzzahl handelt (z. B. 20.75), würden Sie die Mantisse auf 2und den Exponenten auf den gerundeten Wert von xals genauesten Schätzwert festlegen (eine genaue Darstellung ist nicht möglich). Was auch viel schneller ist als "pow".
Damon
1

Wenn 2**xes sich um eine Funktion für ganze Zahlen handelt, stimme ich Stephens Antwort zu, Verschiebung ist billiger. Aber ich sehe , dass typischerweise als 2^xund **Gleitkomma - Potenzierung anzuzeigen. Für diesen Fall würde ich eine ähnliche Leistung zwischen **und erwarten, ^da beide expund pow(die zugrunde liegende Operation für **) beide transzendentale Approximationsoperationen sind.

Tim
quelle
Interessant, ich wusste nicht, dass **es ein Synonym für die Gleitkomma-Version ist (und, dummerweise, hatte ich vergessen, dass die beiden unterschiedlich sein würden).
Isomorphismen
1

Da 2 ^ x = e ^ (x * ln 2) und e ^ x = 2 ^ (x * log2 (e)), würden Sie keinen großen Unterschied erwarten.

Für x nahe Null würde man normalerweise ein Polynom e ^ x = 1 + x + x ^ 2/2 + x ^ 3/6 ... verwenden, das so optimiert ist, dass es so schnell wie möglich abschneidet, während der Rundungsfehler klein bleibt . Offensichtlich ist 2 ^ x ein winziges bisschen langsamer zu berechnen. "x nahe 0" sind normalerweise Werte von x, wobei sqrt (1/2) <= e ^ x <= sqrt (2) ist. Durch Einschränken des Bereichs von x wird sichergestellt, dass der Polynomgrad nicht zu hoch gewählt werden muss.

Für ein größeres x würde man normalerweise 2 ^ x berechnen, indem man x = x '+ x' 'lässt, wobei x' eine ganze Zahl und -0,5 <= x '' <= 0,5 ist. 2 ^ x 'würde dann berechnet werden, indem eine Gleitkommazahl mit dem rechten Bitmuster konstruiert wird, und 2 ^ x' ', indem die e ^ x-Methode für kleines x verwendet wird. Hier ist 2 ^ x etwas schneller. Wenn x außerdem groß ist (z. B. x = 100,3), würde das Multiplizieren von x mit log2 (e) einen inakzeptablen Rundungsfehler verursachen (da es viel weniger Bruchbits gibt), sodass mehr Sorgfalt erforderlich ist.

Und hoffentlich würde eine gute Bibliotheksfunktion dafür sorgen, dass immer x <= y, e ^ x <= e ^ y und 2 ^ x <= 2 ^ y, unabhängig von den Rundungsfehlern. So etwas zu erreichen kann schwierig sein.

gnasher729
quelle
0

Sie müssen verstehen, dass Mathematik auf einem Computer auf unterschiedliche Weise von unterschiedlicher Software ausgeführt wird und hoffentlich einheitliche Antworten liefert. Wenn ich mir die meisten Programme anschaue, denke ich, dass sich Computer wie gute Computer verhalten und die Antwort auf lange Sicht auch für 0 ^ 0 berechnen. Das Problem ist, dass es in Sonderfällen um "Erkennung" geht, die bei digitalen Computern nicht kostenlos ist. Dies bedeutet, dass nur in den Fällen, in denen die Antwort die Dinge "am meisten" beschleunigt, eine Optimierung stattfindet. Aber in diesen Fällen wird es sehr gut vorkommen. Beachten Sie auch, dass möglicherweise mehrere unterschiedliche Erkennungen erforderlich sind, um die richtige Antwort zu erhalten. Dies wird als Geschwindigkeitsoptimierungsstufe bezeichnet und ist auf der Basis der meisten Software, die als GNU "C" bezeichnet wird, in höchstem Maße professionell aufgetreten. Dies liegt daran, dass hier winzige Laufzeitunterschiede von Software zu Software und von Maschine zu Maschine als Qualitätsabnahmewerte herangezogen werden. Bei anderen Interpreten wird in der Regel nur dann eine schnellere Erkennung durchgeführt, wenn als Nebeneffekt früherer Berechnungen ein "Null-Flag" auftritt. wie 0 * x => C0.

Kennzeichen
quelle