wake-up-neo.com

Der effizienteste Weg zum Implementieren einer auf Integer basierenden Potenzfunktion (int, int)

Was ist der effizienteste Weg, eine Ganzzahl auf die Potenz einer anderen Ganzzahl in C zu erhöhen?

// 2^3
pow(2,3) == 8

// 5^5
pow(5,5) == 3125
220
Doug T.

Potenzierung durch Quadrieren.

int ipow(int base, int exp)
{
    int result = 1;
    for (;;)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        if (!exp)
            break;
        base *= base;
    }

    return result;
}

Dies ist die Standardmethode für die modulare Exponentiation für große Zahlen in der asymmetrischen Kryptographie.

362
Elias Yarrkov

Beachten Sie, dass Exponentiation durch Quadrieren nicht die optimalste Methode ist. Es ist wahrscheinlich das Beste, was Sie als eine allgemeine Methode tun können, die für alle Exponentenwerte geeignet ist, aber für einen bestimmten Exponentenwert gibt es möglicherweise eine bessere Sequenz, die weniger Multiplikationen erfordert.

Wenn Sie zum Beispiel x ^ 15 berechnen möchten, erhalten Sie die Potenzierungsmethode durch Quadrieren:

x^15 = (x^7)*(x^7)*x 
x^7 = (x^3)*(x^3)*x 
x^3 = x*x*x

Dies sind insgesamt 6 Multiplikationen.

Es stellt sich heraus, dass dies mit "nur" 5 Multiplikationen über Additionskettenexponentiation erfolgen kann.

n*n = n^2
n^2*n = n^3
n^3*n^3 = n^6
n^6*n^6 = n^12
n^12*n^3 = n^15

Es gibt keine effizienten Algorithmen, um diese optimale Sequenz von Multiplikationen zu finden. Aus Wikipedia :

Das Problem der Suche nach der kürzesten Additionskette kann nicht durch dynamische Programmierung gelöst werden, da die Annahme einer optimalen Unterstruktur nicht erfüllt wird. Das heißt, es reicht nicht aus, die Leistung in kleinere Leistungen zu zerlegen, von denen jede minimal berechnet wird, da die Additionsketten für die kleineren Leistungen in Beziehung stehen können (um Berechnungen gemeinsam zu nutzen). Zum Beispiel muss in der kürzesten Additionskette für a¹⁵ das Unterproblem für aproblem als (a³) ² berechnet werden, da a³ wiederverwendet wird (im Gegensatz zu a⁶ = a² (a²) ², das ebenfalls drei Multiplikationen erfordert ).

59
Pramod

Wenn Sie 2 auf eine Leistung erhöhen müssen. Der schnellste Weg, dies zu tun, besteht darin, sich durch die Leistung etwas zu verschieben.

2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)
17
Jake

Hier ist die Methode in Java

private int ipow(int base, int exp)
{
    int result = 1;
    while (exp != 0)
    {
        if ((exp & 1) == 1)
            result *= base;
        exp >>= 1;
        base *= base;
    }

    return result;
}
15
user1067920
int pow( int base, int exponent)

{   // Does not work for negative exponents. (But that would be leaving the range of int) 
    if (exponent == 0) return 1;  // base case;
    int temp = pow(base, exponent/2);
    if (exponent % 2 == 0)
        return temp * temp; 
    else
        return (base * temp * temp);
}
7
Chris Cudmore

Ein extrem spezieller Fall ist, wenn Sie sagen müssen 2 ^ (- x zu y), wobei x natürlich negativ ist und y zu groß ist, um ein Int zu verschieben. Sie können noch 2 ^ x in konstanter Zeit ausführen, indem Sie mit einem Schwimmer verschrauben.

struct IeeeFloat
{

    unsigned int base : 23;
    unsigned int exponent : 8;
    unsigned int signBit : 1;
};


union IeeeFloatUnion
{
    IeeeFloat brokenOut;
    float f;
};

inline float twoToThe(char exponent)
{
    // notice how the range checking is already done on the exponent var 
    static IeeeFloatUnion u;
    u.f = 2.0;
    // Change the exponent part of the float
    u.brokenOut.exponent += (exponent - 1);
    return (u.f);
}

Sie können mehr Potenzen von 2 erhalten, wenn Sie als Basistyp ein Double verwenden. (Vielen Dank an die Kommentatoren, dass Sie diesen Beitrag wegfassen).

Es besteht auch die Möglichkeit, dass Sie mehr über IEEE-Floats erfahren, andere Spezialfälle der Potenzierung können auftreten.

