Warum ist "int pow (int base, int exponent)" nicht in den Standard-C ++ - Bibliotheken enthalten?

Ich habe das Gefühl, ich muss es einfach nicht finden können. Gibt es einen Grund, warum die C ++ - powFunktion die "Power" -Funktion nur für floats und doubles implementiert ?

Ich weiß, dass die Implementierung trivial ist. Ich habe nur das Gefühl, dass ich Arbeiten mache, die in einer Standardbibliothek sein sollten. Eine robuste Power-Funktion (dh sie behandelt den Überlauf auf konsistente, explizite Weise) macht keinen Spaß beim Schreiben.

Ab C++11sofort wurden Sonderfälle zur Reihe der Leistungsfunktionen (und anderer) hinzugefügt. C++11 [c.math] /11stellt fest, nachdem alle float/double/long doubleÜberladungen aufgelistet wurden (meine Betonung und umschrieben):

Darüber hinaus müssen zusätzliche Überladungen vorhanden sein, die ausreichen, um sicherzustellen, dass, wenn ein Argument, das einem doubleParameter entspricht, einen Typ doubleoder einen ganzzahligen Typ hat, alle Argumente, die doubleParametern entsprechen, effektiv umgewandelt werden double.

Im Grunde genommen werden ganzzahlige Parameter auf doppelt aktualisiert, um die Operation auszuführen.

Vor C++11(als Ihre Frage gestellt wurde) gab es keine ganzzahligen Überladungen.

Da ich weder eng mit den Erstellern Cnoch C++in den Tagen ihrer Gründung verbunden war (obwohl ich ziemlich alt bin ), noch Teil der ANSI / ISO-Komitees, die die Standards erstellt haben, ist dies notwendigerweise eine Meinung von meiner Seite. Ich würde gerne denken, dass es eine informierte Meinung ist, aber wie meine Frau Ihnen sagen wird (häufig und ohne viel Ermutigung), habe ich mich vorher geirrt :-)

Es folgt die Annahme, was es wert ist.

Ich vermute, dass der Grund, warum das ursprüngliche Pre-ANSI Cdiese Funktion nicht hatte, darin besteht, dass es völlig unnötig war. Zuerst gab es bereits eine sehr gute Möglichkeit, ganzzahlige Potenzen zu erstellen (mit Doppelwerten und dann einfach wieder in eine Ganzzahl umzuwandeln, vor der Konvertierung auf Ganzzahlüberlauf und -unterlauf zu prüfen).

Zweitens, eine andere Sache , die Sie dürfen nicht vergessen, ist , dass die ursprüngliche Absicht Cals war Systeme Sprache Programmierung, und es ist fraglich , ob Floating - Point in dieser Arena überhaupt wünschenswert ist.

Da einer der ersten Anwendungsfälle darin bestand, UNIX zu codieren, wäre der Gleitkomma nahezu unbrauchbar gewesen. BCPL, auf dem C basierte, hatte auch keine Verwendung für Potenzen (es hatte überhaupt keinen Gleitkomma aus dem Speicher).

Abgesehen davon wäre ein integraler Energieoperator wahrscheinlich eher ein binärer Operator als ein Bibliotheksaufruf gewesen. Sie fügen nicht zwei Ganzzahlen mit, x = add (y, z)sondern mit x = y + z- einem Teil der eigentlichen Sprache anstelle der Bibliothek hinzu.

Drittens, da die Implementierung integraler Leistung relativ trivial ist, ist es fast sicher, dass die Entwickler der Sprache ihre Zeit besser nutzen würden, um nützlichere Dinge bereitzustellen (siehe unten Kommentare zu Opportunitätskosten).

Das ist auch für das Original relevant C++. Da die ursprüngliche Implementierung praktisch nur ein Übersetzer war, der CCode produzierte , übertrug sie viele der Attribute von C. Seine ursprüngliche Absicht war C-mit-Klassen, nicht C-mit-Klassen-plus-ein-bisschen-extra-Mathe-Zeug.

