N-th Power
-
@Finnegan sagte in N-th Power:
Die frage ist ja "Liegt N im Vector?
So wie der Code dasteht eher "liegt N ausserhalb vom Vektor" bzw. "ist N zu gross".
Aber ja, kann man ruhig so schreiben.Verwirrend finde ich dagegen das grosse N. Da hätte ich etwas konstantes erwartet.
-
@hustbaer sagte in N-th Power:
Verwirrend finde ich dagegen das grosse N. Da hätte ich etwas konstantes erwartet.
Oh ja, autsch, das ist ja garkein Template
-
@Finnegan sagte in N-th Power:
Wenn du Wert auf Code mit Sahnehäubchen legst, dann könntest du hier noch ein paar Schleifendurchläufe einsparen. Ein
result *= result;
verdoppelt z.B. den Exponenten in einem Schritt, statt ihn immer nur um 1 zu erhöhen. Mit der Regel kann man sich auf jeden Fall mit etwas Tüfteln einen -Algorithmus für die Integer-Potenz stricken.Man sollte dabei aber nicht vergessen, dass man vorher eine sinnvolle Zerlegung des Exponenten finden muss, und da verbraucht man auch wieder Zeit für. Bei 64Bit Zahlen kann man maximal die Zahl darstellen, d.h. es gibt maximal 64 Multiplikationen – in der Regel deutlich weniger, weil sonst es zum Integerüberlauf kommt. Nehmen wir als Beispiel . Die lässt sich in zerlegen. Besser wäre es aber zu zerlegen. Wir rechnen somit , , , . Das Endergebnis ist dann . Dazu waren dann 7 Multiplikationen notwendig. Wie viel Aufwand ist es nun, den Exponenten vorher sinnvoll zu verlegen und dann entsprechend zu multiplizieren?
-
Der macht eigentlich unterm Strich dasselbe. Die ganzen / 2 und * 2 kann man auch als Bit-Operationen und die Endrekursion als fortgesetzte Schleife umformulieren, dann landet man ist man wahrscheinlich bei der Binären Exponentiation.
Hmm, nicht ganz. Berechne ich 2^255 (als double) so komme ich bei deinem Algo auf 36 Multiplikationen und bei der anderen Variante auf 16 Multiplikationen.
#include <cstdlib> #include <cstdio> #include <cmath> double Pow(double Value, unsigned char Exp, int& Counter) { double z = 1.0; double b = Value; unsigned char x = Exp; while (x != 0) { if (x & 1) { Counter++; z *= b; } Counter++; b = b * b; x = x >> 1; } return z; } double PowFinn(double x, int n, int& Counter) // Variante von ipow { if (n == 0) return 1; double result = x; int i = 1; for (; i <= n / 2; i *= 2) { result *= result; Counter++; } Counter++; return result * PowFinn(x, n - i, Counter); } int main(int argc, char** argv) { int Counter1 = 0; int Counter2 = 0; double r1; double r2; r1 = Pow(2, 255, Counter1); printf("Variante 1:\n\t%e\n\t# Mult: %i\n", r1, Counter1); r2 = PowFinn(2, 255, Counter2); printf("Variante 2:\n\t%e\n\t# Mult: %i\n", r2, Counter2); printf("Differenz: %f\n", r1 - r2); return 0; }
-
@john-0 @Quiche-Lorraine Ja, da hab ich nicht gross drüber nachgedacht und den Algo einfach so runtergeschreiben. Der macht da den Greedy-Ansatz - immer bis zum größten Exponenten der
<=
Rest-Exponent ist. Die Sache mit ist interessant, das schau ich mir die Tage nochmal genauer an. Das möchte ich schon wissen, warum der (wohl aus gutem Grund) etablierte Algo hier so viel besser abschneidet (ich weiss schon, dass "greedy" meist nicht zum optimalen Ergebnis führt).Was die optimale Zerlegung zur Minimierung der Multiplikationen angeht, so riecht das gerade auf den ersten Blick ein wenig nach Rucksackproblem. Könnte also gut sein, dass es sich nicht wirklich lohnt, da ein Optimum zu finden. Aber das muss ich mir auch nochmal in Ruhe zu Gemüte führen. Habe abe das Gefühl, dass der etablierte Algo wohl der beste Kompromiss ist, sonst wäre er eben nicht so "etabliert"
-
Noch zwei kleine Nachfragen zum Verständnis.
@hustbaer sagte in N-th Power:
@Finnegan sagte in N-th Power:
Die frage ist ja "Liegt N im Vector?
So wie der Code dasteht eher "liegt N ausserhalb vom Vektor" bzw. "ist N zu gross".
Ist doch richtig so, wenn die Aufgabe lautetet
If N is outside of the array, then return -1
?
@hustbaer sagte in N-th Power:
Verwirrend finde ich dagegen das grosse N. Da hätte ich etwas konstantes erwartet.
Das ist eine Sache, die ich eh noch nachfragen wollte. Sind Großbuchstaben nicht grundsätzlich Konstanten? Oder ist N nur in der Aufgabe groß geschrieben zum besseren Lesen?
-
@zeropage sagte in N-th Power:
Noch zwei kleine Nachfragen zum Verständnis.
@hustbaer sagte in N-th Power:@Finnegan sagte in N-th Power:
Die frage ist ja "Liegt N im Vector?
So wie der Code dasteht eher "liegt N ausserhalb vom Vektor" bzw. "ist N zu gross".
Ist doch richtig so, wenn die Aufgabe lautetet
Ich hab auch nicht behauptet dass es falsch wäre.
Trotzdem steht da nicht "liegt N im Vector?" sondern "liegt N ausserhalb vom Vektor?"
Dass das nicht das selbe ist, verstehst du hoffentlich.Das ist eine Sache, die ich eh noch nachfragen wollte. Sind Großbuchstaben nicht grundsätzlich Konstanten? Oder ist N nur in der Aufgabe groß geschrieben zum besseren Lesen?
In welchem Kontext sollen Großbuchstaben grundsätzlich Konstanten sein? In C und C++ auf jeden Fall nicht.
-
@hustbaer sagte in N-th Power:
Ich hab auch nicht behauptet dass es falsch wäre.
Trotzdem steht da nicht "liegt N im Vector?" sondern "liegt N ausserhalb vom Vektor?"
Dass das nicht das selbe ist, verstehst du hoffentlich.Hoffentlich. Liegt N im Vector
if (N < vec.size())
Liegt N außerhalb des Vector
if (N >= vec.size())
-
@hustbaer sagte in N-th Power:
In welchem Kontext sollen Großbuchstaben grundsätzlich Konstanten sein? In C und C++ auf jeden Fall nicht.
Ok. Dachte, weil der Autor N großgeschrieben hat, hat das seine Bewandnis, in diesem Fall soll es dann eine Konstante sein. Und dann dachte ich, es ist vielleicht eine Regel. Und weil auch im Thread etwas über konstantes stand, wollte ich lieber nachfragen.
-
@zeropage sagte in N-th Power:
Und dann dachte ich, es ist vielleicht eine Regel.
Es ist in C und C++ relativ üblich dass etwas was mit nur Grossbuchstaben geschrieben wird konstant ist.
Aber Regel in dem Sinn gibt es keine - zumindest keine allgemeingültige. In diversen Coding-Guidelines verschiedener Projekte/Firmen wird es sicher massig solche Regeln geben. Aber die sind ja nicht allgemein bindend.
-
Alles klar, danke.
(Die Feinheiten des schriftlichen Ausdrucks )