Der effizienteste Weg, um eine ganzzahlige Potenzfunktion pow (int, int) zu implementieren

249

Was ist der effizienteste Weg, um 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
Doug T.
quelle
3
Wenn Sie "Effizienz" sagen, müssen Sie die Effizienz in Bezug auf was angeben. Geschwindigkeit? Speichernutzung? Codegröße? Wartbarkeit?
Andy Lester
Hat C keine pow () -Funktion?
Jalf
16
Ja, aber das funktioniert auf Floats oder Doubles, nicht auf Ints
Nathan Fellman
1
Wenn Sie sich an die tatsächlichen ints halten (und nicht an eine riesige Int-Klasse), werden viele Aufrufe von ipow überlaufen. Ich frage mich, ob es eine clevere Möglichkeit gibt, eine Tabelle vorab zu berechnen und alle nicht überfüllten Kombinationen auf eine einfache Tabellensuche zu reduzieren. Dies würde mehr Speicher benötigen als die meisten allgemeinen Antworten, wäre aber möglicherweise effizienter in Bezug auf die Geschwindigkeit.
Adrian McCarthy
pow()keine sichere Funktion
EsmaeelE

Antworten:

391

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.

Elias Yarrkov
quelle
38
Sie sollten wahrscheinlich einen Scheck hinzufügen, dass "exp" nicht negativ ist. Derzeit gibt diese Funktion entweder eine falsche Antwort oder eine Schleife für immer. (Abhängig davon, ob >> = auf einem signierten Int Zero-Padding oder Sign-Extension ausführt, dürfen C-Compiler beide Verhaltensweisen auswählen.)
user9876
23
Ich habe eine optimierte Version davon geschrieben, die hier kostenlos heruntergeladen werden kann: gist.github.com/3551590 Auf meinem Computer war sie ungefähr 2,5-mal schneller.
Orlp
10
@AkhilJain: Es ist vollkommen gut C; es gilt auch in Java zu machen, ersetzen while (exp)und if (exp & 1)mit while (exp != 0)und if ((exp & 1) != 0)jeweils.
Ilmari Karonen
3
Ihre Funktion sollte wahrscheinlich haben unsigned expoder negativ exprichtig behandeln.
Craig McQueen
5
@ZinanXing n-fache Multiplikation führt zu mehr Multiplikationen und ist langsamer. Diese Methode spart Multiplikationen, indem sie effektiv wiederverwendet wird. Um n ^ 8 zu berechnen, verwendet die naive Methode n*n*n*n*n*n*n*n7 Multiplikationen. Dieser Algorithmus berechnet statt m=n*n, dann o=m*m, dann p=o*o, in p= n ^ 8, mit nur drei Multiplikationen. Bei großen Exponenten ist der Leistungsunterschied erheblich.
Bames53
68

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

Wenn Sie beispielsweise x ^ 15 berechnen möchten, erhalten Sie mit der Exponentiationsmethode 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 durch Potenzierung der Additionskette 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 Folge von Multiplikationen zu finden. Aus Wikipedia :

Das Problem, die kürzeste Additionskette zu finden, kann durch dynamische Programmierung nicht gelöst werden, da es die Annahme einer optimalen Unterstruktur nicht erfüllt. 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 gesetzt werden können (um Berechnungen zu teilen). Zum Beispiel muss in der kürzesten Additionskette für a¹⁵ oben das Teilproblem für a⁶ als (a³) ² berechnet werden, da a³ wiederverwendet wird (im Gegensatz zu beispielsweise a⁶ = a² (a²) ², was ebenfalls drei Multiplikationen erfordert ).

Pramod
quelle
4
@JeremySalwen: Wie diese Antwort besagt, ist die binäre Potenzierung im Allgemeinen nicht die optimalste Methode. Derzeit sind keine effizienten Algorithmen bekannt, um die minimale Folge von Multiplikationen zu finden.
Eric Postpischil
2
@EricPostpischil, das hängt von deiner Anwendung ab. Normalerweise benötigen wir keinen allgemeinen Algorithmus, um für alle Zahlen zu arbeiten. Siehe The Art of Computer Programming, Vol. 3, No. 2: Seminumerische Algorithmen
Pacerier
3
Es gibt eine gute Darstellung dieses genauen Problems in Von der Mathematik zur generischen Programmierung von Alexander Stepanov und Daniel Rose. Dieses Buch sollte im Regal eines jeden Software-Praktikers stehen, IMHO.
Toby Speight
2
Siehe auch en.wikipedia.org/wiki/… .
lhf
Dies könnte für Ganzzahlen optimiert werden, da es weit unter 255 Ganzzahlleistungen gibt, die bei 32-Bit-Ganzzahlen keinen Überlauf verursachen. Sie können die optimale Multiplikationsstruktur für jedes int zwischenspeichern. Ich stelle mir vor, der Code + die Daten wären immer noch kleiner als nur das Zwischenspeichern aller Kräfte ...
Josiah Yoder
22