Um zu verstehen, warum es noch nie zuvor zu den Standards hinzugefügt wurde C++11, müssen Sie bedenken, dass die Normungsgremien spezifische Richtlinien befolgen müssen. Zum Beispiel wurde ANSI Cspeziell beauftragt, bestehende Praktiken zu kodifizieren und keine neue Sprache zu erstellen. Sonst hätten sie verrückt werden und uns Ada geben können :-)

Spätere Iterationen dieses Standards haben auch spezifische Richtlinien und können in den Begründungsdokumenten gefunden werden (Begründung, warum der Ausschuss bestimmte Entscheidungen getroffen hat, nicht Begründung für die Sprache selbst).

Zum Beispiel enthält das C99Begründungsdokument speziell zwei der C89Leitprinzipien, die einschränken, was hinzugefügt werden kann:

• Halten Sie die Sprache klein und einfach.
  
• Geben Sie nur eine Möglichkeit an, eine Operation auszuführen.

Richtlinien (nicht unbedingt diese spezifischen ) sind für die einzelnen Arbeitsgruppen festgelegt und beschränken daher auch die C++Ausschüsse (und alle anderen ISO-Gruppen).

Darüber hinaus erkennen die Normungsgremien, dass für jede Entscheidung, die sie treffen, Opportunitätskosten (ein wirtschaftlicher Begriff, auf den Sie bei einer getroffenen Entscheidung verzichten müssen) anfallen. Zum Beispiel sind die Opportunitätskosten für den Kauf dieses 10.000-Dollar-Über-Spielautomaten herzliche Beziehungen (oder wahrscheinlich alle Beziehungen) zu Ihrer anderen Hälfte für etwa sechs Monate.

Eric Gunnerson erklärt dies gut mit seiner Erklärung von -100 Punkten , warum Dinge nicht immer zu Microsoft-Produkten hinzugefügt werden. Grundsätzlich beginnt eine Funktion mit 100 Punkten in der Lücke, sodass sie einen erheblichen Mehrwert bieten muss, um überhaupt berücksichtigt zu werden.

Mit anderen Worten, hätten Sie lieber einen integrierten Stromversorger (den ehrlich gesagt jeder halbwegs anständige Codierer in zehn Minuten aufpeppen könnte) oder Multithreading zum Standard hinzugefügt? Für mich selbst würde ich lieber Letzteres haben und mich nicht mit den unterschiedlichen Implementierungen unter UNIX und Windows herumschlagen müssen.

Ich würde auch gerne Tausende und Abertausende von Sammlungen in der Standardbibliothek sehen (Hashes, Bäume, rot-schwarze Bäume, Wörterbuch, beliebige Karten usw.), aber wie die Begründung besagt:

Ein Standard ist ein Vertrag zwischen Implementierer und Programmierer.

Und die Anzahl der Implementierer in den Normungsgremien überwiegt bei weitem die Anzahl der Programmierer (oder zumindest der Programmierer, die die Opportunitätskosten nicht verstehen). Wenn all diese Dinge hinzugefügt würden, C++wäre C++215xund würde der nächste Standard dreihundert Jahre später von Compiler-Entwicklern vollständig implementiert.

Wie auch immer, das sind meine (ziemlich umfangreichen) Gedanken zu diesem Thema. Wenn nur Stimmen eher nach Quantität als nach Qualität abgegeben würden, würde ich bald alle anderen aus dem Wasser sprengen. Danke fürs Zuhören :-)

Bei jedem Integraltyp mit fester Breite laufen ohnehin fast alle möglichen Eingangspaare über den Typ hinaus. Was nützt es, eine Funktion zu standardisieren, die für die überwiegende Mehrheit ihrer möglichen Eingaben kein nützliches Ergebnis liefert?

