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

Lesezeit: 4 Minuten

Doug T.

Was ist der effizienteste Weg, um eine Ganzzahl mit einer anderen Ganzzahl in C zu potenzieren?

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

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

Wenn Sie „Effizienz“ sagen, müssen Sie effizient angeben in Bezug auf was. Geschwindigkeit? Speichernutzung? Codegröße? Wartbarkeit?

– Andy Lester

2. Oktober 2008 um 17:26 Uhr
Hat C keine pow()-Funktion?

– jalf

30. Mai 2009 um 13:07 Uhr
Ja, aber das funktioniert bei Floats oder Doubles, nicht bei Ints

– Nathan Fellmann

30. Mai 2009 um 13:46 Uhr
Wenn Sie sich an die Realität halten ints (und nicht irgendeiner huge-int-Klasse) laufen viele Aufrufe von ipow über. Ich frage mich, ob es eine clevere Möglichkeit gibt, eine Tabelle vorzuberechnen und alle nicht überlaufenden Kombinationen auf eine einfache Tabellensuche zu reduzieren. Dies würde mehr Speicher beanspruchen als die meisten allgemeinen Antworten, aber vielleicht effizienter in Bezug auf die Geschwindigkeit sein.

– Adrian McCarthy

7. Januar 2016 um 17:15 Uhr
pow() keine sichere Funktion

– EsmaeelE

29. Oktober 2017 um 15:42 Uhr

Elias Jarkow

Potenzieren 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 Potenzierung großer Zahlen in der asymmetrischen Kryptografie.

Sie sollten wahrscheinlich eine Überprüfung hinzufügen, dass “exp” nicht negativ ist. Derzeit gibt diese Funktion entweder eine falsche Antwort oder eine Endlosschleife. (Abhängig davon, ob >>= bei einem signed int Null-Padding oder Sign-Extension durchführt – C-Compiler dürfen beide Verhaltensweisen auswählen).

– Benutzer9876

28. Juli 2009 um 16:42 Uhr
Ich habe eine optimierte Version davon geschrieben, die hier kostenlos heruntergeladen werden kann: gist.github.com/3551590 Auf meiner Maschine war es etwa 2,5x schneller.

– orlp

31. August 2012 um 11:18 Uhr
@AkhilJain: Es ist perfekt C; um es auch in Java gültig zu machen, ersetzen Sie while (exp) und if (exp & 1) mit while (exp != 0) und if ((exp & 1) != 0) beziehungsweise.

– Ilmari Karonen

8. April 2013 um 16:38 Uhr
Deine Funktion sollte es wohl haben unsigned expoder negativ behandeln exp richtig.

– Craig McQueen

21. August 2013 um 0:40 Uhr
@ZinanXing Das n-fache Multiplizieren führt zu mehr Multiplikationen und ist langsamer. Diese Methode spart Multiplikationen, indem sie effektiv wiederverwendet werden. ZB, um n^8 zu berechnen, die naive Methode von n*n*n*n*n*n*n*n verwendet 7 Multiplikationen. Dieser Algorithmus berechnet stattdessen m=n*ndann o=m*mdann p=o*owo p = n^8, mit nur drei Multiplikationen. Bei großen Exponenten ist der Leistungsunterschied signifikant.

– Namen53

11. Oktober 2015 um 22:40 Uhr

Pramod

Beachten Sie, dass Potenzieren durch Quadrieren ist nicht die optimale Methode. 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 erfordert.

Wenn Sie beispielsweise x^15 berechnen möchten, erhalten Sie mit der Methode der Potenzierung durch Quadrierung:

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 erfolgen kann Potenzierung der Additionskette.

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 nicht durch dynamisches Programmieren gelöst werden, da es die Annahme einer optimalen Substruktur nicht erfüllt. Das heißt, es reicht nicht aus, die Potenz in kleinere Potenzen zu zerlegen, von denen jede minimal berechnet wird, da die Additionsketten für die kleineren Potenzen verwandt sein können (um Berechnungen zu teilen). Beispielsweise muss in der kürzesten Additionskette für a¹⁵ oben das Unterproblem für a⁶ als (a³)² berechnet werden, da a³ wiederverwendet wird (im Gegensatz zu beispielsweise a⁶ = a²(a²)², was ebenfalls drei Multiplikationen erfordert ).

@JeremySalwen: Wie diese Antwort besagt, ist die binäre Potenzierung im Allgemeinen nicht die optimalste Methode. Es sind derzeit keine effizienten Algorithmen bekannt, um die minimale Folge von Multiplikationen zu finden.

– Eric Postpischil

27. Dezember 2013 um 21:32 Uhr
@EricPostpischil, das hängt von deiner Anwendung ab. Normalerweise brauchen wir keine Allgemeines Algorithmus zu arbeiten alle Zahlen. Siehe The Art of Computer Programming, Bd. 2: Seminumerische Algorithmen

– Schrittmacher

16. September 2014 um 9:03 Uhr
Es gibt eine gute Darstellung dieses genauen Problems in Von der Mathematik zur generischen Programmierung von Alexander Stepanov und Daniel Rose. Dieses Buch sollte IMHO im Regal eines jeden Softwarepraktikers stehen.