Wenn Sie 2 auf eine Potenz erhöhen müssen. Der schnellste Weg, dies zu tun, ist eine Bitverschiebung durch die Leistung.

2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)
Jake
quelle
Gibt es eine elegante Möglichkeit, dies so zu tun, dass 2 ** 0 == 1?
Rob Smallshire
16
2 ** 0 == 1 << 0 == 1
Jake
14

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;
}
user1067920
quelle
funktioniert nicht für große Zahlen zB pow (71045970,41535484)
Anushree Acharjee
16
@ AnushreeAcharjee natürlich nicht. Das Berechnen einer solchen Zahl würde eine Arithmetik mit beliebiger Genauigkeit erfordern.
David Etler
Verwenden Sie BigInteger # modPow oder Biginteger # pow für große Zahlen. Geeignete Algorithmen basierend auf der Größe der Argumente sind bereits implementiert
Raman Yelianevich
Dies ist KEINE Java-Frage!
Cacahuete Frito
7
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);
}
Chris Cudmore
quelle
Nicht meine Stimme, pow(1, -1)verlässt aber trotz eines negativen Exponenten nicht den Bereich von int. Jetzt, wo man zufällig arbeitet, genauso wie pow(-1, -1).
MSalters
Der einzige negative Exponent, der Sie möglicherweise nicht dazu bringt, den Bereich von int zu verlassen, ist -1. Und es funktioniert nur, wenn die Basis 1 oder -1 ist. Es gibt also nur zwei Paare (Basis, Exp) mit Exp <0, die nicht zu nicht ganzzahligen Potenzen führen würden. Obwohl ich Matematiker bin und Quantifizierer mag, denke ich, dass es in diesem Fall in der Praxis in Ordnung ist zu sagen, dass ein negativer Exponent Sie dazu bringt, das ganzzahlige Reich zu verlassen ...
Bartgol
6

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

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

Das ist viel effizienter.

aditya
quelle
6

power()Funktion, die nur für Ganzzahlen funktioniert

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, um für negative exp und float base zu arbeiten .

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))

Roottraveller
quelle
Wie unterscheidet sich das von den Antworten von Abhijit Gaikwad und Chux ? Bitte argumentieren Sie mit der Verwendung floatim zweiten vorgestellten Codeblock (zeigen Sie, wie power(2.0, -3)berechnet wird).
Graubart
@ Greybeard Ich habe einige Kommentare erwähnt. Möglicherweise kann das Ihre Anfrage lösen
Roottraveller
1
Die GNU Scientific Library hat bereits Ihre zweite Funktion: gnu.org/software/gsl/manual/html_node/Small-integer-powers.html
Cacahuete Frito
@roottraveller Könnten Sie bitte die negative exp and float baseLösung erklären ? Warum verwenden wir temp, trennen exp durch 2 und überprüfen exp (gerade / ungerade)? Vielen Dank!
Lev
6

Ein äußerst spezialisierter Fall ist, wenn Sie sagen müssen 2 ^ (- x zum y), wobei x natürlich negativ ist und y zu groß ist, um auf einem int zu verschieben. Sie können immer noch 2 ^ x in konstanter Zeit ausführen, indem Sie mit einem Schwimmer schrauben.

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, indem Sie ein Double als Basistyp verwenden. (Vielen Dank an die Kommentatoren, die geholfen haben, diesen Beitrag zu korrigieren).

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

