Pow?

[Lukases2]

Sei M eine Menge und ° : M x M -> M eine assoziative Verknupfung auf M. Falls Sie ein konkretes
Beispiel haben wollen, konnen Sie sich also M = |N und a ° b := a (mal)
b vorstellen, wobei mit a (mal)
b hier die
gewohnliche Multiplikation bezeichnet wird.
Sei n (element) |N und a (element) M. Wir definieren pow(a; n) durch
pow(a; n) := a ° ... ° a (n-mal)
In dem obigen Beispiel von M = N gilt also: pow(a; n) = a^n.
Offensichtlich lasst sich pow(a; n) durch einen naiven Algorithmus in n-Schritten berechnen, wenn eine
Anwendung von ° als ein Schritt gilt.
Entwickeln Sie einen Algorithmus in Pseudocode, der pow(a; 2^m) in m Schritten berechnet. Zeigen Sie
die Korrektheit Ihres Algorithmus und begrunden Sie, dass die geforderte Laufzeitschranke tatsachlich
eingehalten wird.
Wo wird die Assoziativitat von ° benotigt?

Was mich an der Aufgabe stört ist dieses "pow(a; 2^m) in m Schritten" Was ist damit gemeint? Ich dachte pow(a;n) soll 2^n bedeuten? Kann mit das jemand erklären?

Weiterhin habe ich eine Methode geschrieben, die eben pow berechnet:

public int pow(int base, int exp){
		int sol = 1;
		while(exp>0){
			sol *= base;
			exp -= 1;
		}
		return sol;
	}

Die gilt es ja jetzt als Pseudocode aufzuschreiben. Das habe ich so richtig verstanden, oder?

 

[stg]

° (n,m) ist hier einfach irgendeine assoziative Verknupfung, das Beispiel mit der Multiplikation dient nur zur Veranschaulichung.

Es gilt pow(a; n) := pow(a; n-1) ° a. Wie man leicht sieht und ja schon angemerkt wurde, kannst du pow(a; n) somit in n Schritt berechnen.

Nun is klar, dass du pow(a; 2^m) in 2^m Schritten berechnen kannst. Es geht aber deutlich besser, nämlich sogar in m Schritten. Dazu musst du eigentlich nur einsehen, dass pow(a, 2^m) = pow(a; 2^(m-1) ) ° pow(a; 2^(m-1) ) gilt.

Bezogen auf das Beispiel mit der Multiplikation:
Willst du etwa 2^8 berechnen, dann kannst du das in 8 Schritten machen, indem du die 1 acht mal mit der 2 Multiplizierst.
Jetzt gilt aber 2^8=2^(2^3). Du kannst das Ergebnis nun also auch in 3 Schritten berechnen, indem du rechnest:
2*2 = 4
4*4 = 16
16*16 = 256

Du sollst das nun nur ganz allgemein für eine beliebige assoziative Verknüfung formulieren.

 

[Lukases2]

Ich habe mir hier mal einen Algorithmus ausgedacht:

1. Falls n=1 setze g auf a und beende die Rechnung. Andernfalls fahre mit Schritt 2 fort
2. Falls n>1 vermindere n um 1 und setze a = a ° a und führe Schritt 1 durch. Andernfalls führe Schritt 2 durch

wobei g die Lösung sein soll. Damit wäre ich jetzt hier angekommen:

Es gilt pow(a; n) := pow(a; n-1) ° a. Wie man leicht sieht und ja schon angemerkt wurde, kannst du pow(a; n) somit in n Schritt berechnen.

Nun is klar, dass du pow(a; 2^m) in 2^m Schritten berechnen kannst. Es geht aber deutlich besser, nämlich sogar in m Schritten. Dazu musst du eigentlich nur einsehen, dass pow(a, 2^m) = pow(a; 2^(m-1) ) ° pow(a; 2^(m-1) ) gilt.

Ich verstehe zwar die einzelnen Teile von dem was du gesagt hast, aber nicht wieso ich das jetzt in m Schritten berechnen kann. Um an m zu kommen, muss ich ja n in eine Zweier-potenz umwandeln, d.h. m = log_2(n)?

 

[stg]

Du musst m nirgends ausrechnen. Was du zeigen sollst ist im Grunde in anderen Worten folgendes:

1. Für eine beliebige Verknüpfung ° lässt sich pow(a; n) (so wie obendefiniert) in n Schritten berechnen.
2. Ist die Verknüpfung ° assoziativ, so lässt sich pow(a; n) in log(n) Schritten berechnen.

Was soll dein Algorithmus denn nun berechnen? Ich fürchte fast, dass er was anderes macht, als du eigentlich haben willst. Wenn du einen Algorithmus formulierst, so solltest du auch immer dazu schreiben, was du für Eingabewerte hast (und was diese bedeuten), und was du für Ausgabewerte hast (und was diese bedeuten)