Potenz Funktion mit Rekursion

Hallo,
wir sollen eine C-Funktion schreiben, womit die Potenz zweier Zahlen (Basis = a und Exponent = b) REKURSIV berechnet wird. 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.

Mein Programm:

#include<stdio.h>

/* Funktion potenz wird deklariert */
double potenz(double basis, int exponent);

/* Globale Variablen deklarieren */
double basis;
int exponent;

/* main Funktion */
int main(void)
{
	printf("Geben Sie eine reelle Zahl für die Basis ein: \n");
	scanf("%lf" , &basis);
	printf("Geben Sie eine natürliche Zahl für den Exponeneten ein: \n");
	scanf("%d" , &exponent);

	printf("%lf ^ %d = %lf" , basis, exponent, potenz(basis, exponent));

	return 0;
}

/* Funktion potenz wird definiert */
double potenz(double basis, int exponent)
{
	if (exponent == 0)
		return 1;
	else
		return potenz(basis, --exponent) * basis;
}

Ich bin mir nicht sicher, ob ich es nicht doch durch b-maliges Mit-sichselbst-multiplizieren der Zahl a gelöst habe?!? Außerdem fehlt mir die Erklärung, warum mein Programm so schneller arbeitet.
Vielen Dank

Wutz

Du hast das Problem durch Rekursion gelöst. Davon, dass die Rekursion keine einfache Multiplikation benutzen darf, war ja wohl keine Rede.
Statt --exponent sollte exponent-1 etwas schneller sein.
Dass hier die Rekursion schneller sein soll als keine Rekursion halte ich für ein Gerücht, die Rekursion belastet zusätzlich den Stack, was mehr Zeit kostet.
Außerdem ist hierbei die Gefahr des Stacküberlaufs gegeben.

mngbd

imanxxl schrieb:

Hallo,
wir sollen eine C-Funktion schreiben, womit die Potenz zweier Zahlen (Basis = a und Exponent = b) REKURSIV berechnet wird. Die Berechnung soll deutlich schneller erfolgen als durch b-maliges Mit-sichselbst-multiplizieren der Zahl a.

Hast du da sicher nichts verwechselt? Warum sollte eine Iteration schneller sein, wenn sie über rekursive Aufrufe erledigt wird?

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.