Der effizienteste Weg, eine ganze Zahl basierte Power-Funktion pow (int, int) zu implementieren

Question

Was ist der effizienteste Weg gegeben eine ganze Zahl an die Macht einer anderen ganzen Zahl in C zu erhöhen?

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

// 5^5
pow(5,5) == 3125

Answer 1

Binäre Exponentiation.

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 Potenzierung für große Zahlen in der asymmetrischen Kryptographie zu tun.

Answer 2

Beachten Sie, dass Binäre Exponentiation nicht die optimale Methode. Es ist wahrscheinlich das Beste, was Sie als allgemeine Methode tun können, die für alle Exponenten Werte, sondern für einen bestimmten Exponenten Wert arbeitet es könnte eine bessere Sequenz sein, die weniger Multiplikationen benötigt.

Zum Beispiel, wenn Sie berechnen mögen x ^ 15, wobei das Verfahren von Binäre Exponentiation gibt Ihnen:

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

Dies ist insgesamt 6 Multiplikationen.

Es stellt sich heraus, das mit „nur“ 5 Multiplikationen über Zusatz-Kette Potenzierung .

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 diese optimale Folge von Multiplikationen zu finden. Aus Wikipedia :

  

Das Problem der kürzeste Additionskette zu finden, kann nicht durch die dynamische Programmierung gelöst werden, weil es nicht die Annahme eines optimalen Unterbaus nicht erfüllt. Das heißt, dass es nicht ausreicht, um die Kraft in kleinere Kräfte zu zersetzen, von denen jede minimal berechnet wird, da die Additionsketten für die kleineren Kräfte in Zusammenhang stehen können (Berechnungen zu teilen). Zum Beispiel oben in der kürzesten Additionskette für a¹⁵ muss die Subproblem für A⁶ wie folgt berechnet werden (a³) ² seit A³ wieder verwendet (im Gegensatz zu, sagen wir, A⁶ = a² (a²) ², die erfordert auch drei Multiplikationen ).

Answer 3

Wenn benötigen Sie 2 auf eine Leistung zu erhöhen. Der schnellste Weg durch die Kraft so ist zu Bitverschiebung zu tun.

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

Answer 4

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

Answer 5

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

Answer 6

Wenn Sie für 2, um den Wert einer ganzen Zahl zu bekommen, um die Macht der etwas angehoben ist es immer besser, die Verschiebung Option zu verwenden:

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

Das ist viel effizienter.

Answer 7

Ein extrem spezialisierter Fall ist, wenn Sie sagen, müssen 2 ^ (- x zu y), wobei x ist natürlich negativ ist und y ist zu groß, um auf einem int zu tun zu verschieben. Sie können noch 2 tun ^ x in konstanter Zeit, indem sie mit einem Schwimmer zu 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 eine doppelte als Basistyp verwendet wird. (Vielen Dank an commen für die Unterstützung dieses Amt zu quadrieren weg).

Es gibt auch die Möglichkeit, dass Sie mehr über IEEE schwimmt , andere Sonderfälle von Potenzierung lernen könnte präsentieren sich.

Answer 8

So wie ein auf die Kommentare auf die Effizienz der Potenzierung Follow-up von quadriert.

Der Vorteil dieses Ansatzes besteht darin, dass es in log (n) die Zeit abläuft. Zum Beispiel, wenn Sie etwas Großes, zu berechnen, wie x ^ 1048575 (2 ^ 20-1) gehen. Sie müssen nur gehen durch die Schleife 20-mal, nicht mehr als 1 Million + mit dem naiven Ansatz

Auch im Hinblick auf die Komplexität des Codes, ist es einfacher, als zu versuchen, die optimale Reihenfolge der Multiplikationen, a la Pramod Vorschlag zu finden.

Edit:

Ich glaube, ich klären sollten, bevor mich jemand für Überlauf für den möglichen Tags. Dieser Ansatz geht davon aus, dass Sie irgendeine Art von hugeint Bibliothek haben.

Answer 9

power() Funktion arbeitet für Die ganzen Zahlen nur

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 negativ exp zu arbeiten und schwebt 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))