6
Doug T.

Wenn Sie den Wert einer Ganzzahl für 2 auf die Potenz von etwas erhöhen möchten, ist es immer besser, die Shift-Option zu verwenden:

pow(2,5) kann durch 1<<5 ersetzt werden

Das ist viel effizienter.

6
aditya

Nur ein Follow-up zu Kommentaren zur Effektivität der Potenzierung durch Quadrieren.

Der Vorteil dieses Ansatzes ist, dass er in log (n) -Zeit ausgeführt wird. Wenn Sie zum Beispiel etwas Großes berechnen möchten, z. B. x ^ 1048575 (2 ^ 20 - 1), müssen Sie nur 20 Mal durch die Schleife gehen, nicht mehr als 1 Million +, indem Sie den naiven Ansatz verwenden.

In Bezug auf die Komplexität des Codes ist es einfacher, als die optimale Reihenfolge der Multiplikationen zu finden, wie der Vorschlag von Pramod.

Bearbeiten:

Ich denke, ich sollte klären, bevor mich jemand auf das Überlaufpotential hinweist. Dieser Ansatz setzt voraus, dass Sie über eine Art riesige Bibliothek verfügen.

4
Jason Z

power() Funktion für Nur ganze Zahlen  

int power(int base, unsigned int exp){

    if (exp == 0)
        return 1;
    int temp = power(base, exp/2);
    if (exp%2 == 0)
        return temp*temp;
    else
        return base*temp*temp;

}

Komplexität = O(log(exp))

power() Funktion für negative Exp und Float-Basis .

float power(float base, int exp) {

    if( exp == 0)
       return 1;
    float temp = power(base, exp/2);       
    if (exp%2 == 0)
        return temp*temp;
    else {
        if(exp > 0)
            return base*temp*temp;
        else
            return (temp*temp)/base; //negative exponent computation 
    }

} 

Komplexität = O(log(exp))

4
roottraveller

Spät zur Party: 

Nachfolgend finden Sie eine Lösung, die sich mit y < 0 so gut wie möglich befasst. 

  1. Es verwendet ein Ergebnis von intmax_t für die maximale Reichweite. Es gibt keine Vorkehrungen für Antworten, die nicht in intmax_t passen. 
  2. powjii(0, 0) --> 1 das ist ein gemeinsames Ergebnis für diesen Fall.
  3. pow(0,negative), ein anderes undefiniertes Ergebnis, gibt INTMAX_MAX zurück.

    intmax_t powjii(int x, int y) {
      if (y < 0) {
        switch (x) {
          case 0:
            return INTMAX_MAX;
          case 1:
            return 1;
          case -1:
            return y % 2 ? -1 : 1;
        }
        return 0;
      }
      intmax_t z = 1;
      intmax_t base = x;
      for (;;) {
        if (y % 2) {
          z *= base;
        }
        y /= 2;
        if (y == 0) {
          break; 
        }
        base *= base;
      }
      return z;
    }
    

Dieser Code verwendet eine unendliche Schleife for(;;), um den endgültigen base *= base zu vermeiden, der bei anderen Lösungen mit Schleifen üblich ist. Diese Multiplikation ist 1) nicht erforderlich und 2) könnte int*int-Überlauf sein, der UB ist.

2
chux

Eine weitere Implementierung (in Java). Ist möglicherweise nicht die effizienteste Lösung, aber die Anzahl der Iterationen ist dieselbe wie die der Exponential-Lösung.

public static long pow(long base, long exp){        
    if(exp ==0){
        return 1;
    }
    if(exp ==1){
        return base;
    }

    if(exp % 2 == 0){
        long half = pow(base, exp/2);
        return half * half;
    }else{
        long half = pow(base, (exp -1)/2);
        return base * half * half;
    }       
}
1
Vaibhav Fouzdar

generischere Lösung unter Berücksichtigung des negativen Exponenten

private static int pow(int base, int exponent) {

    int result = 1;
    if (exponent == 0)
        return result; // base case;

    if (exponent < 0)
        return 1 / pow(base, -exponent);
    int temp = pow(base, exponent / 2);
    if (exponent % 2 == 0)
        return temp * temp;
    else
        return (base * temp * temp);
}
1
Abhijit Gaikwad

Ich habe einen Algorithmus implementiert, der alle berechneten Kräfte speichert und dann bei Bedarf verwendet. Zum Beispiel ist x ^ 13 gleich (x ^ 2) ^ 2 ^ 2 * x ^ 2 ^ 2 * x wobei x ^ 2 ^ 2 aus der Tabelle genommen wird, anstatt sie erneut zu berechnen. .__ Die erforderliche Multiplikation ist Ceil (Log n)