– Toby Speight

19. Oktober 2015 um 10:03 Uhr
Siehe auch de.wikipedia.org/wiki/….

– lhf

14. April 2016 um 11:27 Uhr
Dies könnte für ganze Zahlen optimiert werden, weil es weit unter 255 ganzzahlige Potenzen gibt, die keinen Überlauf für 32-Bit-Ganzzahlen verursachen. Sie könnten die optimale Multiplikationsstruktur für jedes int zwischenspeichern. Ich stelle mir vor, dass der Code + die Daten immer noch kleiner wären, als einfach alle Kräfte zwischenzuspeichern …

– Josiah Yoder

17. August 2018 um 19:25 Uhr

Wenn Sie 2 potenzieren müssen. Der schnellste Weg, dies zu tun, ist die Bitverschiebung durch die Macht.

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

Gibt es eine elegante Möglichkeit, dies so zu tun, dass 2 ** 0 == 1 ?

– Rob Smallshire

23. November 2011 um 21:39 Uhr
@RobSmallshire Vielleicht 2 ** x = 1 << x (Da 1<<0 1 ist, müssen Sie prüfen, ob es sich in C std befindet oder ob es plattformabhängig ist, aber Sie könnten dies auch tun 2 ** x = x ? (1 << x) : 1 beachten Sie, dass 2 ** x hat eine Bedeutung in C, und das ist keine Macht 🙂

– Déjà-vu

6. Mai 2021 um 6:47 Uhr

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

Wurzelreisender

power() Funktion zu arbeiten 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 zu arbeiten negativer 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))

Wie unterscheidet sich das von den Antworten von Abhijit Gaikwad und Chux? Bitte argumentieren Sie die Verwendung von float im zweiten angezeigten Codeblock (erwägen Sie zu zeigen, wie power(2.0, -3) wird berechnet).

– Graubart

7. Januar 2016 um 20:27 Uhr
@greybeard Ich habe einen Kommentar erwähnt. vielleicht kann das deine Frage lösen

– Wurzelreisender

8. Januar 2016 um 3:34 Uhr
GNU Scientific Library hat bereits Ihre zweite Funktion: gnu.org/software/gsl/manual/html_node/Small-integer-powers.html

– alx

17. März 2019 um 18:17 Uhr
@roottraveller könntest du das bitte erklären negative exp and float base Lösung? Warum verwenden wir temp, trennen exp durch 2 und prüfen exp (gerade/ungerade)? Danke!

– Leon

23. März 2020 um 22:27 Uhr

Ein extrem spezieller Fall ist, wenn Sie beispielsweise 2^(-x zu y) benötigen, wobei x, ist natürlich negativ und y zu groß ist, um eine Ganzzahl zu verschieben. Sie können immer noch 2^x in konstanter Zeit machen, 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 einen Double als Basistyp verwenden. (Vielen Dank an die Kommentatoren, die dazu beigetragen haben, diesen Beitrag zu beseitigen).

Es besteht auch die Möglichkeit, mehr darüber zu erfahren IEEE schwimmtandere Sonderfälle der Potenzierung könnten sich ergeben.

Wie unterscheidet sich das von den Antworten von Abhijit Gaikwad und Chux? Bitte argumentieren Sie die Verwendung von float im zweiten angezeigten Codeblock (erwägen Sie zu zeigen, wie power(2.0, -3) wird berechnet).

– Graubart

7. Januar 2016 um 20:27 Uhr
@greybeard Ich habe einen Kommentar erwähnt. vielleicht kann das deine Frage lösen

– Wurzelreisender

8. Januar 2016 um 3:34 Uhr
GNU Scientific Library hat bereits Ihre zweite Funktion: gnu.org/software/gsl/manual/html_node/Small-integer-powers.html

– alx

17. März 2019 um 18:17 Uhr
@roottraveller könntest du das bitte erklären negative exp and float base Lösung? Warum verwenden wir temp, trennen exp durch 2 und prüfen exp (gerade/ungerade)? Danke!

– Leon

23. März 2020 um 22:27 Uhr

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

Nicht meine Stimme, aber pow(1, -1) verlässt den Bereich von int trotz negativem Exponenten nicht. Nun, dass man zufällig funktioniert, wie auch pow(-1, -1).

– MSalter

13. August 2015 um 9:34 Uhr
Der einzige negative Exponent kann lassen Sie den Bereich von int nicht verlassen, ist -1. Und es funktioniert nur, wenn base 1 oder -1 ist. Es gibt also nur zwei Paare (base,exp) mit exp<0, die nicht zu nicht ganzzahligen Potenzen führen würden. Obwohl ich Mathematiker 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, den Bereich der ganzen Zahlen zu verlassen ...

– bartgol

15. August 2017 um 15:15 Uhr

14268500cookie-checkDer effizienteste Weg, eine ganzzahlbasierte Potenzfunktion zu implementieren pow(int, int)

#Algorithmus #c++ #Mathematik #Potenzierung