Answer 10

spät zur Party:

Im Folgenden finden Sie eine Lösung, die auch mit y < 0 beschäftigt, so gut wie er kann.

1. Es wird ein Ergebnis von intmax_t für maximale Reichweite. Es gibt keine Bestimmung für Antworten, die in intmax_t nicht passen.
2. powjii(0, 0) --> 1 das ist ein gemeinsames Ergebnis für diesen Fall.

3. pow(0,negative), ein anderes undefiniertes Ergebnis kehrt 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 für immer Schleife for(;;) die endgültige base *= base gemeinsam in anderen geschlungen Lösungen zu vermeiden. Das Multiplikation 1) nicht erforderlich und 2) könnte Überlauf werden int*int die UB.

Answer 11

mehr generische Lösung unter Berücksichtigung 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);
}

Answer 12

Eine weitere Implementierung (in Java). nicht die effizienteste Lösung sein kann, aber Anzahl der Iterationen ist das gleiche wie die von 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;
    }       
}

Answer 13

Ich verwende rekursiv, wenn die exp selbst 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);
   }
}

Answer 14

Neben die Antwort von Elias, das nicht definiertes Verhalten verursacht, wenn mit signierten Integer implementiert und falschen Werten für hohen Eingang, wenn sie mit unsignierten ganzen Zahlen umgesetzt,

Hier ist eine modifizierte Version des Binäre Exponentiation, die auch mit signierten Integer-Typen arbeitet, und nicht geben falsche Werte:

#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 für diese Funktion:

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

Wenn ein Überlauf oder in der Verpackung wird zu, return 0;

Ich benutzen int64_t, aber jede Breite (mit oder ohne Vorzeichen) kann mit wenig Modifikation verwendet werden. Wenn Sie jedoch einen nicht-feste Breite Integer-Typen verwenden müssen, müssen Sie SQRT_INT64_MAX von (int)sqrt(INT_MAX) ändern (im Fall der Verwendung von int) oder etwas ähnlichem, das optimiert werden soll, aber es ist hässlicher, und kein C konstanter Ausdruck. Auch Gießen das Ergebnis sqrt() zu einem int ist nicht sehr gut, weil der Punkt precission bei einem perfekten Platz schwimmen, aber ich weiß nicht, von der Anwendung, wo INT_MAX -oder das Maximum jeder Typ- ein perfekter Platz, Sie können damit leben.

Answer 15

Ich habe Algorithmus implementiert, die alle berechneten Kräfte speichert und dann nutzt sie, wenn notwendig. So zum Beispiel x ^ 13 gleich (x ^ 2) ^ 2 ^ 2 * x ^ 2 ^ 2 * x, wobei x ^ 2 ^ 2 aus der Tabelle entnommen, anstatt es der Berechnung wieder. Dies ist im Grunde der Umsetzung von @Pramod Antwort (aber in C #). Die Anzahl der Multiplikation erforderlich 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);
}

Answer 16

Mein Fall ist ein wenig anders, ich versuche, eine Maske von einer Macht zu schaffen, aber ich dachte, ich würde die Lösung teile ich sowieso gefunden.

Offensichtlich ist es funktioniert nur für Potenzen von 2.

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

Answer 17

Falls Sie die Exponenten kennen (und es ist eine ganze Zahl) zur Compile-Zeit können Sie Vorlagen verwenden, um die Schleife entrollen. Dies kann effizienter gestaltet werden, aber ich wollte das grundlegende Prinzip demonstrieren hier:

#include <iostream>

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

Wir beenden die Rekursion eine Vorlage Spezialisierung mit:

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

Answer 18

den Sonderfall von 2 bis potenziert Ignorieren, der effizienteste Weg geht einfach Iteration sein.

int pow(int base, int pow) {
  int res = 1;
  for(int i=pow; i<pow; i++)
    res *= base;

  return res;
}

EDIT:. Wie wurde dies darauf hingewiesen, ist nicht der effizienteste Weg, ... so lange, wie Sie die Effizienz als CPU-Zyklen definieren, die ich denke, fair genug ist