✔ Korrektes Potenzieren durch Divide&Conquer

[Cherrycoke]

Hallo,

ich möchte eine Funktion schreiben, die für eine Eingabe x und n, die Potenz x^n ausgibt. Dabei möchte ich den Divide&Conquer-Algorithmus einsetzen. Nun habe ich folgende Funktion geschrieben:

double potenz_dc( double x , int n )
{
	double potenz = x;
  
	if( n%2 == 0 ){
		if( (n/2) != 1 ){
			potenz = potenz_dc(x, n/2) * potenz_dc(x, n/2);
		}
		else{
			return x*x;
		}
	}
	else{
		n = n-1;
		if( (n/2) != 1 ){
			potenz = potenz_dc(x, n/2) * potenz_dc(x, n/2)*x;
		}
		else{
			return x*x;
		}
	}

	return potenz;
}

Nun soll ich noch die Zeit im Vergleich der "normalen" Methode berechnen und für die Zahlen 2^256, 2^512 und 2^1000 vergleichen.

Hier tun sich mir zwei Fragen auf:

1. Ist es richtig, dass der Divide&Conquer-A. nur bei kleinen Zahlen schneller ist?
2. Für die Zahl 2^1000 liefert der Algorithmus kein korrektes Ergebnis. Zielt die Fragestellung darauf ab, oder ist mein Algorithmus falsch?

Danke für eure Hilfe!

 

[Jellysheep]

Zu 1.: Das weiß ich nicht genau.
zu 2.: Du teilst ja n immer durch 2, solange es größer / gleich 1 ist. In deiner Funktion können also für n nur 2er-Potenzen (1, 2, 4, 8...) eingesetzt werden, weil der Algorythmus sonst nicht funktioniert.
Du kannst evtl überprüfen, ob 2 ein Teiler von n ist und wenn das nicht so ist, mit dem normalen Algorythmus potenzieren.

 

[Vereth]

1. Kommt darauf an, mit welchem anderen du ihn vergleichst. Außerdem arbeitest du rekursiv; iterative Implementierungen sind oft etwas schneller. Du kannst z.B. auch in einer Schleife das Bitmuster deines Exponenten n untersuchen.
2. Vermutlich wird ein Overflow durch Überschreiten des Wertebereichs von double erzeugt. Schau mal in deiner Doku nach, wie der Datentyp bei deinem Compiler definiert ist, und ob dir der Datentyp long double zur Verfügung steht.

 

[Jellysheep]

An einen Overflow hatte ich auch schon gedacht...
Hier mal ein Vorschlag (als Ersatz der Zeile 7 in deinem Code) in Pseudo-Code:

wenn n durch 2 teilbar:
   gebe potenz_dc(x, n/2)*potenz_dc(x, n/2) zurück;
sonst:
   a = nächster_teiler(x);
   gebe potenz_dc(potenz_normal(x, a), x/a) zurück;

Das sollte eigentlich so funktionieren.

// EDIT:
Overflow kann nicht sein, denn ein normales Double geht sogar bis 2^1023. (siehe hier)

 

[deepthroat]

Hi.

Dein Algorithmus ist einfach fehlerhaft. Was kommt denn z.B. bei 2^0 heraus? ;-]

Gruß

\edit: Außerdem erzeugst du einen baum-rekursiven Prozess: du rufst potenz_dc jedesmal doppelt mit den gleichen Argumenten auf. Das ist ziemlich unsinnig und rechenintensiv.

 

[Jellysheep]

\edit: Außerdem erzeugst du einen baum-rekursiven Prozess: du rufst potenz_dc jedesmal doppelt mit den gleichen Argumenten auf. Das ist ziemlich unsinnig und rechenintensiv.

Das ist ja der Sinn des Algorithmus'.
Er brauch große Rechenleistung, hat aber evtl. sehr flott ein Ergebnis.

mit den gleichen Argumenten

Das stimmt nicht ganz, er teilt jedes mal durch 2.

@Cherrycoke:
Wenn du 2^1000 eingibst, kommt theoretisch 2^1024 heraus.
Gib bitte mal 2^1024 ein und vergleiche die Ergebnisse.

 

[deepthroat]

Das ist ja der Sinn des Algorythmus'.

Du meinst der Sinn des Algorithmus (ohne y!) ist Ergebnisse doppelt zu berechnen? Und dadurch wird der schneller? ;-] Das würde mich wundern...

