Pottenzieren

Dummie

Ein weiterer Kandidat:

#include <iostream>

typedef long PowNumType;

inline PowNumType NewSq(PowNumType a)
{
	return a * a;
}

PowNumType NewPow(PowNumType a, PowNumType b)
{
	if (b == 0)
	{
		return 1;
	}
	else if (b == 1)
	{
		return a;
	}
	else if (b % 2 == 0)
	{
		return NewSq(NewPow(a, b / 2));
	}

	return a * NewPow(a, b - 1);
}

int main()
{
	std::cout << NewPow(14, 8) << "\n";

	return 0;
}

Für größere Zahlen müsste das sehr gut performen. Aber kann gerade keine konkrete Vergleichszeit messen.

volkard

Dummie schrieb:

Für größere Zahlen müsste das es sehr gut performen. Aber kann gerade keine konkrete Vergleichszeit messen.

Warum soll das besser als my_pow unskilled 09 Jun 2010 00:22 sein?

Dummie

volkard schrieb:

Dummie schrieb:

Für größere Zahlen müsste das es sehr gut performen. Aber kann gerade keine konkrete Vergleichszeit messen.

Warum soll das besser als my_pow unskilled 09 Jun 2010 00:22 sein?

Ich hatte den Algorithmus irgendwo mal aufgeschnappt und hatte einfach gedacht, dass er vielleicht mithalten kann.
Aber die Begeisterung ist wohl nicht so groß

otze

SeppJ schrieb:

Es wird nach jedem Durchgang exp durch zwei geteilt bis exp Null ist, daher werden ~log_2(exp) Durchläufe gemacht.

Niemals vergessen: Es gilt nicht der eingegebene Zahlenwert für die Laufzeitberechnung, sondern die Größe der Eingabe, also wird in Bits gemessen!

Um ganz genau zu sein ist Variante 1 deswegen O(2^n). Bei einer Eingabe der Größe n-Bits braucht der Algorithmus 2^n Rechenschritte. Der andere Algorithmus hingegen ist O(n), da er bei jedem Schritt exakt 1 Bit abarbeitet.

SeppJ

otze schrieb:

SeppJ schrieb:

Es wird nach jedem Durchgang exp durch zwei geteilt bis exp Null ist, daher werden ~log_2(exp) Durchläufe gemacht.

Niemals vergessen: Es gilt nicht der eingegebene Zahlenwert für die Laufzeitberechnung, sondern die Größe der Eingabe, also wird in Bits gemessen!

Um ganz genau zu sein ist Variante 1 deswegen O(2^n). Bei einer Eingabe der Größe n-Bits braucht der Algorithmus 2^n Rechenschritte. Der andere Algorithmus hingegen ist O(n), da er bei jedem Schritt exakt 1 Bit abarbeitet.

Tatsächlich? Mal wieder was gelernt.

Du hast bei der Analyse jedoch Variante 1 und 2 verwechselt.

volkard

otze schrieb:

Niemals vergessen: Es gilt nicht der eingegebene Zahlenwert für die Laufzeitberechnung, sondern die Größe der Eingabe, also wird in Bits gemessen!

Es gilt die Größe für die Laufzeitberechnung, die man angibt. Die Größe der Eingabe in Bits ist da nicht unüblich. Kann sein, muß aber nicht.

otze schrieb:

Niemals vergessen: Es gilt nicht der eingegebene Zahlenwert für die Laufzeitberechnung, sondern die Größe der Eingabe, also wird in Bits gemessen!

Das kann man machen, wie man will. Du kannst die Laufzeit in Abhängigkeit der Eingabelänge angeben oder einfach in Abhängigkeit des Wert des Exponenten. Hauptsache, es ist klar, was gemeint ist.

Nur für den Fall, dass das noch nicht erwähnt worden ist: Der eine Algorithmus heißt "square and multiply".

kk

DocShoe

Ich möchte an dieser Stelle mal einwerfen, dass der Exponent auch negativ sein darf...

SeppJ

DocShoe schrieb:

Ich möchte an dieser Stelle mal einwerfen, dass der Exponent auch negativ sein darf...

Ach, dann kann man auch noch kommen, dass jemand komplexe Exponenten will. Oder Matrixexponenten. Oder einen Tensor 15-ter Stufe über den Quaternionen. Mit einer hyperkomplexen Basis.

Lassen wir das Problem doch erstmal einfach.

unskilled

DocShoe schrieb:

Ich möchte an dieser Stelle mal einwerfen, dass der Exponent auch negativ sein darf...

ich hab extra unsigned davor geschrieben, um deutlich zu machen, dass er das nicht sein kann(darf^^) ;P

bb