✔ Korrektes Potenzieren durch Divide&Conquer

Hi.
Cherrycoke hat gesagt.:
In Pseudocode habe ich mir folgendes gedacht:
Code: 
wenn n durch 2 teilbar:
   gebe potenz_dc(x, n/2)*potenz_dc(x, n/2) zurück;
sonst:
  gebe potenz_dc(x, (n-1)/2)*potenz_dc(x, (n-1)/2)*x zurück;

Müsste so doch auch funktionieren. Oder steckt da schon ein Fehler drin?
Zum Vergrößern anklicken....
Hm. Wann terminiert denn der Algorithmus? ;-]
Cherrycoke hat gesagt.:
Hmm, klar! Also berechne ich potenz_dc(x, n/ 2) einmal und speicher es in eine Variable ab. Erst im nächsten Schritt multipliziere ich es mit sich selbst. Habe ich das richtig verstanden?
Zum Vergrößern anklicken....
Ja. :)
Cherrycoke hat gesagt.:
Naja, ansonsten muss ich nochmal nachschauen, das der Algorithmus überhaupt erst für die trivialen Fälle funktioniert. :(
Zum Vergrößern anklicken....
Das schöne an den Trivialfällen ist ja, das sie so schön einfach sind... ;)

Gruß
 
deepthroat hat gesagt.:
Hi.
Hm. Wann terminiert denn der Algorithmus? ;-]
Zum Vergrößern anklicken....

Verbesserte Variante:

Code: 
wenn n durch 2 teilbar:
   	gebe potenz_dc(x, n/2)*potenz_dc(x, n/2) zurück;
sonst:
	wenn n gleich 1:
		gebe x zurück;
	sonst:
		gebe potenz_dc(x, (n-1)/2)*potenz_dc(x, (n-1)/2)*x zurück;

Könnte man die so nehmen? Der Algorithmus terminiert nun, nachdem x zurückgegeben wird.
 
Cherrycoke hat gesagt.:
Verbesserte Variante:

Code: 
wenn n durch 2 teilbar:
   	gebe potenz_dc(x, n/2)*potenz_dc(x, n/2) zurück;
sonst:
	wenn n gleich 1:
		gebe x zurück;
	sonst:
		gebe potenz_dc(x, (n-1)/2)*potenz_dc(x, (n-1)/2)*x zurück;

Könnte man die so nehmen? Der Algorithmus terminiert nun, nachdem x zurückgegeben wird.
Zum Vergrößern anklicken....
Nein, der Algorithmus terminiert immer noch nicht für alle gültigen Eingaben.

Gruß
 
deepthroat hat gesagt.:
Nein, der Algorithmus terminiert immer noch nicht für alle gültigen Eingaben.

Gruß
Zum Vergrößern anklicken....

Code: 
wenn n durch 2 teilbar:
   	gebe potenz_dc(x, n/2)*potenz_dc(x, n/2) zurück;
sonst:
	wenn n gleich 0:
		gebe 1 zurück;
	wenn n gleich 1:
		gebe x zurück;
	sonst:
		gebe potenz_dc(x, (n-1)/2)*potenz_dc(x, (n-1)/2)*x zurück;

Und nun? So funktioniert es bei mir jedenfalls auf dem Blatt. Vielleicht soll ich noch dazu sagen, dass laut Aufgabenstellung der Exponent eine natürliche Zahl ist.
 
Cherrycoke hat gesagt.:
Code: 
wenn n durch 2 teilbar:
   	gebe potenz_dc(x, n/2)*potenz_dc(x, n/2) zurück;
sonst:
	wenn n gleich 0:
		gebe 1 zurück;
	wenn n gleich 1:
		gebe x zurück;
	sonst:
		gebe potenz_dc(x, (n-1)/2)*potenz_dc(x, (n-1)/2)*x zurück;

Und nun? So funktioniert es bei mir jedenfalls auf dem Blatt. Vielleicht soll ich noch dazu sagen, dass laut Aufgabenstellung der Exponent eine natürliche Zahl ist.
Zum Vergrößern anklicken....
n = 0 scheint auf deinem Blatt nicht durch 2 teilbar zu sein.. ;-]

Gruß
 
@Jellysheep: Ein Overflow KANN sein. C/C++ ist nicht Java, und double ist keine Klasse, sondern ein primitiver Datentyp. In C/C++ ist der Wertebereich von Zahlen stark implementierungsabhängig, und genaueres zum Wertebereich in C/C++ findest du hier.