Sie benötigen so ziemlich einen großen Ganzzahltyp, um die Funktion nützlich zu machen, und die meisten großen Ganzzahlbibliotheken bieten die Funktion.

Bearbeiten: In einem Kommentar zu der Frage schreibt static_rtti: "Die meisten Eingaben verursachen einen Überlauf? Dasselbe gilt für exp und double pow. Ich sehe niemanden, der sich beschwert." Das ist falsch.

Lassen wir es beiseite exp, denn das ist nebensächlich (obwohl es meinen Fall tatsächlich stärker machen würde), und konzentrieren wir uns darauf double pow(double x, double y). Für welchen Teil von (x, y) Paaren macht diese Funktion etwas Nützliches (dh nicht einfach Überlauf oder Unterlauf)?

Ich werde mich eigentlich nur auf einen kleinen Teil der Eingabepaare konzentrieren, powwas sinnvoll ist, da dies ausreicht, um meinen Standpunkt zu beweisen: Wenn x positiv ist und | y | <= 1, powläuft dann nicht über oder unter. Dies umfasst fast ein Viertel aller Gleitkomma-Paare (genau die Hälfte der Nicht-NaN-Gleitkommazahlen ist positiv, und nur weniger als die Hälfte der Nicht-NaN-Gleitkommazahlen hat eine Größe von weniger als 1). Natürlich gibt es viele andere Eingabepaare, für die pownützliche Ergebnisse erzielt werden, aber wir haben festgestellt, dass es mindestens ein Viertel aller Eingaben ist.

Betrachten wir nun eine ganzzahlige Potenzfunktion mit fester Breite (dh ohne Bignum). Für welche Teileingänge läuft es nicht einfach über? Um die Anzahl der aussagekräftigen Eingabepaare zu maximieren, sollte die Basis signiert und der Exponent vorzeichenlos sein. Angenommen, die Basis und der Exponent sind beide nBits breit. Wir können leicht eine Grenze für den Teil der Eingaben bekommen, die sinnvoll sind:

• Wenn der Exponent 0 oder 1 ist, ist jede Basis sinnvoll.
• Wenn der Exponent 2 oder größer ist, liefert keine Basis größer als 2 ^ (n / 2) ein aussagekräftiges Ergebnis.

Somit führen von den 2 ^ (2n) -Eingangspaaren weniger als 2 ^ (n + 1) + 2 ^ (3n / 2) zu aussagekräftigen Ergebnissen. Wenn wir uns die wahrscheinlich am häufigsten verwendete Verwendung von 32-Bit-Ganzzahlen ansehen, bedeutet dies, dass etwas in der Größenordnung von 1/1000 von einem Prozent der Eingabepaare nicht einfach überläuft.

Weil es sowieso keine Möglichkeit gibt, alle ganzzahligen Potenzen in einem int darzustellen:

>>> print 2**-4
0.0625

Das ist eigentlich eine interessante Frage. Ein Argument, das ich in der Diskussion nicht gefunden habe, ist das einfache Fehlen offensichtlicher Rückgabewerte für die Argumente. Zählen wir, wie die hypthetische int pow_int(int, int)Funktion versagen könnte.

1. Überlauf
2. Ergebnis undefiniert pow_int(0,0)
3. Ergebnis kann nicht dargestellt werden pow_int(2,-1)

Die Funktion verfügt über mindestens 2 Fehlermodi. Ganzzahlen können diese Werte nicht darstellen, das Verhalten der Funktion müsste in diesen Fällen vom Standard definiert werden - und Programmierer müssten wissen, wie genau die Funktion diese Fälle behandelt.

Insgesamt scheint es die einzig sinnvolle Option zu sein, die Funktion wegzulassen. Der Programmierer kann stattdessen die Gleitkommaversion mit allen verfügbaren Fehlerberichten verwenden.

Kurze Antwort:

Eine Spezialisierung pow(x, n), wo neine natürliche Zahl ist oft nützlich für Pünktlichkeit . Aber das Generikum der Standardbibliothek pow()funktioniert für diesen Zweck immer noch ziemlich ( überraschend! ) Gut und es ist absolut wichtig, so wenig wie möglich in die Standard-C-Bibliothek aufzunehmen, damit sie so portabel und so einfach wie möglich implementiert werden kann. Auf der anderen Seite hindert das sie überhaupt nicht daran, in der C ++ - Standardbibliothek oder der STL zu sein, und ich bin mir ziemlich sicher, dass niemand vorhat, sie in einer Art eingebetteter Plattform zu verwenden.

Nun zur langen Antwort.

pow(x, n)kann in vielen Fällen viel schneller gemacht werden, indem man sich nauf eine natürliche Zahl spezialisiert. Ich musste für fast jedes Programm, das ich schreibe, meine eigene Implementierung dieser Funktion verwenden (aber ich schreibe viele mathematische Programme in C). Die spezialisierte Operation kann rechtzeitig durchgeführt O(log(n))werden, aber wenn sie nklein ist, kann eine einfachere lineare Version schneller sein. Hier sind Implementierungen von beiden:

    // Computes x^n, where n is a natural number.
    double pown(double x, unsigned n)
    {
        double y = 1;
        // n = 2*d + r. x^n = (x^2)^d * x^r.
        unsigned d = n >> 1;
        unsigned r = n & 1;
        double x_2_d = d == 0? 1 : pown(x*x, d);
        double x_r = r == 0? 1 : x;
        return x_2_d*x_r;
    }
    // The linear implementation.
    double pown_l(double x, unsigned n)
    {
        double y = 1;
        for (unsigned i = 0; i < n; i++)
            y *= x;
        return y;
    }

(Ich bin gegangen xund der Rückgabewert verdoppelt sich, weil das Ergebnis von pow(double x, unsigned n)ungefähr so ​​oft wie möglich in ein Doppel passt pow(double, double).)

(Ja, pownist rekursiv, aber das Brechen des Stapels ist absolut unmöglich, da die maximale Stapelgröße ungefähr gleich ist log_2(n)und neine Ganzzahl ist. Wenn nes sich um eine 64-Bit-Ganzzahl handelt, erhalten Sie eine maximale Stapelgröße von etwa 64. Keine Hardware ist so extrem Speicherbeschränkungen, mit Ausnahme einiger zwielichtiger PICs mit Hardware-Stacks, die nur 3 bis 8 Funktionsaufrufe tief gehen.)

Was die Leistung angeht, werden Sie überrascht sein, wozu eine Gartensorte pow(double, double)in der Lage ist. Ich habe hundert Millionen Iterationen auf meinem 5 Jahre alten IBM Thinkpad getestet x, die der Iterationsnummer und n10 entsprechen. In diesem Szenario habe ich pown_lgewonnen. glibc pow()dauerte 12,0 Benutzersekunden, pown7,4 Benutzersekunden und pown_lnur 6,5 Benutzersekunden. Das ist also nicht allzu überraschend. Wir haben das mehr oder weniger erwartet.

Dann lasse xich konstant sein (ich setze es auf 2,5) und habe nhundert Millionen Mal von 0 auf 19 geschleift . Diesmal powgewann glibc ganz unerwartet und durch einen Erdrutsch! Es dauerte nur 2,0 Sekunden. Ich pownbrauchte 9,6 Sekunden und pown_l12,2 Sekunden. Was ist hier passiert? Ich habe einen weiteren Test gemacht, um das herauszufinden.

Ich habe das Gleiche wie oben gemacht, nur mit xeiner Million. Diesmal powngewann bei 9,6s. pown_ldauerte 12,2 s und glibc pow dauerte 16,3 s. Jetzt ist es klar! glibc powschneidet besser ab als die drei, wenn xes niedrig ist, aber am schlechtesten, wenn xes hoch ist. Wenn xhoch ist, ist pown_ldie beste Leistung, wenn nes niedrig ist, und powndie beste Leistung, wenn xes hoch ist.