Doug T.
quelle
Schicke Lösung, aber unsigend?
Paxdiablo
Ein IEEE-Float ist Basis x 2 ^ exp. Eine Änderung des Exponentenwerts führt zu nichts anderem als einer Multiplikation mit einer Zweierpotenz. Die Wahrscheinlichkeit ist hoch, dass der Float denormalisiert wird. Ihre Lösung ist
meiner Meinung nach
Sie haben alle Recht, ich habe mich falsch daran erinnert, dass meine Lösung ursprünglich vor ach so langer Zeit explizit für Potenzen von 2 geschrieben wurde. Ich habe meine Antwort umgeschrieben, um eine Sonderfalllösung für das Problem zu sein.
Doug T.
Erstens ist der Code wie angegeben fehlerhaft und muss bearbeitet werden, damit er kompiliert werden kann. Zweitens wird der Code auf einem Core2d mit gcc gebrochen. siehe diese Müllkippe Vielleicht habe ich etwas falsch gemacht. Ich glaube jedoch nicht, dass dies funktionieren wird, da der IEEE-Float-Exponent Basis 10 ist.
Freespace
3
Basis 10? Äh nein, es ist Basis 2, es sei denn, Sie meinten 10 in binär :)
Drealmer
4

Nur als Folge von Kommentaren zur Effizienz der Potenzierung durch Quadrieren.

Der Vorteil dieses Ansatzes besteht darin, dass er in log (n) -Zeit ausgeführt wird. Wenn Sie beispielsweise etwas Großes wie x ^ 1048575 (2 ^ 20 - 1) berechnen möchten, müssen Sie die Schleife nur 20 Mal durchlaufen, nicht 1 Million + mit dem naiven Ansatz.

In Bezug auf die Codekomplexität ist es auch einfacher als zu versuchen, die optimalste Folge von Multiplikationen zu finden, wie es a la Pramod vorschlägt.

Bearbeiten:

Ich denke, ich sollte klären, bevor mich jemand auf das Potenzial für einen Überlauf hinweist. Bei diesem Ansatz wird davon ausgegangen, dass Sie über eine riesige Bibliothek verfügen.

Jason Z.
quelle
2

Spät zur Party:

Im Folgenden finden Sie eine Lösung, die auch y < 0so gut wie möglich funktioniert.

  1. Es wird ein Ergebnis von intmax_tfür maximale Reichweite verwendet. Antworten, die nicht passen, sind nicht vorgesehen intmax_t.
  2. powjii(0, 0) --> 1Das ist ein häufiges Ergebnis für diesen Fall.
  3. pow(0,negative), ein weiteres undefiniertes Ergebnis, wird zurückgegeben INTMAX_MAX

    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 Forever-Schleife for(;;), um das endgültige base *= baseCommon in anderen Loop-Lösungen zu vermeiden . Diese Multiplikation ist 1) nicht erforderlich und 2) könnte ein int*intÜberlauf sein, der UB ist.

chux - Monica wieder einsetzen
quelle
powjii(INT_MAX, 63)verursacht UB in base *= base. Überprüfen Sie, ob Sie multiplizieren können, oder wechseln Sie zu unsigniert und lassen Sie es umlaufen.
Cacahuete Frito
Es gibt keinen Grund, expunterschrieben zu werden. Es verkompliziert den Code aufgrund der seltsamen Situation, in der er (-1) ** (-N)gültig ist, und jeder abs(base) > 1gilt 0für negative Werte von exp. Daher ist es besser, ihn ohne Vorzeichen zu haben und diesen Code zu speichern.
Cacahuete Frito
1
@CacahueteFrito Stimmt, dass ydie Unterschrift nicht wirklich benötigt wird und die von Ihnen kommentierten Komplikationen mit sich bringt, aber die Anfrage von OP war spezifisch pow(int, int). Somit gehören diese guten Kommentare zur Frage des OP. Da OP nicht angegeben hat, was bei Überlauf zu tun ist, ist eine genau definierte falsche Antwort nur unwesentlich besser als UB. Angesichts des "effizientesten Weges" bezweifle ich, dass OP sich um OF kümmert.
chux
1