Cherrycoke hat gesagt.:
Also x^n = x * x^n-1 in eine Schleife, und durchgehen.
Zum Vergrößern anklicken....

Eigentlich dachte ich mehr an so etwas:
C: 
#include <stdio.h>

double potenz ( double x, unsigned int n )
{
  double erg = 1;

  for ( ; n != 0; n >>= 1, x *= x )
  { if ( (n&1) == 1 ) erg *= x; }

  return erg;
}

int main()
{
  double erg;
  double x;
  unsigned int n;

  x = 2; n =    5; erg = potenz(x,n); printf("%g hoch %u: %g\n",x,n,erg);
  x = 7; n =    3; erg = potenz(x,n); printf("%g hoch %u: %f\n",x,n,erg);
  x = 9; n =    0; erg = potenz(x,n); printf("%g hoch %u: %f\n",x,n,erg);
  x = 0; n =    5; erg = potenz(x,n); printf("%g hoch %u: %f\n",x,n,erg);
  x = 0; n =    0; erg = potenz(x,n); printf("%g hoch %u: %f\n",x,n,erg);

  x = 2; n =   10; erg = potenz(x,n); printf("%g hoch %u: %gs\n",x,n,erg);
  x = 2; n =  100; erg = potenz(x,n); printf("%g hoch %u: %g\n",x,n,erg);
  x = 2; n = 1000; erg = potenz(x,n); printf("%g hoch %u: %g\n",x,n,erg);

  return 0;
}

Und 2^1000 ergibt bei meinem (alten) C/C++ - Compiler einen Overflow.

Hinweis: 0^0 = 1
 
@Cherrycoke:
Das sieht richtig aus, denke ich.

@Vereth:
Da hast du natürlich Recht.
2^1000 passt mei mir aber noch locker in ein double hinein (ca. 10^301, Wertebereich geht bis 10^308).
// EDIT: Bis 2^1023 geht in double bei mir rein, long double ist bei mir leider als double definiert. (WARUM?)


@Cherrycoke:
Ich denke, dein Fehler liegt in Zeile 19 des zuerst geposteten Codes:
C++: 
return x*x;
Wenn n%2==1 dann wird n zu n-1. Jetzt: Wenn n (bzw. n-1)/2 == 1 dann gebe x*x zurück.
Was fällt dir auf? n ist in dem Fall 3, du gibst aber x^2 zurück. :eek:
Lass mal die Überprüfung (ob x/2 == 1) weg und teste nochmal bei 2^1000. ;)

So, ich hab hier kurz eine Lösung zusammengeschrieben, es sind nur ein paar kleine Fallunterscheidungen drin:
C++: 
double potenz_dc(long double x , int n)
{
    long double potenz;
    if( n < 0 ){
        potenz = 1;
        potenz /= potenz_dc(x, -n);
    }else if( n == 0 ){
        potenz = 1;
    }else if( n == 0 ){
        potenz = x;
    }else if( n%2 == 0 ){
        potenz = potenz_dc(x, n/2);
        potenz *= potenz;
    }else{
        n = n-1;
        potenz = potenz_dc(x, n/2);
        potenz *= potenz;
        potenz *= x;
    }
    return potenz;
}

Ein Nachtrag zur Geschwindigkeit:
Für diesen Versuch
C++: 
    for(int j = 0; j<1000; j++){
        for(int i = 0; i<1024; i++){
            x = pow((double)2, i);
            //x = potenz_dc(2, i);
        }
    }
braucht pow() aus math.h knappe 350 ms, die eigene Variante dagegen knapp eine Sekunde.
Die "normale" Variante ist dort also ungefähr dreimal so schnell.
 
Ich danke euch allen für eure Hilfe! Der Vollständigkeit wegen gibt es hier noch mein Programm

C: 
double potenz_dc( double x , int n )
{
	double potenz = x, teilergebnis = 0;

  	//Wenn n durch 2 teilbaer
	if( (n%2) == 0 ){
		if( n == 0 ){
			return 1;
		}
		else{
			teilergebnis = potenz_dc(x, n/2);
			return (teilergebnis * teilergebnis);	
		}
	}
	else{
		//Wenn n gleich 1
		if( n == 1 ){
			return x;
		}
		else{
			teilergebnis = potenz_dc(x, (n-1)/2);
			return (teilergebnis*teilergebnis*x);
		}
	}
	
}
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück