N-th Power
-
Kannst Du ein Beispiel geben? Ich habe das extra so gemacht, das es oben passt.
int getNthPower(const std::vector<unsigned int>& vec, const std::size_t N) { if (N >= vec.size()) return -1; else return (int)std::pow(vec[N], N); //oder return nPow(vec[N], N); }
-
@yahendrik sagte in N-th Power:
daher würde ich bei
getNthPower
auch zwei Iteratoren oder einen Zeiger und die Anzahl entgegennehmen.Ups, jetzt erst gesehen.
Jopp, nur wär dann die Aufgabe nicht mehr so einfach gewesen und ich wäre erst gar nicht drauf aufmerksam geworden. Außerdem hätte mir man das in die Aufgabe reinschreiben sollen, damit ich es so mache.
Aber gut, es stand auch nicht drin, mach es so einfach wie möglich.
-
@zeropage Nein, das war mein Fehler, es war nicht eindeutig und daher habe ich es editiert.
-
Davor hatte ich mir überlegt, ob ich dann überall gleich
int
nehmen sollte, aber spätestens beim Vergleich N mit vec.size() hätte es die erste Warnung gegeben.Außerdem hatte ich geglaubt, die Anforderung bei dieser Aufgabe wäre es, positive und nicht-negative Zahlen abzubilden.
-
@zeropage sagte in N-th Power:
Das pow würde ich dann so machen:
int nPow(unsigned int v, const std::size_t N) { int result = 1; for (std::size_t i = 0; i < N; ++i) result *= v; return result; }
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.Ausserdem würde ich empfehlen, für diese Funktion nur einen einzigen Datentypen zu verwenden. 3 verschiedene Typen für Rückgabewert und Parameter ist für so eine grundlegende Funktion etwas chaotisch. Wenn du nicht wirklich weisst, welchen Typen du nehmen willst, dann machs generisch und entscheide dich später:
// C++14 #include <type_traits> template <typename T> std::enable_if_t<std::is_integral<T>::value, T> nPow(T v, T N) { ... } // C++20 #include <concepts> template <std::integral T> T nPow(T v, T N) { ... }
-
Dieser Beitrag wurde gelöscht!
-
Dieser Beitrag wurde gelöscht!
-
Ein result *= result; verdoppelt z.B. den Exponenten in einem Schritt, statt ihn immer nur um 1 zu erhöhen. Mit der Regel ax⋅ay=ax+ya^x \cdot a^y = a^{x+y}ax⋅ay=ax+y kann man sich auf jeden Fall mit etwas Tüfteln einen O(logn)\mathcal{O}(\log n)O(logn)-Algorithmus für die Integer-Potenz stricken.
Hierfür kenne ich die binäre Exponentiation.
https://de.wikipedia.org/wiki/Binäre_Exponentiation
https://en.wikipedia.org/wiki/Exponentiation_by_squaringIch habe diese mal im Bereich von GNSS / GPS eingesetzt, kenne diese aber durch einen Kryptographie Kurs.
-
@Quiche-Lorraine sagte in N-th Power:
Hierfür kenne ich die binäre Exponentiation.
Ja, da gab es was, ich erinnere mich. Ich wollte es nicht direkt posten um @zeropage die Möglichkeit zu geben selbst drauf zu kommen, aber ich hatte mir gestern das hier überlegt:
int ipow(int x, int n) { if (n == 0) return 1; int result = x; int i = 1; for (; i <= n / 2; i *= 2) result *= result; return result * ipow(x, n - i); }
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.
-
@Finnegan sagte in N-th Power:
Die ganzen
/ 2
und* 2
kann man auch als Bit-Operationen [...] umformulierenBrrrr. Schauder.
-
@zeropage sagte in N-th Power:
Das hätte mich jetzt aber interessiert
Ja, weil's so blöd dasteht:
@zeropage sagte in N-th Power:
if (N >= vec.size())
da muss man (ich zumindest) nachdenken. Vorschlag:
if (vec.size() <= N)
Aber vielleicht liegt es auch nur an mir.
@others: Overflow check?? Anyone??
-
@Swordfish Finde ich schon okay das
N
auf der linken Seite. Die frage ist ja "LiegtN
im Vector?" und nicht "Hat der Vector höchstensN
(+1) Elemente?" ... danach entscheide zumindest ich was links und was rechts steht.
-
@Finnegan Ich stelle mir das optisch vor. Nimm einen Zahlenstrahl:
+---------------------------> | | vec.size() | | N
aber wie gesagt:
@Swordfish sagte in N-th Power:
Aber vielleicht liegt es auch nur an mir.
-
@Swordfish Hehe... habs grad auch verschnöselt. Die Frage hier ist "Liegt
N
außerhalb des Vector?". Kann man so machen, aber ich hätte wohl eher!(N < vec.size())
geschrieben. "LiegtN
nicht im Vector?"
-
@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?