# Pow?



## Lukases2 (22. Apr 2015)

Sei M eine Menge und ° : M x M -> M eine assoziative Verknupfung auf M. Falls Sie ein konkretes
Beispiel haben wollen, konnen Sie sich also M = |N und a ° b := a (mal)  b vorstellen, wobei mit a (mal)  b hier die
gewohnliche 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 lasst 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 begrunden Sie, dass die geforderte Laufzeitschranke tatsachlich
eingehalten wird.
Wo wird die Assoziativitat von ° benotigt?

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 (22. Apr 2015)

° (n,m) ist hier einfach irgendeine assoziative Verknupfung, 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 (23. Apr 2015)

Ich habe mir hier mal einen Algorithmus ausgedacht:


Falls n=1 setze g auf a und beende die Rechnung. Andernfalls fahre mit Schritt 2 fort
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 (23. Apr 2015)

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)


----------