Hier sind drei verschiedene Algorithmen, von denen jeder unter den richtigen Umständen eine bessere Leistung als die anderen erzielen kann. Also, letztlich, die am ehesten zu verwenden , hängt davon ab , wie Sie planen , über die Verwendung pow, aber die richtige Version verwenden ist es wert, und ist schön , alle Versionen haben. Mit einer Funktion wie der folgenden können Sie sogar die Auswahl des Algorithmus automatisieren:

double pown_auto(double x, unsigned n, double x_expected, unsigned n_expected) {
    if (x_expected < x_threshold)
        return pow(x, n);
    if (n_expected < n_threshold)
        return pown_l(x, n);
    return pown(x, n);
}

Solange x_expectedund n_expectedzum Zeitpunkt der Kompilierung Konstanten festgelegt werden, entfernt ein Optimierungs-Compiler, der es wert ist, automatisch den gesamten pown_autoFunktionsaufruf und ersetzt ihn durch die entsprechende Auswahl der drei Algorithmen. (Wenn Sie nun tatsächlich versuchen wollen, dies zu verwenden , müssen Sie wahrscheinlich ein wenig damit spielen, da ich nicht genau versucht habe , das zu kompilieren, was ich oben geschrieben habe .;))

Auf der anderen Seite pow funktioniert glibc und glibc ist bereits groß genug. Der C-Standard soll portabel sein, auch für verschiedene eingebettete Geräte (tatsächlich sind sich eingebettete Entwickler überall im Allgemeinen einig, dass glibc bereits zu groß für sie ist), und er kann nicht portabel sein, wenn für jede einfache mathematische Funktion jede enthalten sein muss alternativer Algorithmus, könnte von nutzen sein. Deshalb ist es nicht im C-Standard.

Fußnote: Beim Testen der -s -O2Zeitleistung habe ich meinen Funktionen relativ großzügige Optimierungsflags ( ) gegeben, die wahrscheinlich mit dem vergleichbar sind, wenn nicht sogar schlechter als das, was wahrscheinlich zum Kompilieren von glibc auf meinem System (archlinux) verwendet wurde. Die Ergebnisse sind also wahrscheinlich Messe. Für einen strengeren Test müsste ich glibc selbst kompilieren und ich habe wirklich keine Lust dazu. Früher habe ich Gentoo verwendet, daher erinnere ich mich, wie lange es dauert, auch wenn die Aufgabe automatisiert ist . Die Ergebnisse sind für mich schlüssig (oder eher nicht schlüssig) genug. Sie können dies natürlich gerne selbst tun.

Bonusrunde: Eine Spezialisierung pow(x, n)auf alle Ganzzahlen ist von entscheidender Bedeutung, wenn eine genaue Ganzzahlausgabe erforderlich ist. Ziehen Sie in Betracht, Speicher für ein N-dimensionales Array mit p ^ N Elementen zuzuweisen. Wenn p ^ N auch nur um eins ausgeschaltet wird, tritt möglicherweise ein zufällig auftretender Segfault auf.

Ein Grund dafür, dass C ++ keine zusätzlichen Überladungen aufweist, ist die Kompatibilität mit C.

C ++ 98 hat Funktionen wie double pow(double, int), aber diese wurden in C ++ 11 mit dem Argument entfernt, dass C99 sie nicht enthielt.

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3286.html#550

Ein etwas genaueres Ergebnis zu erzielen bedeutet auch, ein etwas anderes Ergebnis zu erzielen.

Die Welt entwickelt sich ständig weiter, ebenso wie die Programmiersprachen. Der vierte Teil der C-Dezimalstelle TR ¹ fügt einige weitere Funktionen hinzu <math.h>. Für diese Frage können zwei Familien dieser Funktionen von Interesse sein:

• Die pownFunktionen, die eine Gleitkommazahl und einen intmax_tExponenten annehmen.
• Die powrFunktionen, die zwei Gleitkommazahlen ( xund y) verwenden und mit der Formel xzur Potenz yberechnen exp(y*log(x)).

Es scheint, dass die Standard-Leute diese Funktionen letztendlich als nützlich genug erachteten, um in die Standardbibliothek integriert zu werden. Das Rationale ist jedoch, dass diese Funktionen vom ISO / IEC / IEEE 60559: 2011- Standard für binäre und dezimale Gleitkommazahlen empfohlen werden . Ich kann nicht sicher sagen, welcher "Standard" zum Zeitpunkt von C89 befolgt wurde, aber die zukünftigen Entwicklungen von <math.h>werden wahrscheinlich stark von den zukünftigen Entwicklungen des ISO / IEC / IEEE 60559- Standards beeinflusst.

Beachten Sie, dass der vierte Teil der Dezimal-TR nicht in C2x (der nächsten größeren C-Revision) enthalten ist und wahrscheinlich später als optionale Funktion enthalten sein wird. Ich hatte keine Absicht, diesen Teil der TR in eine zukünftige C ++ - Revision aufzunehmen.

¹ Sie können einige Arbeit-in-progress finden Dokumentation hier .

Vielleicht, weil die ALU des Prozessors eine solche Funktion für ganze Zahlen nicht implementiert hat, aber es gibt eine solche FPU-Anweisung (wie Stephen betont, handelt es sich tatsächlich um ein Paar). Es war also tatsächlich schneller, in Double umzuwandeln, pow mit Doubles aufzurufen, dann auf Überlauf zu testen und zurückzusetzen, als es mit ganzzahliger Arithmetik zu implementieren.

(Zum einen reduzieren Logarithmen die Potenzen auf Multiplikation, aber Logarithmen von ganzen Zahlen verlieren bei den meisten Eingaben viel Genauigkeit.)

Stephen hat Recht, dass dies auf modernen Prozessoren nicht mehr der Fall ist, aber der C-Standard, als die mathematischen Funktionen ausgewählt wurden (C ++ hat nur die C-Funktionen verwendet), ist jetzt was, 20 Jahre alt?

Hier ist eine wirklich einfache O (log (n)) - Implementierung von pow (), die für alle numerischen Typen, einschließlich Ganzzahlen , funktioniert :

template<typename T>
static constexpr inline T pown(T x, unsigned p) {
    T result = 1;

    while (p) {
        if (p & 0x1) {
            result *= x;
        }
        x *= x;
        p >>= 1;
    }

    return result;
}

Es ist besser als die O (log (n)) - Implementierung von enigmaticPhysicist, da keine Rekursion verwendet wird.

Es ist auch fast immer schneller als seine lineare Implementierung (solange p> ~ 3), weil:

• Es wird kein zusätzlicher Speicher benötigt
• Es werden nur ~ 1,5x mehr Operationen pro Schleife ausgeführt
• Es werden nur ~ 1,25x mehr Speicheraktualisierungen pro Schleife durchgeführt

Tatsächlich tut es das auch.

Seit C ++ 11 gibt es eine Vorlagenimplementierung von pow(int, int)--- und noch allgemeineren Fällen, siehe (7) unter http://en.cppreference.com/w/cpp/numeric/math/pow

EDIT: Puristen können argumentieren, dass dies nicht korrekt ist, da tatsächlich "geförderte" Typisierung verwendet wird. Auf die eine oder andere Weise erhält man ein korrektes intErgebnis oder einen Fehler bei den intParametern.

Ein sehr einfacher Grund:

5^-2 = 1/25

Alles in der STL-Bibliothek basiert auf den genauesten und robustesten Dingen, die man sich vorstellen kann. Sicher, das int würde auf eine Null zurückkehren (von 1/25), aber dies wäre eine ungenaue Antwort.

Ich stimme zu, es ist in einigen Fällen komisch.