public static int Power(int base, int exp)
{
    int tab[] = new int[exp + 1];
    tab[0] = 1;
    tab[1] = base;
    return Power(base, exp, tab);
}

public static int Power(int base, int exp, int tab[])
    {
         if(exp == 0) return 1;
         if(exp == 1) return base;
         int i = 1;
         while(i < exp/2)
         {  
            if(tab[2 * i] <= 0)
                tab[2 * i] = tab[i] * tab[i];
            i = i << 1;
          }
    if(exp <=  i)
        return tab[i];
     else return tab[i] * Power(base, exp - i, tab);
}
1
rank1

Wenn Sie den Exponenten (und eine ganze Zahl) zur Kompilierzeit kennen, können Sie die Schleife mithilfe von Vorlagen abwickeln. Dies kann effizienter gestaltet werden, aber ich wollte hier das Grundprinzip demonstrieren:

#include <iostream>

template<unsigned long N>
unsigned long inline exp_unroll(unsigned base) {
    return base * exp_unroll<N-1>(base);
}

Wir beenden die Rekursion mit einer Vorlagenspezialisierung:

template<>
unsigned long inline exp_unroll<1>(unsigned base) {
    return base;
}

Der Exponent muss zur Laufzeit bekannt sein.

int main(int argc, char * argv[]) {
    std::cout << argv[1] <<"**5= " << exp_unroll<5>(atoi(argv[1])) << ;std::endl;
}
0

Mein Fall ist etwas anders, ich versuche, eine Maske aus einer Macht zu erstellen, aber ich dachte, ich würde die Lösung, die ich trotzdem gefunden habe, teilen.

Offensichtlich funktioniert es nur für Potenzen von 2.

Mask1 = 1 << (Exponent - 1);
Mask2 = Mask1 - 1;
return Mask1 + Mask2;
0
MarcusJ

Ich verwende rekursiv, wenn der exp gerade ist, 5 ^ 10 = 25 ^ 5.

int pow(float base,float exp){
   if (exp==0)return 1;
   else if(exp>0&&exp%2==0){
      return pow(base*base,exp/2);
   }else if (exp>0&&exp%2!=0){
      return base*pow(base,exp-1);
   }
}
0
kyorilys

Zusätzlich zur Antwort von Elias, die bei der Implementierung mit vorzeichenbehafteten Ganzzahlen undefiniertes Verhalten verursacht, und zu falschen Werten für hohe Eingaben bei der Implementierung mit vorzeichenlosen Ganzzahlen,

hier ist eine modifizierte Version der Potenzierung durch Quadrieren, die auch mit vorzeichenbehafteten Ganzzahltypen funktioniert und keine falschen Werte angibt:

#include <stdint.h>

#define SQRT_INT64_MAX (INT64_C(0xB504F333))

int64_t alx_pow_s64 (int64_t base, uint8_t exp)
{
    int_fast64_t    base_;
    int_fast64_t    result;

    base_   = base;

    if (base_ == 1)
        return  1;
    if (!exp)
        return  1;
    if (!base_)
        return  0;

    result  = 1;
    if (exp & 1)
        result *= base_;
    exp >>= 1;
    while (exp) {
        if (base_ > SQRT_INT64_MAX)
            return  0;
        base_ *= base_;
        if (exp & 1)
            result *= base_;
        exp >>= 1;
    }

    return  result;
}

Überlegungen zu dieser Funktion:

(1 ** N) == 1
(N ** 0) == 1
(0 ** 0) == 1
(0 ** N) == 0

Wenn ein Überlauf oder ein Umbruch stattfinden soll, return 0;

Ich habe int64_t verwendet, aber jede Breite (mit oder ohne Vorzeichen) kann mit geringen Änderungen verwendet werden. Wenn Sie jedoch einen Integer-Typ ohne feste Breite verwenden müssen, müssen Sie SQRT_INT64_MAX durch (int)sqrt(INT_MAX) (im Fall der Verwendung von int) oder ähnliches ändern, was optimiert werden sollte, aber hässlicher ist und kein C ständiger Ausdruck. Auch das Umwandeln des Ergebnisses von sqrt() in eine int ist aufgrund der Gleitkommapräzision im Falle eines perfekten Quadrats nicht sehr gut, aber da ich keine Implementierung kenne, bei der INT_MAX - oder das Maximum eines beliebigen Typs - ein perfektes Quadrat ist, damit kannst du leben.

0
Cacahuete Frito