allgemeinere Lösung unter Berücksichtigung negativer Exponenet

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);
}
Abhijit Gaikwad
quelle
1
Die Ganzzahldivision führt zu einer Ganzzahl, sodass Ihr negativer Exponent viel effizienter sein kann, da er nur 0, 1 oder -1
zurückgibt
pow(i, INT_MIN)könnte eine Endlosschleife sein.
chux
1
@chux: Es könnte Ihre Festplatte formatieren: Ganzzahlüberlauf ist UB.
MSalters
@MSalters pow(i, INT_MIN)ist kein ganzzahliger Überlauf. Die Zuordnung dieses Ergebnisses zu tempkann sicherlich überlaufen, was möglicherweise das Ende der Zeit verursacht , aber ich werde mich mit einem scheinbar zufälligen Wert zufrieden geben. :-)
chux
0

Noch eine Implementierung (in Java). Möglicherweise nicht die effizienteste Lösung, aber die Anzahl der Iterationen entspricht der 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;
    }       
}
Vaibhav Fouzdar
quelle
Keine Java-Frage!
Cacahuete Frito
0

Ich benutze rekursiv, wenn die 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);
   }
}
Kyorilys
quelle
0

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

Hier ist eine modifizierte Version der Exponentiation 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 eine Umhüllung stattfinden soll, return 0;

Ich habe verwendet int64_t, aber jede Breite (signiert oder nicht signiert) kann mit nur geringen Änderungen verwendet werden. Wenn Sie jedoch einen nicht-feste Breite Integer - Typen verwenden müssen, werden Sie ändern müssen , SQRT_INT64_MAXum (int)sqrt(INT_MAX)(in dem Fall der Verwendung int) oder etwas ähnliches, das optimiert werden soll, aber es ist hässlicher, und kein C konstanter Ausdruck. Auch das Casting des Ergebnisses sqrt()auf ein intist aufgrund der Gleitkomma-Präzision bei einem perfekten Quadrat nicht sehr gut, aber da ich keine Implementierung kenne, bei der INT_MAX- oder das Maximum eines Typs - ein perfektes Quadrat ist, können Sie leben damit.

Cacahuete Frito
quelle
0

Ich habe einen Algorithmus implementiert, der alle berechneten Potenzen speichert und sie dann bei Bedarf verwendet. So ist zum Beispiel x ^ 13 gleich (x ^ 2) ^ 2 ^ 2 * x ^ 2 ^ 2 * x, wobei x ^ 2 ^ 2 aus der Tabelle entnommen wird, anstatt es erneut zu berechnen. Dies ist im Grunde eine Implementierung der @ Pramod-Antwort (jedoch in C #). Die Anzahl der erforderlichen Multiplikationen 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);
}
Rang 1
quelle
public? 2 gleichnamige Funktionen? Dies ist eine C-Frage.
Cacahuete Frito
-1

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

Offensichtlich funktioniert es nur für Potenzen von 2.

Mask1 = 1 << (Exponent - 1);
Mask2 = Mask1 - 1;
return Mask1 + Mask2;
MarcusJ
quelle
Ich habe das versucht, es funktioniert nicht für 64-Bit, es wird verschoben, um niemals zurückzukehren, und in diesem speziellen Fall versuche ich, alle Bits niedriger als X einschließlich zu setzen.
MarcusJ
War das für 1 << 64? Das ist ein Überlauf. Die größte ganze Zahl liegt knapp darunter: (1 << 64) - 1.
Michaël Roy
1 << 64 == 0, deshalb. Vielleicht ist Ihre Darstellung am besten für Ihre App. Ich bevorzuge Dinge, die in ein Makro eingefügt werden können, ohne eine zusätzliche Variable, wie zum Beispiel #define MASK(e) (((e) >= 64) ? -1 :( (1 << (e)) - 1)), die zur Kompilierungszeit berechnet werden können
Michaël Roy
Ja, ich weiß, was ein Überlauf ist. Nur weil ich dieses Wort nicht benutzt habe, ist das keine Einladung, unnötig herablassend zu sein. Wie gesagt, das funktioniert bei mir und es hat ein wenig Mühe gekostet, es zu entdecken und es daher zu teilen. So einfach ist das.
MarcusJ
Es tut mir leid, wenn ich dich beleidigt habe. Das wollte ich wirklich nicht.
Michaël Roy
-1

Wenn Sie den Exponenten (und eine Ganzzahl) zur Kompilierungszeit kennen, können Sie die Schleife mithilfe von Vorlagen abrollen. 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;
}
Johannes Blaschke
quelle
1
Dies ist eindeutig keine C ++ - Frage. (c != c++) == 1
Cacahuete Frito