Potenz Funktion mit Rekursion
-
@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); }
-
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. Mity>>1
ist auch voellig unklar, was der Programmierer beabsichtigt. Gleiches gilt fuery&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 * xn-1
b) iterative Methode
-
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 * xn-1
b) iterative Methodeiterative 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))); }
-
_-- 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.
-
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.
-
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?
-
imanxxl schrieb:
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?
Sollen wir dir jetzt erlauben, faul zu sein? Nein, deine Funktion aus dem ersten Post ist keine Loesung der Aufgabenstellung. Wo beruecksichts du in deiner Funktion die Teilbarkeit von b durch 2?
-
Das x sollte aber ruhig ein double sein.
Untersuchen Sie b auf Teilbarkeit durch 2.
Aber genau das macht doch die Funktion von _--
Wenn du dir noch mal den englischen Wikipedia-Artikel zu Potenzen durchliest, geht es genau darum, die Teilbarkeit durch 2 auszunutzen.
-
Und wenn du dir meinen Beitrag durchlesen magst, ging es mir nicht um die von __--. Ich habe selbst die Vorlage dafuer geliefert ...
-
Schau dir "Divide and Conquer" an und dann weißt du warum es schneller ist.