Das stimmt nicht ganz, er teilt jedes mal durch 2.

Ja, eben.

Er berechnet potenz_dc(x, n/ 2) und dann berechnet er - weils so schön war - nochmal potenz_dc(x, n/ 2).

Gruß

 

[Jellysheep]

Oh, da hst du Recht, das hab ich übersehen. :-(
Danke auch für den erkannten Tippfehler.
Jedenfalls funktionierts bei 10 und 512, bei 100 und 1000 aber nicht.
Wenn ich mir die ganzen n's ausgeben lasse, kommt bei 1000 z.B. 6 und 3 und 15 heraus, macht das Sinn?
Irgendwo ist noch der Wurm drin... ich glaube, das ist in der äußeren else-Schleife...

 

[deepthroat]

Oh, da hst du Recht, das hab ich übersehen. :-(
Danke auch für den erkannten Tippfehler.
Jedenfalls funktionierts bei 10 und 512, bei 100 und 1000 aber nicht.
Wenn ich mir die ganzen n's ausgeben lasse, kommt bei 1000 z.B. 6 und 3 und 15 heraus, macht das Sinn?
Irgendwo ist noch der Wurm drin... ich glaube, das ist in der äußeren else-Schleife...

2^3 funktioniert auch nicht. Und 2^0 schon gar nicht. Man sollte sich ruhig erstmal die trivialen Fällen anschauen bevor man Experimente mit größeren Eingaben macht.

Und eine if Anweisung ist bitte keine Schleife...

Grußo

 

[Cherrycoke]

Ersteinmal bedanke ich mich für die vielen Antworten, die ich nun versuche der Reihe nach abzuarbeiten.

Zu 1.: Das weiß ich nicht genau.
zu 2.: Du teilst ja n immer durch 2, solange es größer / gleich 1 ist. In deiner Funktion können also für n nur 2er-Potenzen (1, 2, 4, 8...) eingesetzt werden, weil der Algorythmus sonst nicht funktioniert.

Hmm, ich weiß nicht, ob ich dich richtig verstehe. Aber der Fall, dass n ungerade ist, wird ja in der äußeren if-Abfrage abgefangen. Sollte n ungerade sein, wird in Zeile 13 fortgesetzt. Hier wird dann x^n = (n-1)/2 *( n-1)/2 *x gerechnet. Dadurch ist alles wieder gerade.

1. Kommt darauf an, mit welchem anderen du ihn vergleichst. Außerdem arbeitest du rekursiv; iterative Implementierungen sind oft etwas schneller. Du kannst z.B. auch in einer Schleife das Bitmuster deines Exponenten n untersuchen.

Okay, stimmt auch mal wieder. :-D Ich möchte es mit der "intuitiven" Methode vergleichen. Also x^n = x * x^n-1 in eine Schleife, und durchgehen. Danke für den weiteren Hinweis, aber ich möchte die rekursive Variante vergleichen. Es ist praktich in der Aufgabenstellung festgelegt.

2. Vermutlich wird ein Overflow durch Überschreiten des Wertebereichs von double erzeugt. Schau mal in deiner Doku nach, wie der Datentyp bei deinem Compiler definiert ist, und ob dir der Datentyp long double zur Verfügung steht.

Ja, das habe ich mir auch schon gedacht. Allerdings verstehe ich nicht, warum meine zweite, "intuitive" Variante, auf das richtige Ergebnis kommt. Dann müsste diese doch genauso ein Überlauf erzeugen, oder?

An einen Overflow hatte ich auch schon gedacht...
Hier mal ein Vorschlag (als Ersatz der Zeile 7 in deinem Code) in Pseudo-Code:Code:

wenn n durch 2 teilbar:
   gebe potenz_dc(x, n/2)*potenz_dc(x, n/2) zurück;
sonst:
   a = nächster_teiler(x);
   gebe potenz_dc(potenz_normal(x, a), x/a) zurück;

Das sollte eigentlich so funktionieren.

In Pseudocode habe ich mir folgendes gedacht:

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? Wenn nicht probiere ich mal deine Variante aus.

Er berechnet potenz_dc(x, n/ 2) und dann berechnet er - weils so schön war - nochmal potenz_dc(x, n/ 2).

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?

Naja, ansonsten muss ich nochmal nachschauen, das der Algorithmus überhaupt erst für die trivialen Fälle funktioniert.