Potenz Funktion mit Rekursion

Michael E.

Nein, er hat nichts verwechselt. Die richtige Lösung lässt sich zwar auch iterativ darstellen, aber es war nirgendwo die Rede davon, dass die rekursive Version schneller sein soll als die entsprechende iterative Version.

Als Tipp zum Algorithmus: Statt a^b = a * a^(b-1) könnte man sich ne andere Rekursionsformel suchen, vielleicht etwas in der Art a^b = (...)^2. Dazu solltest du ein altbekanntes Potenzgesetz verwenden (Potenzen werden multipliziert, indem man...).

Vicious Falcon

Ich habe das mal gegen eine schnell geschriebene Version von mir getestet.
Zunächst die Vergleichsfunktion

double mypow(double val,int exp)
{
	int i;
	if(!exp)
		return 1;
	for(i=1;i<exp;++i)
		val*=val;
	return val;
}

5 Maximaler Exponent
1		16
2		0
10 max exp
1       32
2       15
100 max exp
1       250
2       78
1000 max exp
1       2672
2       672
10000 max exp
1       28359
2       7235

Die Zeit ist jeweils in ms angegeben (und nein, 1 ist die rekursive Funktion). Erst kann sie noch halbwegs mithalten, bei steigendem Exponenten fällt sie jedoch immer weiter ab.
Du musst auch beachten, dass eine rekursive Funktion vom Compiler nicht inline erzeugt werden kann (okay, mit passenden pragmas geht es, aber nur bis zu einer sehr beschränkten Tiefe, die um 8 liegt).

Michael E.

Vicious Falcon: Nochmal: Es geht nicht darum, dass eine rekursive Variante schneller sein soll als eine äquivalente iterative Variante. Außerdem wäre der Test fairer, wenn du aus der Rekursion ne tail recursion machen würdest

Zeigst du mal bitte den ganzen Vergleichscode?

Vicious Falcon

Ich wollte ja auch nur die vorliegende Version gegen eine iterative testen. Den Code habe ich gar nicht mehr
Auf jeden Fall sah er in etwa so aus

const int num = 1000000; // in etwa
start = GetTickCount(); // WinAPI
for(i=0;i<num;++i)
{
  if(potenz(2.0,i%maxexp)==0.0) // Wegoptimieren verhindern
    puts("huch");
}
// GetTickCount() auswerten

Mit mypow genau so.
Edit: Ohje, die UN wollte ich mir doch abgewöhnen...

Man kann ja die Potenz aufteilen z.B.::
x⁸ = x⁴ * x⁴
x⁴ = x² * x²
x² = x * x

Das sind nur 3 statt 7 Multiplikationen.

minastaros

Michael E. schrieb:

Nochmal: Es geht nicht darum, dass eine rekursive Variante schneller sein soll als eine äquivalente iterative Variante.

Naja, das war schon Teil der Aufgabe (s. ganz oben):

Die Berechnung soll deutlich schneller erfolgen als durch b-maliges Mit-sichselbst-multiplizieren der Zahl a. Wir sollen zusätzlich begründen, warum die Funktion schneller arbeitet.

SG1

minastaros schrieb:

Michael E. schrieb:

Nochmal: Es geht nicht darum, dass eine rekursive Variante schneller sein soll als eine äquivalente iterative Variante.

Naja, das war schon Teil der Aufgabe (s. ganz oben):

Die Berechnung soll deutlich schneller erfolgen als durch b-maliges Mit-sichselbst-multiplizieren der Zahl a. Wir sollen zusätzlich begründen, warum die Funktion schneller arbeitet.

Nein, eben nicht. Die Aufgabenstellung fordert "schneller als b-maliges mit sich selber multiplizieren" nicht "schneller als iterativ".

Ist leider nur auf English:
http://en.wikipedia.org/wiki/Exponentiation#Efficiently_computing_an_integer_power

Dein erstes Beispiel ist doch rekursives b-maliges mit sich selber multiplizieren.
Du suchst jetzt eine rekursiven Algorithmus der schneller ist als deiner.

Das bringt meiner Meinung nach erst etwas bei großen Exponenten.
Dabei muss man Bedenken das eine Fließkommaoperation i.A. langsamer ist als eine Integer-Operation.
Deine Basis ist Fließkomma, der Exponent ist Integer. Deshalb ein paar mehr Operationen am Exponent als an der Basis

Vicious Falcon

SG1 schrieb:

Die Aufgabenstellung fordert "schneller als b-maliges mit sich selber multiplizieren" nicht "schneller als iterativ".

Richtig, das habe ich im ersten Moment nicht gesehen, blöd von mir.

_--

@edit okay das war alles mist hier mal die neue variante, allerdings immernoch mit 3 parametern

int rec_pow_ex(int res,int x,int c){
	return c > 0 ? rec_pow_ex(((c % 2) == 1 ? res * x : res),x*x,c/2) : res;
}

int rec_pow(int x,int c){
	return rec_pow_ex(1,x,c);
}

knivil

Michael E. schrieb:

Außerdem wäre der Test fairer, wenn du aus der Rekursion ne tail recursion machen würdest

