Warum ist nicht `int pow(int base, int exponent) " in der standard C++ - Bibliotheken?

https://stackoverflow.com/questions/2398442

25-09-2019
|

Frage

Ich fühle mich wie ich muss nur nicht in der Lage zu finden es.Gibt es einen Grund, dass die C++ pow Funktion implementiert nicht die "power" - Funktion für alles, außer floats und doubles?

Ich weiß, die Umsetzung ist trivial, ich fühle mich einfach wie ich bin, die Arbeit sollte in einem standard-Bibliothek.Eine robuste power-Funktion ist (d.h.Griffe überlauf in einigen Einklang, explizite Weise) wird nicht Spaß, zu schreiben.

Lösung

Wie in der Tat, es tut.

Da C ++ 11 gibt es eine Templat Implementierung von pow(int, int) --- und noch allgemeinere Fälle siehe (7) in http://en.cppreference.com/w/cpp/numeric/math/ pow

EDIT: Puristen mögen argumentieren, dies nicht korrekt ist, da es tatsächlich ist „befördert“ Typisierung verwendet. Eine oder andere Weise, so erhält man ein korrektes int Ergebnis oder einen Fehler, auf int Parametern.

Andere Tipps

Ab C++11 wurden spezielle Fälle in die Suite von Potenzfunktionen hinzugefügt (und andere). C++11 [c.math] /11 Staaten, nach all den float/double/long double Überlastungen listing (Hervorhebung von mir, und paraphrasiert):

Darüber hinaus gibt sind zusätzliche Überlastungen ausreichend sein, um sicherzustellen, , wenn ein Argument zu einem double Parameter entsprechenden Typ double oder einen Integer-Typ hat, dann werden alle Argumente double Parameter entsprechen, werden zu double effektiv gegossen.

Also, im Grunde, integer Parameter auf Doppel aktualisiert werden, um die Operation auszuführen.

Vor C++11 (das war, wenn Ihre Frage gestellt wurde), keine ganze Zahl Überlastungen vorhanden war.

Da ich weder eng mit den Machern von C noch C++ in den Tagen ihrer Schöpfung (obwohl ich am eher alt), noch einen Teil der ANSI / ISO-Gremien, die die Standards geschaffen, dies ist unbedingt Meinung von mir. Ich möchte es die informiert Meinung denken, aber, wie meine Frau wird Ihnen sagen, (häufig und ohne viel Ermutigung erforderlich), habe ich vor, mich geirrt: -)

Supposition, für das, was es wert ist, folgt.

I verdächtigt , dass der Grund die ursprünglich vorge ANSI C nicht über diese Funktion hat, weil es völlig unnötig war. Zuerst gab es schon eine ganz gute Art und Weise ganzzahlige Potenzen von tun (mit Doppel-und dann einfach wieder auf eine ganze Zahl konvertieren, die Überprüfung für Integer-Überlauf und Unterlauf vor der Konvertierung).

Zweitens, eine andere Sache, die Sie sich merken müssen, ist, dass die ursprüngliche Absicht von C war als Systeme Programmiersprache, und es ist fraglich, ob Floating-Point in dieser Arena überhaupt wünschenswert ist.

Da einer seiner ursprünglichen Fälle Verwendung von Code auf UNIX, würde die Gleitkomma neben nutzlos gewesen. BCPL, auf dem C beruhte, hatte auch keine Verwendung für Kräfte (es hat keinen Punkt überhaupt schwimmen, aus dem Gedächtnis).

Als beiseite, ein integraler Strombetreiber wäre wahrscheinlich ein eher Binäroperators gewesen sein als ein Bibliotheksaufruf. Sie addieren sich nicht zwei ganze Zahlen mit x = add (y, z) aber mit x = y + z -. Teil der Sprache richtige anstatt der Bibliothek

Drittens, da die Umsetzung der integralen Leistung relativ trivial ist, ist es fast sicher, dass die Entwickler der Sprache besser ihre Zeit Bereitstellung nützliche Dinge verwenden würden (siehe unten Kommentare zu Opportunitätskosten).

Das ist auch relevant für die ursprüngliche C++. Da die ursprüngliche Implementierung effektiv nur ein Übersetzer war die C Code erzeugt, trug sie viele der Eigenschaften von C über. Seine ursprüngliche Absicht war C-mit-Klassen, nicht C-mit-Klassen-plus-a-little-bit-of-extra-Mathe-Zeug.

Wie, warum wurde es nie zuvor C++11 die Standards hinzugefügt, müssen Sie daran denken, dass die Standards setzenden Gremien spezifische Richtlinien zu folgen. Zum Beispiel war ANSI C speziell damit beauftragt zu kodifizieren bestehenden Praxis, nicht eine neue Sprache zu erstellen. Andernfalls könnten sie verrückt worden und wir Ada haben: -)

Später Iterationen dieser Norm haben auch spezifische Leitlinien und in den Rationale Dokumenten gefunden werden (Gründe, warum der Ausschuß, bestimmte Entscheidungen, nicht Gründe für die Sprache selbst).

Zum Beispiel die C99 Begründung Dokument speziell trägt auf zwei der C89 Leitprinzipien, die begrenzen, was hinzugefügt werden können:

Halten Sie die Sprache klein und einfach.
Geben Sie nur eine Möglichkeit, eine Operation zu tun.

Richtlinien (nicht notwendigerweise die spezifische ist) ist für die einzelnen vorgesehenGruppen arbeiten und damit die C++ Ausschüsse (und alle anderen ISO-Gruppen) als auch begrenzen.

Darüber hinaus werden die Standardisierungsgremien erkennen, dass es eine ist Opportunitätskosten (ein wirtschaftlicher Begriff bedeutet, was Sie für eine Entscheidung getroffen zu verzichten haben) zu jeder Entscheidung, die sie treffen. die Möglichkeit, Kosten für den Kauf zum Beispiel, dass $ 10.000 uber-Gaming-Maschine sind herzliche Beziehungen (oder wahrscheinlich alle Beziehungen) mit dem anderen Hälfte für etwa sechs Monate.

Eric Gunnerson erklärt diese gut mit seinen -100 Punkte Erklärung , warum die Dinge nicht immer hinzugefügt, um Microsoft-Produkte im Grunde eine Funktion 100 Punkten in das Loch beginnt, so dass es ziemlich viel Wert hinzuzufügen hat auch in Betracht gezogen werden.

Mit anderen Worten würden Sie lieber einen integrierten Strom Operator (die, ehrlich gesagt, jeder halbwegs anständige Coder in 10 Minuten zaubern konnte) oder Multi-Threading in den Standard? Für mich, würde ich es vorziehen, diese zu haben und nicht etwa mit den unterschiedlichen Implementierungen unter UNIX und Windows Dreck haben.

Ich möchte auch Tausende und Abertausende von Sammlung der Standardbibliothek (Hashes, btrees, rot-schwarze Bäume, Wörterbuch, willkürliche Karten usw.) als gut, aber, wie die Begründung Staaten sehen:

Ein Standard ist ein Vertrag zwischen Implementierer und Programmierer.

Und die Zahl der Implementierer auf den Normungsgremien überwiegen bei weitem die Anzahl der Programmierer (oder zumindest diejenigen, die Programmierer verstehen Opportunitätskosten nicht). Wenn all das Zeug gegeben, wäre der nächste Standard C++ C++215x sein und wahrscheinlich voll von Compiler-Entwickler 300 Jahre danach umgesetzt werden würde.

Wie auch immer, das ist meine (eher voluminös) Gedanken über die Angelegenheit. Wenn nur Stimmen waren eher basiert auf Quantität ausgehändigt als Qualität, würde ich bald alle anderen aus dem Wasser blasen. Danke fürs Zuhören: -)

Für irgendwelche Feste Breite integral Typ, die fast alle möglichen input-Paare überlauf der Art jedenfalls.Was ist der nutzen von Standardisierung eine Funktion, die nicht geben ein brauchbares Ergebnis für die überwiegende Mehrheit der möglichen Eingaben?

Sie ziemlich viel brauchen, um einen großen integer-Typ in Auftrag zu machen die Funktion nützlich, und die meisten großen integer-Bibliotheken bieten die Funktion.

Edit: In einem Kommentar auf die Frage, static_rtti schreibt "die Meisten Eingänge verursachen, dass es zu überlaufen?Das gleiche gilt für exp und Doppel-pow, ich sehe nicht, dass jemand beschwert." Dies ist falsch.

Wollen wir beiseite lassen exp, weil das ist neben dem Punkt (auch wenn es eigentlich meinem Fall stärker), und konzentrieren Sie sich auf double pow(double x, double y).Für welchen Teil von (x,y) Paaren macht diese Funktion, etwas nützliches zu tun (D. H., nicht nur, überlauf oder Unterlauf)?

Ich bin eigentlich Los, um den Fokus nur auf einen kleinen Teil der Eingabe Paare, für die pow macht Sinn, denn das wird ausreichen, um meinen Standpunkt zu beweisen:wenn x positiv ist, und |y| <= 1, dann pow nicht überlauf oder Unterlauf.Diese umfasst beinahe ein Viertel aller Gleitkomma-Paare (genau die Hälfte der nicht-NaN-floating-point-zahlen, die positiv sind, und nur weniger als die Hälfte der nicht-NaN-floating-point-zahlen haben Größenordnung von weniger als 1).Offensichtlich gibt es eine Menge der andere input-Paare, für die pow produziert brauchbare Ergebnisse, aber wir haben festgestellt, dass es mindestens ein Viertel aller Eingänge.

Schauen wir uns nun an ein fester Breite (alsonon-bignum) - Ganzzahl-power-Funktion.Für das, was Teil-Eingänge hat es nicht einfach überlaufen?Zur Maximierung der Anzahl von sinnvollen input-Paare, die Basis unterzeichnet werden soll, und den Exponenten ohne Vorzeichen.Angenommen, die Basis und der exponent sind beide n bits breit.Wir können leicht eine Schranke der Teil der Eingaben, die sinnvoll sind:

Wenn der exponent 0 oder 1, dann ist jede Basis ist sinnvoll.
Wenn der exponent ist 2 oder mehr, dann keine Basis, die größer als 2^(n/2) erzeugt ein sinnvolles Ergebnis.

So, der 2^(2n) input-Paare, die weniger als 2^(n+1) + 2^(3n/2) sinnvolle Ergebnisse.Wenn wir uns anschauen, was ist wahrscheinlich die häufigste Verwendung, 32-bit-Ganzzahlen, bedeutet dies, dass etwas in der Größenordnung von 1/1000stel ein Prozent des Eingabe-Paare nicht einfach überlaufen.

Weil es keine Möglichkeit, alle ganzzahlige Potenzen in einem int darstellt sowieso:

>>> print 2**-4
0.0625

Das ist eigentlich eine interessante Frage. Ein Argument, das ich nicht in der Diskussion gefunden, ist der einfache Mangel an offensichtlichen Rückgabewerte für die Argumente. Lassen Sie uns zählen die Art und Weise der hypthetical int pow_int(int, int) Funktion fehlschlagen könnte.

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

Die Funktion hat mindestens zwei Ausfallmodi. Ganze Zahlen können diese Werte nicht darstellen, das Verhalten der Funktion in diesen Fällen würde durch die Norm definiert werden müssen -. Und Programmierer würden sich bewusst, wie genau die Funktion Griffe diesen Fällen werden müssen

Insgesamt ist die Funktion heraus zu verlassen scheint, wie die einzig sinnvolle Option. Der Programmierer kann die Gleitkomma-Version mit allen anstelle Berichterstattung zur Verfügung der Fehler verwendet werden.

Kurze Antwort:

Eine Spezialisierung von pow(x, n), wo n eine natürliche Zahl ist oft nützlich für Zeitleistung . Aber die noch generic pow() der Standard-Bibliothek funktioniert recht ( überraschend! ) für diesen Zweck gut und es ist absolut entscheidend, so wenig wie möglich in der Standard-C-Bibliothek enthält, so dass es als tragbar und so einfach gemacht werden kann zu implementieren, wie möglich. Auf der anderen Seite, die überhaupt nicht aufhört es aus in dem C ++ seine Standardbibliothek oder die STL, die ich bin ziemlich sicher, niemand in irgendeiner Art von Embedded-Plattform plant verwendet wird.

Nun, für die lange Antwort.

pow(x, n) kann auf eine natürliche Zahl von spezialisierten n in vielen Fällen viel schneller gemacht werden. Ich habe für meine eigene Implementierung dieser Funktion zu verwenden, fast jedes Programm, das ich schreiben (aber ich habe eine Menge mathematischer Programme in C schreiben). Der Fachbetrieb kann in O(log(n)) Zeit durchgeführt werden, aber wenn n klein ist, eine einfachere lineare Version schneller sein kann. 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;
    }

(I links x und den Rückgabewert als verdoppelt, da das Ergebnis von pow(double x, unsigned n) im Doppel paßt etwa so oft wie pow(double, double) wird.)

(Ja, das ist pown rekursiv, aber der Stapel brechen ist absolut unmöglich, da die maximale Stapelgröße wird in etwa gleich log_2(n) und n eine ganze Zahl ist. Wenn n ist ein 64-Bit-Integer, dass Ihnen eine maximale Stapelgröße von gibt über 64. Nein Hardware, wie extreme Speicherbeschränkungen hat, mit Ausnahme einiger zwielichtigen PICs mit Hardware-Stacks, die nur tief 3 bis 8 Funktionsaufrufe gehen.)

Was die Leistung, Sie werden überrascht sein, was ein Garten Vielzahl pow(double, double) in der Lage ist. Getestet habe ich hundert Millionen Iterationen auf meiner 5-jährig IBM Thinkpad mit x gleich die Wiederholungszahl und n gleich 10. In diesem Szenario pown_l gewonnen. glibc pow() dauerte 12,0 Sekunden Benutzer, pown 7.4 Benutzer Sekunden dauerte, und pown_l dauerte nur 6,5 Sekunden Benutzer. Also das ist nicht allzu überraschend. Wir waren mehr oder weniger dies erwartet.

Dann lasse ich x konstant sein (Ich stelle es auf 2,5), und ich geschleift n 0-19 hundert Millionen mal. Diesmal ganz unerwartet, glibc pow gewonnen und durch einen Erdrutsch! Es dauerte nur 2,0 Sekunden Benutzer. Mein pown nahm 9,6 Sekunden, und pown_l dauerte 12,2 Sekunden. Was ist hier passiert? Ich habe einen weiteren Test zu erfahren.

Ich habe das gleiche wie oben nur mit x gleich zu einer Million. Diesmal gewann pown bei 9.6s. pown_l nahm 12.2s und glibc pow nahm 16.3s. Nun, es ist klar! glibc pow führt besser als die drei, wenn x ist niedrig, aber am schlimmsten, wenn x hoch ist. Wenn x hoch ist, pown_l führt am besten, wenn n niedrig ist, und pown führt am besten, wenn x hoch ist.

So, hier sind drei verschiedene Algorithmen, jeweils in der Lage eine bessere Leistung als die anderen unter den richtigen Umständen. Also, letztlich, die am ehesten zu verwenden, hängt davon ab, wie Sie planen pow über die Verwendung, aber mit der richtigen Version ist es wert, und schön alle Versionen sind mit. In der Tat könnte man sogar die Wahl des Algorithmus mit einer Funktion wie folgt 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_expected und n_expected Konstanten sind bei der Kompilierung entschieden, zusammen mit möglicherweise einigen anderen Einschränkungen, eine Optimierung der Compiler wert sein Salz wird automatisch den gesamten pown_auto Funktionsaufruf entfernen und ersetzen sie durch die geeignete Wahl der dreiAlgorithmen. (Nun, wenn Sie tatsächlich zu um zu versuchen, gehen Verwendung das, werden Sie wahrscheinlich mit ihm ein wenig zu Spielzeug, weil ich nicht genau versuchen Compilieren , was ich ‚d oben geschrieben;.))

Auf der anderen Seite, glibc pow funktioniert und glibc ist schon groß genug. Der C-Standard soll tragbar sein, um verschiedene einschließlich Embedded-Geräte (in der Tat Entwickler eingebettet zustimmen überall im Allgemeinen, dass glibc schon zu groß für sie ist), und es kann nicht tragbar sein, wenn für jede einfache mathematische Funktion braucht es jeden alternativen Algorithmus zu schließen, dass könnte von nutzen sein. Also, das ist, warum es nicht in dem C-Standard ist.

Fußnote: In der Zeit, Performance-Tests, gab ich meine Funktionen relativ großzügig Optimierungsflags (-s -O2), die wahrscheinlich sein vergleichbar sind, wenn nicht schlechter als, was wahrscheinlich auf meinem System zu kompilieren glibc verwendet wurde (archlinux), so die Ergebnisse sind wahrscheinlich fair. Für eine strengere Prüfung, würde ich muss mich kompilieren glibc und ich reeeally keine Lust, das zu tun. Ich verwenden Gentoo zu verwenden, so dass ich erinnere mich, wie lange es dauert, auch wenn die Aufgabe ist automatische . Die Ergebnisse sind schlüssig (oder eher nicht schlüssig) genug für mich. Sie sind natürlich willkommen dies selbst zu tun.

Bonusrunde: Eine Spezialisierung von pow(x, n) auf alle ganzen Zahlen instrumental , wenn eine exakte ganzzahlige Ausgabe erforderlich ist, was geschieht. Betrachten wir für eine N-dimensionale Array mit p ^ N Elementen Zuteilen Speicher. Erst p ^ N aus, auch durch eine in einer möglicherweise zufällig auftretenden segfault führen wird.

Ein Grund für C ++ keine zusätzliche Überlastungen haben, ist mit C kompatibel sein.

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

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

Wie Sie ein etwas genaueres Ergebnis bedeutet auch ein etwas bekommen andere Ergebnis.

Die Welt wird ständig weiterentwickelt und so sind die Programmiersprachen. Der vierte Teil des C decimal TR ¹ fügt einige weitere Funktionen zu <math.h>. Zwei Familien dieser Funktionen von Interesse für diese Frage sein können:

Die pown Funktionen, die eine Fließkommazahl und einen Exponenten intmax_t nimmt.
powr Die Funktionen, die zwei Gleitpunkte Nummern (x und y) und compute x an den Strom y mit der Formel exp(y*log(x)) nimmt.

Es scheint, dass die Standard-Typen schließlich diese Funktionen nützlich genug als in der Standard-Bibliothek integriert werden. Allerdings ist die rationale, dass diese Funktionen durch die empfohlen werden, ISO / IEC / IEEE 60559: 2011 Standard für binäre und dezimale Gleitkommazahlen. Ich kann nicht sicher sagen, was „Standard“ zum Zeitpunkt des C89 gefolgt wurde, aber die künftigen Entwicklungen von <math.h> werden wahrscheinlich stark von den künftigen Entwicklungen des beeinflusst werden ISO / IEC / IEEE 60559 Standard .

Beachten Sie, dass der vierte Teil des Dezimalsystem TR nicht in C2x (die nächsten große C Revision) aufgenommen werden, und wird wahrscheinlich später als optionales Feature enthalten sein. Es gab keine Absicht ich kenne diesen Teil der TR enthält in einem zukünftigen C ++ Revision an.

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

Vielleicht, weil die ALUs Prozessor nicht umgesetzt, eine solche Funktion für ganze Zahlen, aber es ist so ein FPU-Befehl (als Stephen weist darauf hin, es ist eigentlich ein Paar). So war es tatsächlich schneller Guss zu verdoppeln, Call pow mit Doppelzimmer, dann Test für Überlauf und Guss zurück, als es zu implementieren Integer-Arithmetik verwendet wird.

(für eine Sache, Logarithmen reduzieren Kräfte Multiplikation, aber Logarithmen von ganzen Zahlen verlieren viel Genauigkeit für die meisten Eingänge)

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

Ein sehr einfacher Grund:

5^-2 = 1/25

Alles in der STL-Bibliothek basiert auf dem genauesten, robusten Material vorstellbar. Sicher, zurückkehren würde die int zu einer Null (von 25.1), aber dies würde eine ungenaue Antwort sein.

Ich bin einverstanden, es ist seltsam in einigen Fällen.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow