N-th Power



  • Einen unsigned int als Basis, einen size_t als Exponenten und dann einen int zurückgeben passt imho nicht.

    Wie die einzelnen Werte gespeichert sind (std::vector, std::array, std::deque oder C-Array) sollte egal sein, daher würde ich bei getNthPower auch zwei Iteratoren oder einen Zeiger und die Anzahl entgegennehmen.



  • 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 gleichintnehmen 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 axay=ax+ya^x \cdot a^y = a^{x+y} kann man sich auf jeden Fall mit etwas Tüfteln einen O(logn)\mathcal{O}(\log n)-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)
    {
        ...
    }
    


  • This post is deleted!


  • This post is deleted!


  • @zeropage
    @Finnegan

    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}a​x​​⋅a​y​​=a​x+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_squaring

    Ich 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 [...] umformulieren

    Brrrr. 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 "Liegt N im Vector?" und nicht "Hat der Vector höchstens N (+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. "Liegt N 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 axay=ax+ya^x \cdot a^y = a^{x+y} kann man sich auf jeden Fall mit etwas Tüfteln einen O(logn)\mathcal{O}(\log n)-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 2642^{64} darstellen, d.h. es gibt maximal 64 Multiplikationen – in der Regel deutlich weniger, weil sonst es zum Integerüberlauf kommt. Nehmen wir als Beispiel 3373^{37}. Die 3737 lässt sich in 37=32+4+1=25+22+137=32+4+1=2^{5}+2^{2}+1 zerlegen. Besser wäre es aber 37=224+22+137=2\cdot 2^{4}+{2^{2}}+1 zu zerlegen. Wir rechnen somit t1=33t_1=3\cdot3, m2=t1t1m_2=t_1\cdot t_1, t2=m2m2t_2=m_2\cdot m_2, m5=m2m23m_5=m_2\cdot m_2 \cdot 3. Das Endergebnis ist dann 3m5m23\cdot m_5\cdot m_2. Dazu waren dann 7 Multiplikationen notwendig. Wie viel Aufwand ist es nun, dass den Exponenten vorher sinnvoll zu verlegen und dann entsprechend zu mutliplizieren?



  • @Finnegan

    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;    
    }
    

Log in to reply