Schnelles Berechnen der e-Funktion

mowo*fs*

Hallo,

kennt jemand einen weg die e-Funktion schneller zu berechnen als mit exp(x)?
Ich muß das in meinem Programm sehr oft machen. selbst kleine Verbesserungen
würden helfen.

Mfg,
Moritz

Für welche x?

mowo*fs*

zwischen 0 und -50

SeppJ

Eine Möglichkeit da noch was rauszuholen ist es, eine Tabelle mit vorberechneten Ergebnissen zu verwenden.

DerFrosch

Wenn der Wert nicht extrem genau sein muss, kannst du ja selbst eine Funktion exp(x) mit einer Taylor-Reihe approximieren, die nicht so viele Iterationen macht. Kommt aber auch auf die Werte von x an. Wenn die alle ziemlich nahe beieinader liegen, dann suchst du dir den mittleren Wert und tust die Reihe nach diesem Entwicklungspunkt annähern...

EDIT: Hm, aber für werte zwischen 0 und -50 dürfte das schwer werden...

It0101

Eine Mischung aus beiden Lösungen

Du berechnest e^x vorher für alle ganzzahligen Werte zwischen 0 und -50

Beispiel für Kommazahlen:

x = -0.5;

Du legst eine lineare Funktion zwischen exp( 0 ) und exp( -1 ) an und suchst auf dieser Geraden den Wert für dein x. ( Interpolation sozusagen )

Wenn du es noch genauer brauchst, kannst du die Auflösung deiner vorherigen Berechnungen ja noch erhöhen. Also z.B. mit einer Auflösung von 0.5, oder 0.1.

It0101

Ich habe meine Idee hier mal getestet für das Beispiel der e-Funktion:

#include <iostream>
#include <vector>
#include <math.h>
#include <windows.h>

using namespace std;

struct TSpeedCalc
{
	double X, Y, m, n;
};

void PrepareCalc( vector<TSpeedCalc> *Database, double Start, double End, double Solution )
{
	int N = (int)( ( End - Start ) / Solution ) + 1;
	for ( int i = 0; i < N; ++i )
	{
		TSpeedCalc tmp;
		tmp.X = Start + i * Solution;
		tmp.Y = exp( tmp.X );
		Database->push_back( tmp );
	}
	for ( int j = 0; j < N-1; ++j )
	{
		(*Database)[j].m = ( (*Database)[j].Y - (*Database)[j+1].Y ) / ( (*Database)[j].X - (*Database)[j+1].X );
		(*Database)[j].n = (*Database)[j].Y - (*Database)[j].m * (*Database)[j].X;
	}

}

double GetOtherValue( vector<TSpeedCalc> *Database, double x )
{
	int size = (int)Database->size();
	for ( int i = 0; i < size-1; ++i )
	{
		if ( (*Database)[i].X == x )
			return (*Database)[i].Y;
		if ( (*Database)[i+1].X == x )
			return (*Database)[i+1].Y;
		if ( ( x > (*Database)[i].X ) && ( x < (*Database)[i+1].X ) )
		{
			return (*Database)[i].m * x + (*Database)[i].n;
		}
	}
	return -1;
}

int main(int argc, char* argv[])
{
	vector<TSpeedCalc> Database;

	// Berechnet einige Werte im Interval
	PrepareCalc( &Database, 0, 10, 0.1 );

	unsigned long StartTime = GetTickCount();
	double val;
	// Berechnet einen speziellen Wert durch Interpolation
	for ( int i = 0; i < 100000; ++i )
		val = GetOtherValue( &Database, 0 + i * 0.00009998 );
	unsigned long EndTime = GetTickCount();

	cout << "Zeitaufwand in ms: " << EndTime - StartTime << endl;

	return 0;
}

In dem Fall habe ich mal 100000 Interpolationen durchgeführt und benötige dabei ~700ms.

EDIT: der Parameter END sollte natürlich immer größer sein als der Parameter START. Für restliche Feinheiten bitte selber sorgen

knivil

Nachdenken Leute:
exp( x + y ) = exp( x ) * exp( y )

Dadurch kann man sich viel sparen. Z.B. Tabelle fuer 10 9 ... 0 -1 ... -10 anlegen und dann z.B. eine mit hoeherer Aufloesung zwischen 0 und 1. (Das kann man beliebig weit treiben.) Dann kann man immer noch mittels Taylor mit einem Polynom interpolieren.

PS: Den obigen Quelltext finde ich nicht schoen. Ausserdem koennte man ja noch den mittleren/maximalen (quadratischen) Fehler (Standardabweichung, Regressionskoeffizient, ... ) ausrechnen, mit der e^x approximiert wird. Geschwindigkeit allein zaehlt nicht. Auch wuerde ein Vergleich mit der built-in Funktion nicht schaden, um zu sehen, ob es ueberhaupt was gebracht hat. 700ms fuer 100... sagt gar nichts aus.

Werner Salomon

It0101 schrieb:

In dem Fall habe ich mal 100000 Interpolationen durchgeführt und benötige dabei ~700ms.

Bei mir auf dem PC läuft Dein Code in knapp 80ms durch. Wenn ich aber Deinen Aufruf durch

exp( 0 + i * 0.00009998 ); // Zeile 63

ersetze, dann sind es nur 4ms - also so ca. Faktor 20 schneller.

Man sollte doch die Qualitäten von Systemsoftwareentwicklern nicht unterschätzen.

Gruß
Werner

knivil

Sag ich doch. Wobei ich mir den orginal Post nochmal durchgelesen habe: Ist die exp-Funktion denn wirklich der Flaschenhals? Andere Optimierungen waeren vielleicht angebracht, indem man z.B. exp-Aufrufe einspart. Messen hilft!

It0101

Hmm ok, mit der original exp-funktion hatte ich das jetzt nicht verglichen

Ganz offensichtlich wird der exp dann wohl schon relativ optimal berechnet.
Dann muss der TE mal gucken, ob es noch irgendwo anders hakt.

Ich behalte meinen Algorithmus trotzdem im Hinterkopf. Für aufwändigere Berechnungen als exp kann ich den immernoch mal irgendwann gebrauchen

It0101

knivil schrieb:

PS: Den obigen Quelltext finde ich nicht schoen.

der sollte auch nicht schön sein, sondern nur grundlegend den Algorithmus darstellen.

Ist es da nicht die Idee, Schönheit vor Effizienz zu stellen?^^

It0101

bin ich Picasso ?!

Ich hatte nur mal eben 10min Zeit und hab den Kram zusammengefummelt... mehr nich

knivil schrieb:

Nachdenken Leute:
exp( x + y ) = exp( x ) * exp( y )

Diese Gleichung gilt nicht für IEEE Fließkommazahlen.

It0101

Die Gleichung ist Mathematik. Das gilt für alle Zahlen. Nur dass es in digitalen Schaltungen nicht mit unendlicher Genauigkeit passt. Aber fast niemand brauch mehr als 10 Stellen nach dem Komma...

Werner Salomon

Decimad schrieb:

Ist es da nicht die Idee, Schönheit vor Effizienz zu stellen?^^

Kommt drauf an, wer das tut.
Beginner: 1. Mein Code ist schnell 2. nix 3. schön, wenn er funktioniert
Guru: mache den Code 1. korrekt 2. schön und 3. schnell (in dieser Reihenfolge)

Mehr über schönen Code findet man hier.

Gruß
Werner