Sollte der gcc in diesem Fall automatisch hinkriegen. Es handelt sich hierbei um eine Faltung von rechts, bei natuerliche Zahlen und Multiplikation kann sie durch eine Faltung von links ersetzt werden, Faltung von links ist endrekursiv, diese kann leicht in einen Loop verwandelt werden.

Btw.: Code und Compileroptionen bitte bei vergleichen posten !!!1111elf

int fac_rec(int x, int n) {
»···return n ? x*fac_rec(x,n-1) : 1;
}

int fac_ite(int x, int n) {
»···int r = 1;
»···while (n) { r*=x; --n;}
»···return r;
}

g++ mit -O3 erzeugt fuer beide Funktionen identischen Assemblercode. Uebrigens, der Stack ist dazu da, belastet zu werden ...

Hier die andere Loesung. Bitte nicht abschreiben, da man dir wahrscheinlich nicht glauben wird, dass du sie selbst geschrieben hast: (ok, ist auch falsch, da es immernoch genauso viele Multiplikationen benoetigt. DIe Rekursionstiefe ist aber nur O(log n) anstatt n, auch kann man das eine Ergebnis von fac_log zwischenspeichern, dann hat man wieder O(log n) Multiplikationen).

int fac_log(int x, int n) {
»···return n ? ((n%2) ? x : 1) * fac_log(x,n/2) * fac_log(x,n/2) : 1 ;
}

Bei dieser Variante wird die Rekursion auch komplett wegoptimiert.

Mit y/2 kann der Compiler viel besser entscheiden, ob er y>>1 macht oder das div-Rechenwerk benutzt. Mit y>>1 ist auch voellig unklar, was der Programmierer beabsichtigt. Gleiches gilt fuer y&1 .

_--

okay also hier mal eine mit 2, dacht schon ich brings nicht mehr zam. hab aber auch bischen beim knivil gespickt, hehe

int rec_pow(int x,int c){
	return c ? (c % 2 ? x : 1) * rec_pow(x*x,c/2) : 1;
}

Prima!

Wie viel ist das den jetzt schneller als die
a) Standard rekursive Methode x * x^n-1
b) iterative Methode

knivil

rec_pow(x*x,c/2)

Netter Trick, ganz ohne Hilfsvariable

_--

DirkB schrieb:

Prima!

Wie viel ist das den jetzt schneller als die
a) Standard rekursive Methode x * x^n-1
b) iterative Methode

iterative und recursive sollten gleich schnell sein, das andere weiß ich nicht

inline int sq(int x) { return x*x; }
int pow(int a, int b) { return !b ? 1 : (b % 2 ? a * pow(a, b - 1) : sq(pow(a, b / 2))); }

Michael E.

_-- schrieb:

okay also hier mal eine mit 2, dacht schon ich brings nicht mehr zam. hab aber auch bischen beim knivil gespickt, hehe
int rec_pow(int x,int c){
	return c ? (c % 2 ? x : 1) * rec_pow(x*x,c/2) : 1;
}

Einen kleinen Makel hat diese Lösung: Wenn du beim Schritt rec_pow(x, 1) angekommen bist, könntest du einfach x zurückgeben. Allerdings berechnest du x*rec_pow(x*x, 0), wobei x*x größer als das Endergebnis ist und somit bei eigentlich berechenbarer Eingabe zu einem Überlauf führen kann. Diesen verwirfst du allerdings direkt, da dich x bei c=0 nicht interessiert, sodass es keinen Einfluss auf das Ergebnis hat.

knivil

Wie viel ist das den jetzt schneller

Probiere es doch erstmal selber herauszufinfen. Zaehle die Anzahl der Multiplikationen beider Varianten und gib mal 'nen Tipp ab. Das hilft dir auch den Code zu verstehen.

minastaros

SG1 schrieb:

Nein, eben nicht. Die Aufgabenstellung fordert "schneller als b-maliges mit sich selber multiplizieren" nicht "schneller als iterativ".

Alles klar, mein Fehler. Ich hatte das "Mit-sich-selbst-muliplizieren" bereits als "Iteration" verstanden im Sinne von Mehrmaligem-Anwenden-der-gleichen-Rechenoperation. Habe mir die Definition von "Iteration" nochmal angesehen, da geht es ja zusätzlich um die schnelle Annäherung an das Ergebnis. Meine Mathe-Semester sind halt schon ne Weile her... Danke für die Auffrischung!

Vielen Dankf für die zahlreichen Kommentare. Hätte nicht gedacht, dass ich so schnell hier Tips bekomme!

Hier nochmal die genaue Aufgabenstellung:
Schreiben Sie eine C-Funktion, die für gegebene Zahlen a Element R, Element 2 N, die Potenz a^b rekursiv berechnet. Die Berechnung sollte deutlich schneller erfolgen als durch b-maliges Mit-sichselbst-multiplizieren der Zahl a. BegrÜunden Sie, warum Ihre Funktion schneller arbeitet.
Hinweis: Untersuchen Sie b auf Teilbarkeit durch 2.

Habe mir Eure Beiträge jetzt mehrmals durchgelesen und bin mir leider immer noch nicht sicher, welche Lösung die Richtige ist. Kann ich meine Funktion so nicht stehenlassen?